Min Steps in Infinite Grid (IB)

Array Math

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.

For example:

Input:
A = [0, 1, 1]
B = [0, 1, 2]

Output: 2

Explaination: Given three points are: (0, 0),
(1, 1) and (1, 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).

Thought Process

• Can you think of a formula for calculating distance in O(1)?

  • Yes, Manhattan Distance formula

• What's the Manhattan Distance formula?

  • Take the sum of the absolute values of the differences of the coordinates. For example, if 𝑥 = (𝑎, 𝑏) and 𝑦 = (𝑐, 𝑑), the Manhattan distance between 𝑥 and 𝑦 is

    |𝑎 − 𝑐| + |𝑏 − 𝑑|.

  • The Manhattan distance (also known as rectilinear distance, city block distance, taxicab metric) is defined as the sum of the lengths of the projections of the line segment between the points onto the coordinate axes (a.k.a. a grid).

Solution

class Solution:
    def coverPoints(self, A, B):
        count = 0
        if len(A)<=1:
            return 0
        else:   
            for i in range(len(A)-1):
                diff = max(abs(A[i]-A[i+1]), abs(B[i]-B[i+1]))
                count+=diff
            return count

Key Facts

• Since we are dealing with an infinite grid, the best distance formula to apply is the Manhattan distance (as opposed to using Euclidean distance which just deals with a straight line)

• While (x,y) are positive, you will move along the diagonal and (x, y) would both reduce by 1. When one of them becomes 0, you would move so that in each step the remaining number reduces by 1.

  • We are doing max(abs(x diff), abs(y diff)) (which is the Manhattan distance) because we can always replace (1 move up + 1 move left) by a north west diagonal move and likewise for other diagonals. So our main concern is to cover the max diff which is in either along x coordinate or y coordinate , because the smaller of the differences can be covered by this diagonal move as it will count for an x move as well as for a y move in just one move. So the max diff will be the distance not covered.

• For two points (𝑎, 𝑏) and (𝑐, 𝑑), the number of steps (not distance) between them will correspond to max(abs(𝑎 - 𝑐), abs(𝑏 - 𝑑)) since the max from either one would essentially be the "leftover" or "extra" step needed that isn't covered by the diagonal. (if the numbers are the same, then this means it's a straight diagonal.)

Time Complexity

• Time: $O(n)$

• Space: $O(1)$