Points That Intersect With Cars - Practice Coding Problems

Points That Intersect With Cars - Problem

You are given a 0-indexed 2D integer array nums representing the coordinates of cars parking on a number line. For any index i, nums[i] = [start_i, end_i] where start_i is the starting point of the i^th car and end_i is the ending point of the i^th car.

Return the number of integer points on the line that are covered with any part of a car.

Input & Output

Example 1 — Basic Overlapping Cars

$ Input: nums = [[3,6],[1,5],[4,7]]

› Output: 7

💡 Note: Cars cover points: [3,6] covers 3,4,5,6; [1,5] covers 1,2,3,4,5; [4,7] covers 4,5,6,7. Combined unique points: 1,2,3,4,5,6,7 = 7 total points.

Example 2 — Non-overlapping Cars

$ Input: nums = [[1,3],[5,8]]

› Output: 7

💡 Note: Car [1,3] covers points 1,2,3 (3 points). Car [5,8] covers points 5,6,7,8 (4 points). No overlap, so total is 3 + 4 = 7 points.

Example 3 — Single Car

$ Input: nums = [[2,5]]

› Output: 4

💡 Note: Only one car covering points 2,3,4,5, which gives us 4 integer points total.

Constraints

1 ≤ nums.length ≤ 100
nums[i].length == 2
1 ≤ start_i ≤ end_i ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Cars positioned as intervals on number line

Coverage

Each car covers all integer points in its range

Count

Total unique integer points covered

Key Takeaway

🎯 Key Insight: Each car covers all integer points from start to end inclusive, use set to handle overlaps automatically

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is that each car covers all integer points from start to end inclusive, and we need to count unique covered points. The hash set approach is most intuitive - collect all covered points and return set size. For optimization, merge intervals eliminates redundant counting. Time: O(n×k) for hash set, O(n log n) for merge intervals, Space: O(p) where p is unique points covered.

Common Approaches

Approach	Time	Space	Notes
✓ Merge Intervals Approach	O(n log n)	O(1)	Sort intervals, merge overlapping ones, then count points in merged intervals
Hash Set - Track Unique Points	O(n × k)	O(p)	Use a set to collect all covered points and return its size
Brute Force - Check All Points	O(n × r)	O(1)	Find min/max range and check if each point is covered by any car

Merge Intervals Approach — Algorithm Steps

Sort intervals by start position
Merge overlapping intervals
Sum the length of each merged interval

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort intervals by start position

Merge

Combine overlapping intervals

Sum

Add up lengths of merged intervals

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    int* arr1 = (int*)a;
    int* arr2 = (int*)b;
    return arr1[0] - arr2[0];
}

int solution(int nums[][2], int numCars) {
    if (numCars == 0) return 0;
    
    // Sort intervals by start position
    qsort(nums, numCars, sizeof(int[2]), compare);
    
    int count = 0;
    int currentStart = nums[0][0];
    int currentEnd = nums[0][1];
    
    for (int i = 1; i < numCars; i++) {
        int start = nums[i][0];
        int end = nums[i][1];
        
        if (start <= currentEnd + 1) { // Can merge (including adjacent)
            if (end > currentEnd) currentEnd = end;
        } else {
            // Add count for current merged interval
            count += currentEnd - currentStart + 1;
            currentStart = start;
            currentEnd = end;
        }
    }
    
    // Add count for the last interval
    count += currentEnd - currentStart + 1;
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), merging takes O(n), so overall O(n log n)

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables, sorting is done in-place or with O(log n) stack space

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

384 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

Merge Intervals Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler