Minimum Steps to Traverse Points in an Infinite 2D Grid

Problem

You are in an infinite 2D grid where you can move in any of the 8 directions:

1
2
3
4
5
6
7
8
9


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

Examples

Example 1:

1
2
3


Input: [(0, 0), (1, 1), (1, 2)]
Output: 2
Explanation: 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

Method 1 – Chebyshev Distance

Intuition

Since the order of points is fixed, the problem reduces to finding the minimum steps needed to move from each point to the next.

At each move, you can go in any of 8 directions—including diagonally. If both the horizontal (X) and vertical (Y) distances between two points are positive, you can move diagonally, reducing both X and Y by 1 in a single step. Once either X or Y becomes zero, you continue in a straight line (horizontal or vertical) until you reach the target.

Therefore, the minimum number of steps to go from (x1, y1) to (x2, y2) is always the maximum of the absolute differences in their coordinates: max(abs(x1 - x2), abs(y1 - y2)). This is known as the Chebyshev distance.

This insight allows us to efficiently compute the total steps by summing the Chebyshev distances for each consecutive pair of points in the sequence.

Approach

For each consecutive pair of points, calculate the absolute difference in x and y.
The minimum steps to go from one point to the next is max(abs(x2-x1), abs(y2-y1)).
Sum this value for all consecutive pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    int minStepsToCoverPoints(const vector<pair<int, int>>& points) {
        int totalSteps = 0;
        for (size_t i = 1; i < points.size(); ++i) {
            totalSteps += max(abs(points[i].first - points[i-1].first), abs(points[i].second - points[i-1].second));
        }
        return totalSteps;
    }
};
// Example usage:
// vector<pair<int, int>> points = {{0, 0}, {1, 1}, {1, 2}};
// Solution().minStepsToCoverPoints(points); // Output: 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public class Solution {
    public int minStepsToCoverPoints(int[][] points) {
        int totalSteps = 0;
        for (int i = 0; i < points.length - 1; i++) {
            totalSteps += Math.max(Math.abs(points[i+1][0] - points[i][0]), Math.abs(points[i+1][1] - points[i][1]));
        }
        return totalSteps;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] points = {{0, 0}, {1, 1}, {1, 2}};
        System.out.println(solution.minStepsToCoverPoints(points)); // Output: 2
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


from typing import List, Tuple
class Solution:
    def minStepsToCoverPoints(self, points: List[Tuple[int, int]]) -> int:
        total_steps = 0
        for i in range(1, len(points)):
            total_steps += max(abs(points[i][0] - points[i-1][0]), abs(points[i][1] - points[i-1][1]))
        return total_steps

# Example usage:
points = [(0, 0), (1, 1), (1, 2)]
print(Solution().minStepsToCoverPoints(points))  # Output: 2

Complexity

⏰ Time complexity: O(n)
- The main method minStepsToCoverPoints iterates through the array of points. If there are n points, this iteration involves ( n - 1 ) comparisons.
- Each call to the steps method involves calculating the absolute difference and the maximum of two integers, which are constant-time operations ( O(1) ).
🧺 Space complexity: O(1), because the algorithm uses a constant amount of extra space regardless of the input size.

Problem#

Examples#

Solution#

Method 1 – Chebyshev Distance#

Intuition#

Approach#

Code#

Complexity#