Points That Intersect With Cars

Points That Intersect With Cars

What is this problem about?

The Points That Intersect With Cars problem gives you a list of car intervals [start, end] on a number line. Find how many integer points are covered by at least one car. This easy coding problem uses a difference array or a set union. The array, hash table, and prefix sum interview pattern is demonstrated.

Why is this asked in interviews?

Uber asks this to test interval coverage on a number line. The difference array approach (mark +1 at start, -1 at end+1) efficiently counts coverage. Alternatively, a set of all covered integers works for small ranges.

Algorithmic pattern used

Difference array or direct set. Difference array: for each [l, r], increment diff[l] by 1 and decrement diff[r+1] by 1. Compute prefix sum; count positions with prefix sum > 0.

Simpler for small ranges: add all integers in [l, r] to a set. Return set size.

Example explanation

cars=[[3,6],[1,5],[4,7]]. Covered integers: 1,2,3,4,5,6,7 = {1,2,3,4,5,6,7} (from unions). Count = 7.

Using difference array: diff[1]+=1, diff[6]+=1... accumulate and count positives.

Common mistakes candidates make

• Double-counting overlapping intervals.
• Using a list with duplicates instead of a set.
• Off-by-one in difference array: decrement at r+1, not r.
• Not handling very large coordinate ranges (use hash map instead of array).

Interview preparation tip

Interval coverage counting problems have two clean solutions: (1) difference array for range [min..max] coverage, (2) set of covered integers for sparse ranges. The difference array is O(n + range_size), the set approach is O(n * interval_length). For interviews, describe both and choose based on coordinate ranges. Practice: "count points covered by at least k intervals," "find uncovered intervals." Both use difference arrays.