Minimum Time Visiting All Points - Practice Coding Problems

Minimum Time Visiting All Points - Problem

On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi]. Return the minimum time in seconds to visit all the points in the order given by points.

You can move according to these rules:

In 1 second, you can either:
Move vertically by one unit
Move horizontally by one unit
Move diagonally √2 units (in other words, move one unit vertically then one unit horizontally in 1 second)

You have to visit the points in the same order as they appear in the array. You are allowed to pass through points that appear later in the order, but these do not count as visits.

Input & Output

Example 1 — Basic Case

$ Input: points = [[1,1],[3,4],[-1,0]]

› Output: 7

💡 Note: From [1,1] to [3,4]: max(|3-1|, |4-1|) = max(2,3) = 3 seconds. From [3,4] to [-1,0]: max(|-1-3|, |0-4|) = max(4,4) = 4 seconds. Total: 3 + 4 = 7 seconds.

Example 2 — Straight Line Movement

$ Input: points = [[3,2],[-2,2]]

› Output: 5

💡 Note: From [3,2] to [-2,2]: max(|-2-3|, |2-2|) = max(5,0) = 5 seconds. Only horizontal movement needed.

Example 3 — Single Point

$ Input: points = [[0,0]]

› Output: 0

💡 Note: Only one point, no movement required. Time = 0 seconds.

Constraints

1 ≤ points.length ≤ 100
points[i].length == 2
-1000 ≤ points[i][0], points[i][1] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of 2D coordinates representing points to visit in order

Process

Calculate Chebyshev distance between consecutive points

Output

Sum of all minimum travel times

Key Takeaway

🎯 Key Insight: Use Chebyshev distance (max of horizontal and vertical distances) since diagonal movement covers both axes simultaneously

Asked in

a Amazon 12 G Google 8

The key insight is that we can move diagonally to cover both horizontal and vertical distance simultaneously. The minimum time between two points is the Chebyshev distance: max(|dx|, |dy|). Best approach is the mathematical formula with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Distance Calculation	O(n)	O(1)	Calculate minimum time between consecutive points using Chebyshev distance
One-Pass Chebyshev Distance	O(n)	O(1)	Optimized implementation with single loop and inline calculations

Mathematical Distance Calculation — Algorithm Steps

Iterate through consecutive point pairs
Calculate horizontal and vertical distances
Take maximum distance as minimum time
Sum all minimum times

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Distances

Find horizontal and vertical distances between consecutive points

Move Diagonally

Move diagonally to cover min(dx, dy) distance in both axes

Move Straight

Move straight for remaining max(dx, dy) - min(dx, dy) distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int points[][2], int size) {
    int totalTime = 0;
    for (int i = 1; i < size; i++) {
        int x1 = points[i-1][0], y1 = points[i-1][1];
        int x2 = points[i][0], y2 = points[i][1];
        int dx = abs_val(x2 - x1);
        int dy = abs_val(y2 - y1);
        // Minimum time is max of horizontal and vertical distances
        totalTime += max(dx, dy);
    }
    return totalTime;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse 2D array manually
    int points[1000][2];
    int size = 0;
    char *ptr = line + 1; // Skip first '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            points[size][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            points[size][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            size++;
        }
        ptr++;
    }
    
    int result = solution(points, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through n-1 consecutive point pairs

✓ Linear Growth

Space Complexity

O(1)

Only using variables to store distances and sum

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Distance Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler