Domain 2MediumMEDIUM

Find the Start and End Number of Continuous Ranges

LeetCode problem 1285: Find the Start and End Number of Continuous Ranges (medium).

Domain: medium•Updated: 2026-09-14
#Algorithms

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:

  1. Ordering: The input data is likely unsorted (common with SQL tables). Sorting is required to detect continuity efficiently (O(Nlog⁡N)O(N \log N) vs O(N2)O(N^2) naive checks).
  2. 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”).
  3. Empty Input: Must return an empty list if no numbers exist.
  4. 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 (O(N2)O(N^2)), 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:

  1. Sort the input numbers to linearize them spatially (O(Nlog⁡N)O(N \log N)).
  2. Iterate through the sorted list once, maintaining a start pointer for the current sequence.
  3. When we encounter a gap (difference > 1), finalize the previous range and reset start.

Approach

  1. 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.
  2. Iteration: Initialize variables for current_start (the beginning of a potential range) and iterate through each number.
  3. 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 update current_start to the new number.
  4. Finalization: After the loop finishes, append the last active range (since it won’t trigger an internal break).

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N) due to sorting. The subsequent iteration is O(N)O(N). Sorting dominates. If input is pre-sorted, this drops to O(N)O(N).
  • Space Complexity: O(1)O(1) 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.