Skip to content

Instantly share code, notes, and snippets.

@cruxrebels

cruxrebels/MinStepsInInfiniteGrid.cpp

Last active September 20, 2021 05:20
Show Gist options
  • Save cruxrebels/829e95c4455c470f7f50e7ff77d70b8b to your computer and use it in GitHub Desktop.
Save cruxrebels/829e95c4455c470f7f50e7ff77d70b8b to your computer and use it in GitHub Desktop.
Download ZIP
You are in an infinite 2D grid where you can move in any of the 8 directions : (x,y) to (x+1, y), (x - 1, y), (x, y+1), (x, y-1), (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1) You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the firs…
Raw
MinStepsInInfiniteGrid.cpp
/*
You are in an infinite 2D grid where you can move in any of the 8 directions :
(x,y) to (x+1, y), (x - 1, y), (x, y+1), (x, y-1), (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1)
You are given a sequence of points and the order in which you need to cover the points.
Give the minimum number of steps in which you can achieve it. You start from the first point.
Example : Input : [(0, 0), (1, 1), (1, 2)] Output : 2 It takes 1 step to move from (0, 0) to (1, 1).
It takes one more step to move from (1, 1) to (1, 2).
This question is intentionally left slightly vague.
Clarify the question by trying out a few cases in the “See Expected Output” section.
Tags: InterviewBit Arrays Problem https://www.interviewbit.com/problems/min-steps-in-infinite-grid/
*/
// Input : X and Y co-ordinates of the points in order.
// Each point is represented by (X[i], Y[i])
int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
int count = 0;
int a = 0; int b = 0;
for (int i=0; i < (X.size()-1); ++i) {
a = abs((X[i+1]-X[i]));
b = abs((Y[i+1]-Y[i]));
count += max(a,b);
}
return count;
}
@nolanding
Copy link

nolanding commented Sep 3, 2020 via email

@cruxrebels
Copy link
Author

cruxrebels commented Sep 3, 2020 via email

@Anjali-Sah
Copy link

Why are we taking
count += max(a,b);
instead of
count +=min(a,b);
as the question asks for min no steps?

@cruxrebels
Copy link
Author

@Anjali-Sah because the number of steps or distance remains constant to reach from point A to point B. Problem statement reads, "Give the minimum number of steps in which you can achieve it." - It does not literally mean take min(a,b). If we take min(a,b) in each iteration, the number of steps and iterations will only increase to reach the end point/cell B. Taking max(a,b) ensures we find the shortest path in less iterations to reach final destination. (P.S. Distance being constant in the problem for each step distance being 1).

Hope this clarifies a bit.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment