Find the Minimum Number of Steps in an Infinite Grid
Problem
- Minimum number of steps in an infinite grid: InterviewBit
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.
- Category: Arrays
Solving Process
Traversal Solution
We need to iterate over each point and compute each time the number of steps between two points.
The first idea which may pop into our mind to do this computation is to iterate from an existing to a target position:
4 | | | | |B|
3 | | | |x| |
2 | | |x| | |
1 | |x| | | |
0 |A| | | | |
0 1 2 3 4In this case, to go from A to B, we need 4 steps because we made 4 iterations:
- From (0, 0) to (1, 1)
- From (1, 1) to (2, 2)
- From (2, 2) to (3, 3)
- And from (3, 3) to (4, 4)
In Java, we can translate it this way:
The space complexity is O(1) but the time complexity is O(n*s) with n the number of points and s the number of steps between each point. So, it is a quadratic time complexity which is not really a good sign.
Computation Solution
We are obviously obliged to iterate over each point so the optimization has to be done on the way to compute the number of steps between two points.
Can we simplify this computation without having to iterate over each step? Yes, we can.
Let’s check the following example and see how to compute the number of steps between A and B.
4 | | |B| | |
3 | | | | | |
2 | | | | | |
1 | | | | | |
0 |A| | | | |
0 1 2 3 4As we can move diagonally, the result is simply Max(distanceX, distanceY). This means we can get the number of steps in a constant time.
In Java:
The space complexity is O(1) whereas the time complexity is, this time, linear.
