Min Steps in Infinite Grid in JavaScript

May 06, 2019

This question is taken from Interview Bit.

Question

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.

Input

Given two integer arrays A and B, where A[i] is x coordinate and B[i] is y coordinate of ith point respectively.

Output

Return an Integer, i.e minimum number of steps.

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

Solution approach

My approach was simple. Imagine a 2D graph and two random points. Draw a path between them based on the steps allowed.

Here's my thought process:

  1. A simplistic formula like |x2 - x1| + |y2 - y1| seemed to work for points like (1,1) -> (1, 4). But it wouldn't work for diagonal movements. (Everything between | denotes absolute value, i.e. value without the + or - sign.)
  2. It seemed like whenever there were diagonal movements, my formula accounted for an extra step for each diagonal movement.
  3. I need to subtract the extra step diagonal movements from my formula. So, I came up with the new formula. |x2 - x1| + |y2 - y1| - min(|x2 - x1|, |y2 - y1|). This removes the extra step being added because of diagonal movements.

Here's the solution:

var s = {
  coverPoints: function(A, B) {
    var totalSteps = 0;
    var currX = A[0];
    var currY = B[0];
    for (var i = 1; i < A.length; i++) {
      var common = Math.min(Math.abs(currX - A[i]), Math.abs(currY - B[i]));
      var steps = Math.abs(currX - A[i]) + Math.abs(currY - B[i]);
      totalSteps = totalSteps + steps - common;
      currX = A[i];
      currY = B[i];
    }
    return totalSteps;
  }
};

s.coverPoints([1, 2, 6], [1, 2, 6]);
Donate