Largest Range

Tags

Largest Range

Category

Arrays

Difficulty

Hard

Problem Statement

Given an array of integers, find the longest range of consecutive integers contained in the array. A range [a, b] means every integer from a to b (inclusive) is present in the array. Return the range as a two-element array [start, end]. The integers do not need to be adjacent or sorted in the original array.

Intuition

Sorting the array and scanning for consecutive runs would work in O(n log n). To achieve O(n), we use a hash set. The crucial insight is: for each number, we can expand outward (both left and right) to find the full range it belongs to. By marking numbers as "visited" during expansion, we ensure each number is processed at most once across all expansions, keeping total work linear.

Approach

  1. Insert all numbers into a hash map with value true (unvisited).
  2. Initialize variables to track the best range found.
  3. For each number in the array: a. If already visited, skip it. b. Mark it as visited. c. Expand left: decrement from the current number, marking each found number as visited. d. Expand right: increment from the current number, marking each found number as visited. e. Compute the length of this range. If it exceeds the current best, update the best range.
  4. Return the best range.

Pseudocode

function largestRange(array):
    nums = {}
    for num in array:
        nums[num] = true

    bestRange = []
    longestLength = 0

    for num in array:
        if nums[num] == false:
            continue
        nums[num] = false
        currentLength = 1
        left = num - 1
        right = num + 1

        while left in nums:
            nums[left] = false
            currentLength++
            left--

        while right in nums:
            nums[right] = false
            currentLength++
            right++

        if currentLength > longestLength:
            longestLength = currentLength
            bestRange = [left + 1, right - 1]

    return bestRange

Time & Space Complexity

  • Time: O(n) — Each number is inserted into the hash map once and visited/expanded at most once. All expansions combined visit each element at most once.
  • Space: O(n) — For the hash map storing all numbers.

Key Insights

  • The visited flag is essential for achieving O(n). Without it, we could re-expand the same range from different starting points, degrading to O(n^2).
  • After expansion, left is one less than the range start and right is one more than the range end, so the range is [left + 1, right - 1].
  • The array does not need to be sorted. The hash map gives us O(1) lookups to check membership.

Edge Cases

  • Single-element array: the range is [element, element].
  • All elements are the same: the range has length 1.
  • All elements are consecutive: the range spans the entire array.
  • Negative numbers: handled naturally by the hash map.
  • Duplicate values in the array: they do not affect the range since the hash map stores unique keys.

Linked mentions