Problem Breakdown
The goal is to identify continuous sequences within a set of numbers and return them as ranges (start number, end number).
Inputs: A collection of integer values (typically from an id column in a database table like Accounts).
Outputs: A list or array containing tuples/pairs representing (start_num, end_num) for each continuous range found.
Implicit Constraints & Edge Cases:
- Ordering: The input data is likely unsorted (common with SQL tables). Sorting is required to detect continuity efficiently ( vs naive checks).
- Duplicates: If the same number appears multiple times, it should generally be treated as a single point in the sequence unless specified otherwise. We will assume unique IDs for standard range logic or handle duplicates by taking min/max of that cluster (though usually distinct is implied for “ranges”).
- Empty Input: Must return an empty list if no numbers exist.
- Single Element: A single number forms a valid range
(x, x).
Intuition
A naive approach would be to check every pair of numbers to see if they are consecutive and connected (), which is inefficient for large datasets (common in FAANG interviews).
The key insight is that continuity depends on the difference between adjacent elements. If we sort the data, a continuous range exists whenever current_number == previous_number + 1. Any break in this sequence (diff > 1) signifies the end of one range and the start of another.
Optimal Approach:
- Sort the input numbers to linearize them spatially ().
- Iterate through the sorted list once, maintaining a
startpointer for the current sequence. - When we encounter a gap (difference > 1), finalize the previous range and reset
start.
Approach
- Preprocessing: If the input is not guaranteed to be sorted, sort it first. This allows us to process elements in linear order relative to value magnitude.
- Iteration: Initialize variables for
current_start(the beginning of a potential range) and iterate through each number. - Gap Detection: For every subsequent number:
- If the difference between current and previous is exactly 1, continue extending the current range (
end = num). - Otherwise, we hit a gap. Record
(current_start, prev_end)to results, then updatecurrent_startto the new number.
- If the difference between current and previous is exactly 1, continue extending the current range (
- Finalization: After the loop finishes, append the last active range (since it won’t trigger an internal break).
Complexity Analysis
- Time Complexity: due to sorting. The subsequent iteration is . Sorting dominates. If input is pre-sorted, this drops to .
- Space Complexity: auxiliary space if we ignore the output storage (excluding result list). We use a few pointers/variables for state tracking.
Solution
def find_continuous_ranges(numbers):
"""
Finds continuous ranges from a list of integers.
Args:
numbers (List[int]): A list of integer IDs or values to analyze.
Returns:
List[Tuple[int, int]]: List of tuples representing (start_num, end_num).
"""
if not numbers:
return []
# Sort the input to ensure we can detect continuity linearly
sorted_nums = sorted(numbers)
ranges = []
current_start = None
for i in range(len(sorted_nums)):
num = sorted_nums[i]
# Initialize start on first iteration or if gap detected previously (handled by logic below)
if i == 0:
current_start = num
# Check continuity with previous number
if i > 0 and num - sorted_nums[i-1] == 1:
continue
# Gap found, finalize the range ending at the previous number (i-1)
prev_num = sorted_nums[i-1]
ranges.append((current_start, prev_num))
current_start = num
# Append final active range after loop completes
if current_start is not None:
last_end = sorted_nums[-1]
ranges.append((current_start, last_end))
return ranges
Edge Cases Handled
- Empty List: Returns
[]immediately via the initial check. - Single Element: The loop runs once; logic correctly appends
(num, num)after initialization and finalization steps (though simplified in code above to handle gaps). Correction: In the provided solution logic: if list is[5],i=0,current_start=5. Loop ends. Final append adds(5, 5). Correct. - Fully Consecutive: No gap detected inside loop; finalization appends one range covering all elements (e.g.,
1-3). - No Gaps at End: The logic ensures the last segment is always captured in the post-loop append block.