LeetCode 2848 - Points That Intersect With Cars

LeetCode Problem 2848

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine how many integer points on a number line are covered by at least one car. Each car is represented as a range [starti, endi] of integers, inclusive. For example, a car [3,6] covers the points 3, 4, 5, and 6. The input nums is a 2D array of these ranges, and we need to count the unique integer points that intersect with any car.

The constraints indicate that the number of cars is small (1 <= nums.length <= 100) and the coordinates are bounded (1 <= starti <= endi <= 100). This small bounded range allows us to use simple array-based techniques without worrying about efficiency issues for very large numbers.

Important edge cases include overlapping ranges, consecutive ranges, and single-point cars (where starti == endi). The problem guarantees all ranges are valid (start is never greater than end) and all coordinates are positive integers.

Approaches

The brute-force approach would be to iterate through every car and mark every point between starti and endi in a set or array to ensure uniqueness. This guarantees correctness because each integer point is explicitly counted if it falls within a car range. Given the small constraints, this approach is feasible, but we can optimize by using a fixed-size boolean array for marking points.

The optimal approach leverages the fact that the coordinates are bounded by 100. We can create a boolean array of size 101 (to handle index 1 to 100) and simply mark each integer covered by any car. Finally, we count the True values. This avoids the overhead of dynamic data structures like sets and provides a direct, fast solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(k)	n is number of cars, k is the max range length, uses set to store points
Optimal	O(n * k)	O(101)	Uses fixed boolean array for points 1 to 100, direct counting

Algorithm Walkthrough

1. Initialize a boolean array covered of size 101 to False. Each index i represents whether integer i is covered by any car.
2. Iterate through each car range [starti, endi] in nums.
3. For each range, mark all points from starti to endi as True in the covered array.
4. After processing all cars, count the number of True values in covered. This gives the total number of integer points intersecting at least one car.
5. Return the count.

Why it works: The boolean array ensures that each integer point is counted only once, even if it appears in multiple overlapping car ranges. By iterating through all ranges and marking points, we guarantee that every point covered by any car is counted exactly once.

Python Solution

from typing import List

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        covered = [False] * 101  # Boolean array for points 1 to 100
        for start, end in nums:
            for point in range(start, end + 1):
                covered[point] = True
        return sum(covered[1:])  # Ignore index 0 since points start from 1

This Python implementation initializes a fixed-size boolean array and iterates through each car range. Each point in the range is marked as True. Finally, we sum the array from index 1 onward to count the total covered points.

Go Solution

func numberOfPoints(nums [][]int) int {
    covered := [101]bool{} // Boolean array for points 1 to 100
    for _, car := range nums {
        start, end := car[0], car[1]
        for i := start; i <= end; i++ {
            covered[i] = true
        }
    }
    count := 0
    for i := 1; i <= 100; i++ {
        if covered[i] {
            count++
        }
    }
    return count
}

The Go implementation mirrors the Python version. We use a fixed-size array for booleans, loop over each car's range, and mark the points. The final sum is computed by iterating through indices 1 to 100.

Worked Examples

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

Boolean array updates:

Step	Range	Covered Points After Step
1	[3,6]	3,4,5,6
2	[1,5]	1,2,3,4,5,6
3	[4,7]	1,2,3,4,5,6,7

Count of True = 7

Example 2: nums = [[1,3],[5,8]]

Step	Range	Covered Points After Step
1	[1,3]	1,2,3
2	[5,8]	1,2,3,5,6,7,8

Count of True = 7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * k)	n is number of cars, k is max car length (<=100). Each point in each range is visited once.
Space	O(101)	Fixed boolean array size to cover points 1-100, independent of input size.

The bounded range ensures this is efficient, as even the worst case (100 cars covering 100 points each) is manageable.

Test Cases

# Provided examples
assert Solution().numberOfPoints([[3,6],[1,5],[4,7]]) == 7  # overlapping ranges
assert Solution().numberOfPoints([[1,3],[5,8]]) == 7  # non-overlapping ranges

# Boundary cases
assert Solution().numberOfPoints([[1,1]]) == 1  # single point car
assert Solution().numberOfPoints([[1,100]]) == 100  # full range coverage
assert Solution().numberOfPoints([[1,2],[2,3],[3,4]]) == 4  # consecutive overlapping ranges

# Stress case with maximum constraints
assert Solution().numberOfPoints([[i,i] for i in range(1,101)]) == 100  # all single-point cars

Test	Why
[[3,6],[1,5],[4,7]]	Checks overlapping ranges
[[1,3],[5,8]]	Checks non-overlapping ranges
[[1,1]]	Single-point coverage
[[1,100]]	Maximal single range coverage
[[1,2],[2,3],[3,4]]	Consecutive overlapping ranges
[[i,i] for i in range(1,101)]	Maximum number of single-point cars

Edge Cases

Single-point car: When starti == endi, the car covers exactly one point. Our solution correctly marks that point in the boolean array.

Overlapping ranges: When ranges overlap, multiple cars may cover the same integer points. The boolean array ensures that points are only counted once, avoiding double-counting.

Maximal range coverage: A car covering the entire line from 1 to 100 tests whether the implementation correctly handles full coverage. The solution efficiently counts all points without iterating redundantly because each point is only marked once in the boolean array.