Find the Minimum Number of Steps in an Infinite Grid

Teiva Harsanyi
solvingalgo
Published in
3 min readSep 22, 2018

--

Problem

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.

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 4

In 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 4

As 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.

Follow me on Twitter @teivah

--

--

Teiva Harsanyi
solvingalgo

Software Engineer @Google | 📖 100 Go Mistakes author | 改善