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 - Find the distance between points

To solve this problem, we need to determine the minimum number of steps required to move from one point to the next in an infinite 2D grid where movement is allowed in the 8 possible directions.

Key Insight

The minimum steps to move from point (x1, y1) to point (x2, y2) can be calculated based on the maximum of the absolute differences of their coordinates. This is because in each step, you can move diagonally, which reduces both x and y coordinates simultaneously.

For example:

  • To move from (0, 0) to (1, 1) takes 1 step as you can move diagonally.
  • To move from (1, 1) to (1, 2) takes 1 step as you can move vertically.

Approach

  1. Iterate through each pair of consecutive points in the given sequence.
  2. For each pair of points, calculate the minimum steps required to move from the first point to the second point using the formula:
    • steps = max(abs(x2 - x1), abs(y2 - y1))
  3. Sum these minimum steps for all consecutive pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public int minStepsToCoverPoints(int[][] points) {
        int totalSteps = 0;

        for (int i = 0; i < points.length - 1; i++) {
            totalSteps += steps(points[i], points[i + 1]);
        }

        return totalSteps;
    }

    private int steps(int[] p1, int[] p2) {
        return Math.max(Math.abs(p2[0] - p1[0]), Math.abs(p2[1] - p1[1]));
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] points = {{0, 0}, {1, 1}, {1, 2}};

        System.out.println("Minimum steps to cover points: "
            + solution.minStepsToCoverPoints(points)); // Output: 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def min_steps_to_cover_points(points):
    def steps(p1, p2):
        return max(abs(p2[0] - p1[0]), abs(p2[1] - p1[1]))

    total_steps = 0
    for i in range(len(points) - 1):
        total_steps += steps(points[i], points[i + 1])

    return total_steps


# Example usage:
points = [(0, 0), (1, 1), (1, 2)]
print(min_steps_to_cover_points(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.