Widest Vertical Area Between Two Points Containing No Points

Widest Vertical Area Between Two Points Containing No Points - Problem

Array Sorting Easy

Given n points on a 2D plane where points[i] = [xi, yi], return the widest vertical area between two points such that no points are inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

Input & Output

Example 1 — Basic Case

$ Input: points = [[8,7],[9,9],[7,4],[9,7]]

› Output: 1

💡 Note: X-coordinates are [8,9,7,9]. After sorting: [7,8,9,9]. Gaps between consecutive unique x-values: 8-7=1, 9-8=1. Maximum gap is 1.

Example 2 — Larger Gaps

$ Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]

› Output: 3

💡 Note: X-coordinates sorted: [1,3,5,8,9]. Gaps: 3-1=2, 5-3=2, 8-5=3, 9-8=1. Maximum gap is 3.

Example 3 — Minimum Case

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

› Output: 1

💡 Note: Only two points with x-coordinates [1,2]. The gap between them is 2-1=1.

Constraints

n == points.length
2 ≤ n ≤ 10⁵
points[i].length == 2
-10⁸ ≤ x_i, y_i ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Points

Points scattered on 2D plane: [[8,7],[9,9],[7,4],[9,7]]

Extract X-Coordinates

Only x-values matter: [8,9,7,9] → sorted: [7,8,9,9]

Find Maximum Gap

Consecutive gaps: 8-7=1, 9-8=1 → Maximum width = 1

Key Takeaway

🎯 Key Insight: Y-coordinates are irrelevant - only sort x-coordinates and find maximum consecutive gap

Asked in

a Amazon 15 G Google 12

The key insight is that y-coordinates don't matter for vertical areas - only x-coordinates determine the width. Best approach is to sort x-coordinates and find the maximum gap between consecutive unique values. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Find Maximum Gap	O(n log n)	O(n)	Sort points by x-coordinate, then find the maximum gap between consecutive x-values
Brute Force - Check All Pairs	O(n³)	O(1)	Check every pair of points to find the maximum gap with no points in between

Sort and Find Maximum Gap — Algorithm Steps

Step 1: Extract and sort all x-coordinates
Step 2: Remove duplicates to get unique x-values
Step 3: Find maximum difference between consecutive x-values

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract & Sort

Get x-coordinates: [8,15,22,26] → sorted: [8,15,22,26]

Calculate Gaps

Find differences: 15-8=7, 22-15=7, 26-22=4

Find Maximum

Maximum gap is 7 (occurs twice)

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int points[][2], int n) {
    // Extract x-coordinates and sort them
    int *xCoords = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        xCoords[i] = points[i][0];
    }
    qsort(xCoords, n, sizeof(int), compare);
    
    // Find maximum gap between consecutive x-coordinates
    int maxWidth = 0;
    for (int i = 1; i < n; i++) {
        if (xCoords[i] != xCoords[i-1]) {  // Skip duplicates
            int gap = xCoords[i] - xCoords[i-1];
            if (gap > maxWidth) {
                maxWidth = gap;
            }
        }
    }
    
    free(xCoords);
    return maxWidth;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[x,y],[x,y]...]
    int points[1000][2];
    int n = 0;
    
    char *ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            points[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            points[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ']'
            n++;
        }
        ptr++;
    }
    
    int result = solution(points, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the x-coordinates dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Extra array to store x-coordinates for sorting

⚡ Linearithmic Space

25.0K 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

Sort and Find Maximum Gap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler