Check if All the Integers in a Range Are Covered

Check if All the Integers in a Range Are Covered

What is this problem about?

The "Check if All the Integers in a Range Are Covered interview question" is an interval-overlap problem. You are given a 2D array of ranges [[start1, end1], [start2, end2], ...] and two integers left and right. You need to determine if every integer in the inclusive range [left, right] is covered by at least one of the provided ranges.

Why is this asked in interviews?

Amazon and Bloomberg ask the "Check if All the Integers in a Range Are Covered coding problem" to test a candidate's ability to work with intervals and ranges. While it can be solved with a simple nested loop, it also offers opportunities to demonstrate more advanced "Prefix Sum interview pattern" or "Difference Array" techniques, which are useful for handling large sets of range updates efficiently.

Algorithmic pattern used

This problem can be solved with Simulation or a Difference Array.

1. Simulation (Brute Force): For every integer i from left to right, iterate through all given ranges. If i is found in any range, move to i+1. If any i is not found, return false.
2. Difference Array (Optimized):
   • Create an array diff of size 52 (assuming values up to 50).
   • For each range [s, e], increment diff[s] and decrement diff[e+1].
   • Compute the prefix sum of diff. If at any point from left to right, the prefix sum is 0, then that integer is not covered.

Example explanation

Ranges: [[1, 2], [3, 4], [5, 6]], left = 2, right = 5.

• Range [2, 5] includes: {2, 3, 4, 5}.
• 2 is covered by [1, 2].
• 3 is covered by [3, 4].
• 4 is covered by [3, 4].
• 5 is covered by [5, 6]. Result: True.

Common mistakes candidates make

• Boundary Errors: Not checking the inclusive nature of the ranges (e.g., start and end are both covered).
• Inefficient Looping: Using a triple-nested loop (loop through range, loop through left-right, loop through each range).
• Ignoring Scale: If the range were up to $10^9$ instead of 50, the difference array would require coordinate compression.

Interview preparation tip

Get comfortable with "Difference Arrays." They are the standard way to solve problems involving multiple range updates or queries. Understanding how prefix sums transform differences back into values is a vital "Array interview pattern."