Arrays - minimum number of steps in infinite grid

0 users say they have been asked this quesiton in interview.
Difficulty Level:

Problem Statement:

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

Solution:
/**
 * @input X : Integer array corresponding to the X co-ordinate
 * @input n1 : Integer array's ( X ) length
 * @input Y : Integer array corresponding to the Y co-ordinate
 * @input n2 : Integer array's ( Y ) length
 *
 * Points are represented by (X[i], Y[i])
 * 
 * @Output Integer
 *
 */
 
int MAX(int x, int y) 
{
    return (x > y) ? x : y;
}

int coverPoints(int* X, int n1, int* Y, int n2) {
    int len = 0;
    int i;
    int startx, starty;
    
    if (n1 == 0) return 0;
    
    if (n1 == 1) return 0;
    
    startx = X[0];
    starty = Y[0];
    for (i = 1; i < n1; i++) {
        int x = abs(startx - X[i]);
        int y = abs(starty - Y[i]);
        startx = X[i];
        starty = Y[i];
        
        len += MAX(x,y);
    }
    
    return len;
}
comments powered by Disqus