Problem

Given an array of integers, return the largest range, inclusive, of integers that are all included in the array.

For example, given the array [9, 6, 1, 3, 8, 10, 12, 11], return (8, 12) since 8, 9, 10, 11, and 12 are all in the array.

Examples

Example 1

1
2
3

Input: [9, 6, 1, 3, 8, 10, 12, 11]
Output: (8, 12)
Explanation: The largest consecutive range is 8, 9, 10, 11, 12.

Example 2

1
2
3

Input: [5, 2, 99, 3, 4, 1, 100]
Output: (1, 5)
Explanation: The largest consecutive range is 1, 2, 3, 4, 5.

Example 3

1
2
3

Input: [100, 4, 200, 1, 3, 2]
Output: (1, 4)
Explanation: The largest consecutive range is 1, 2, 3, 4.

Example 4

1
2
3

Input: [10]
Output: (10, 10)
Explanation: Only one number, so the range is (10, 10).

Example 5

1
2
3

Input: []
Output: None
Explanation: No numbers, so no range exists.

Solution

Method 1 – Hash Set Expansion

Intuition

The key idea is to use a set for O(1) lookups. For each number, expand left and right to find the full consecutive range, marking numbers as visited to avoid redundant work.

Approach

  1. Put all numbers in a set for fast lookup.
  2. For each number, if not visited, expand left and right to find the full range.
  3. Mark each number in the range as visited.
  4. Track the largest range found.
  5. Return the largest range as a tuple.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    pair<int, int> largestRange(vector<int>& arr) {
        unordered_set<int> s(arr.begin(), arr.end());
        unordered_set<int> visited;
        int maxLen = 0, ansL = 0, ansR = 0;
        for (int num : arr) {
            if (visited.count(num)) continue;
            int l = num, r = num;
            while (s.count(l-1)) l--;
            while (s.count(r+1)) r++;
            for (int i = l; i <= r; ++i) visited.insert(i);
            if (r-l+1 > maxLen) {
                maxLen = r-l+1;
                ansL = l; ansR = r;
            }
        }
        return maxLen ? make_pair(ansL, ansR) : make_pair(0, 0);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func LargestRange(arr []int) (int, int) {
    s := make(map[int]struct{}, len(arr))
    for _, num := range arr { s[num] = struct{}{} }
    visited := make(map[int]struct{})
    maxLen, ansL, ansR := 0, 0, 0
    for _, num := range arr {
        if _, ok := visited[num]; ok { continue }
        l, r := num, num
        for { _, ok := s[l-1]; if !ok { break }; l-- }
        for { _, ok := s[r+1]; if !ok { break }; r++ }
        for i := l; i <= r; i++ { visited[i] = struct{}{} }
        if r-l+1 > maxLen {
            maxLen = r-l+1; ansL = l; ansR = r
        }
    }
    if maxLen == 0 { return 0, 0 }
    return ansL, ansR
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int[] largestRange(int[] arr) {
        Set<Integer> s = new HashSet<>();
        for (int num : arr) s.add(num);
        Set<Integer> visited = new HashSet<>();
        int maxLen = 0, ansL = 0, ansR = 0;
        for (int num : arr) {
            if (visited.contains(num)) continue;
            int l = num, r = num;
            while (s.contains(l-1)) l--;
            while (s.contains(r+1)) r++;
            for (int i = l; i <= r; i++) visited.add(i);
            if (r-l+1 > maxLen) {
                maxLen = r-l+1; ansL = l; ansR = r;
            }
        }
        return maxLen == 0 ? null : new int[]{ansL, ansR};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def largest_range(self, arr: list[int]) -> tuple[int, int] | None:
        s = set(arr)
        visited = set()
        max_len, ans_l, ans_r = 0, 0, 0
        for num in arr:
            if num in visited:
                continue
            l, r = num, num
            while l-1 in s:
                l -= 1
            while r+1 in s:
                r += 1
            for i in range(l, r+1):
                visited.add(i)
            if r-l+1 > max_len:
                max_len = r-l+1
                ans_l, ans_r = l, r
        return (ans_l, ans_r) if max_len else None

Complexity

  • ⏰ Time complexity: O(n)
    • Each number is visited at most once, and set lookups are O(1).
  • 🧺 Space complexity: O(n)
    • Sets for input and visited numbers.