How to Solve Points That Intersect With Cars

For Points That Intersect With Cars, the goal is to count how many integer positions are covered by at least one closed interval. Because every car covers all points from start to end, the clean solution is either to mark each covered point with a lookup structure or sort and merge overlaps before summing lengths. The main trap is double-counting points inside overlapping ranges.

Problem Statement

You get a 0-indexed array nums where each entry is a car segment on a number line. For each nums[i] = [starti, endi], that car covers every integer point from starti through endi, inclusive.

Return how many distinct integer points are covered by at least one car. In the sample nums = [[3,6],[1,5],[4,7]], the covered points run continuously from 1 through 7, so the answer is 7. In nums = [[1,3],[5,8]], the covered points are 1, 2, 3, 5, 6, 7, and 8, which also gives 7.

Examples

Example 1

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

Output: 7

All the points from 1 to 7 intersect at least one car, therefore the answer would be 7.

Example 2

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

Output: 7

Points intersecting at least one car are 1, 2, 3, 5, 6, 7, 8. There are a total of 7 points, therefore the answer would be 7.

Constraints

• 1 <= nums.length <= 100
• nums[i].length == 2
• 1 <= starti <= endi <= 100

Solution Approach

Direct marking with a hash set or boolean array

Because each start and end value is at most 100, you can scan every interval and mark each covered integer point. A hash set fits the Array plus hash lookup pattern directly, while a fixed boolean array is even simpler here. After processing all cars, count how many positions were marked true. This avoids overlap logic entirely, which makes it the safest Easy-level solution.

Sort and merge overlapping intervals

If you want the interval-based interview route, sort nums by start value, then walk from left to right and merge any range whose start is at most the current merged end. Each time a gap appears, add the finished merged segment length as end - start + 1 and start a new segment. This matches the hint about sorting and removing overlap, and it prevents counting the same covered points twice.

Prefix sum over the number line

Since coordinates are small, you can also use a difference array. Add 1 at starti and subtract 1 at endi + 1, then build a prefix sum across the line. Every index with running sum greater than 0 is covered by at least one car. This connects the problem to Prefix Sum and is useful when you want to count covered points without touching every interval position separately in larger coordinate settings.

Complexity Analysis

The marking solution runs in O(n * L) time, where L is the average interval length, and uses O(U) space for the covered positions, with U at most 100 here. The sort-and-merge solution runs in O(n log n) time for sorting and O(1) or O(n) extra space depending on implementation. The prefix sum method runs in O(n + U) time and O(U) space, which is very efficient in this problem because the coordinate range is tiny.

What Interviewers Usually Probe

• The small coordinate bound up to 100 is a strong signal that brute-force marking each integer point is fully acceptable.
• If the interviewer mentions overlap removal or sorting by the first element, they are steering toward interval merging.
• If they ask for a cleaner counting trick instead of repeated point insertion, they may want the Prefix Sum difference-array version.

Common Pitfalls or Variants

Common pitfalls

• Forgetting that intervals are inclusive causes off-by-one errors, especially when computing merged length as end - start + 1.
• Double-counting overlap happens when you sum each car length independently instead of merging or deduplicating points.
• Using endi + 1 in the prefix method without allocating enough space can break the last update boundary.

Follow-up variants

• Return the actual covered points instead of only the count, which favors the marking approach.
• Increase coordinate bounds dramatically, which makes sort-and-merge more practical than point-by-point scanning.
• Ask how many points are covered by at least k cars, which turns the Prefix Sum running count into the key extension.

How GhostInterview Helps

• GhostInterview identifies that Points That Intersect With Cars is really an inclusive-interval counting problem, so it avoids unnecessary heavy logic.
• GhostInterview shows when the small bound makes hash lookup or boolean marking the fastest correct choice for this exact problem.
• GhostInterview compares marking, merging, and prefix sum so you can pick the right trade-off without double-counting overlaps.

Topic Pages

• Array
• Hash Table
• Prefix Sum

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the easiest way to solve Points That Intersect With Cars?

The easiest solution is to mark every integer point covered by each car using a boolean array or hash set, then count the marked positions. It works especially well because all coordinates are between 1 and 100.

Why does interval merging work for this problem?

Merging works because overlapping car ranges cover one continuous block of integer points. After sorting by start, you can combine overlaps and add each merged block length once, which avoids double-counting.

Is prefix sum overkill for this problem?

It is not necessary for the given limits, but it is still a valid and neat approach. It becomes more interesting when you want to count coverage from many intervals or extend the task to coverage frequency.

What is the main failure mode in this pattern?

The main failure mode is double-counting points that belong to multiple overlapping cars. Another common mistake is forgetting that both start and end are included in the covered segment.

How does the array scanning plus hash lookup pattern apply here?

You scan each interval in nums and insert every covered integer point into a set, or mark it in a boolean array. The lookup structure guarantees each point is counted once even when intervals overlap heavily.