Summary Ranges — Linear Scan Two-Pointer [LC 228]

Problem Statement#

Given a sorted unique integer array nums, return the smallest sorted list of ranges that cover all the numbers. A range [a, b] is represented as "a->b" if a != b, or "a" if a == b.

Constraints:

• 0 <= nums.length <= 20
• -2^31 <= nums[i] <= 2^31 - 1
• All values in nums are unique
• nums is sorted in ascending order

Input:  nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]

Input:  nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]

Why This Problem Matters#

LeetCode 228 is a common screening problem at Amazon, Google, and Microsoft. It tests the ability to implement a clean linear scan with boundary detection — a pattern that appears in many array manipulation tasks like run-length encoding, interval merging, and streak detection.

The problem is conceptually simple but trips candidates who overthink it. The implementation requires careful handling of the loop end: whether the current range terminates at each step or only when the run breaks. This is a great warm-up problem for interval-based reasoning.

The Core Insight#

Use two pointers start and i. Extend i while nums[i+1] == nums[i] + 1 (consecutive). When the run breaks (or we hit the end), record the range [start, i] and advance start to i + 1.

The only decision: is the range a single element or a span? If start == i, output just the number. Otherwise output "start->i".

Visual Dry Run#

nums = [0, 1, 2, 4, 5, 7]

Result: ["0->2", "4->5", "7"]

Solution (Optimal)#

class Solution:
    def summaryRanges(self, nums):
        result = []
        i = 0
        while i < len(nums):
            start = nums[i]
            while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
                i += 1
            if nums[i] == start:
                result.append(str(start))
            else:
                result.append(f"{start}->{nums[i]}")
            i += 1
        return result

var summaryRanges = function(nums) {
    const result = [];
    let i = 0;
    while (i < nums.length) {
        const start = nums[i];
        while (i + 1 < nums.length && nums[i + 1] === nums[i] + 1) {
            i++;
        }
        if (nums[i] === start) {
            result.push(String(start));
        } else {
            result.push(`${start}->${nums[i]}`);
        }
        i++;
    }
    return result;
};

Time: O(n) — each element visited exactly once Space: O(1) — output list aside, only scalar variables

Common Mistakes#

• Using for loop index and separate start pointer — causes off-by-one errors in the inner extension loop
• Checking nums[i] == nums[i-1] + 1 instead of nums[i+1] == nums[i] + 1 — boundary mismatch
• Forgetting to increment i after closing each range — causes infinite loop
• Not handling the single-element range case — when start == end, output just the number without ->
• Assuming the array is always non-empty — handle empty input (while loop never executes, returns empty list)

Interview Tips#

• State the algorithm in one sentence before coding: "extend while consecutive, cut when the run breaks, record range"
• Trace through the first example step by step showing when ranges close
• Clarify: is a single number formatted as "n" or "n->n"? (The problem says "n" — check constraints)
• Mention the output list isn't counted as extra space when analyzing space complexity
• Compare to run-length encoding — same "detect run breaks" pattern

Follow-up Questions#

• What if the array is not sorted? (Sort it first — O(n log n) total, but the linear scan still applies after sorting)
• What if there are duplicates? (The problem guarantees uniqueness — with duplicates, decide whether duplicates extend the range or are separate)
• How does this relate to Merge Intervals (LC 56)? (Both detect overlapping/adjacent spans; Summary Ranges is simpler because the input is already sorted and contains individual numbers)
• Can you solve it in a single pass without a nested inner while? (Yes — track start, advance i one at a time, close range when nums[i+1] != nums[i]+1)
• What if you need to output intervals as [start, end] instead of strings? (Remove the string formatting, return pairs directly)

Key Takeaways#

• LeetCode 228 is asked at Amazon, Google, and Microsoft — clean linear scan with run detection
• Two-pointer approach: start marks the beginning of a run, inner loop extends while consecutive
• When the run breaks, record "start->end" or "start" depending on whether start equals end
• Time O(n) — each element visited exactly once; Space O(1) auxiliary
• Empty array input is valid — the while loop handles it without any special case
• The "detect run breaks" pattern (extend while equal to prev+1) appears in run-length encoding, interval merging, and streak problems
• Single-element ranges output as "n" not "n->n" — verify this with the interviewer at the start