228.summary-ranges.md

228. Summary Ranges

Hints

• Try to scan the array and keep track of the start and end of each consecutive range.
• What should you do when you find a gap between numbers?

Breakdowns

1. How do you identify the start and end of a consecutive range?

Keep a pointer to the start of the current range. When the next number is not consecutive, close the current range and start a new one.

1, 2, 3, _, 5, 6, _, 7, 8, 9, 10
|-----|     |--|     |---------|
s --> e     s  e     s ------> e

2. How do you format the output for single numbers vs. ranges?

If the start and end are the same, output just the number. Otherwise, output in the format start->end.

Two Pointers

We can use the approach of "group by consecutive" to solve this problem. This approach is to to iterate through the array, tracking the start of each range, then extend the range until the next number is not consecutive, and add the range to the result.

fun summaryRanges(nums: IntArray): List<String> {
    val n = nums.size
    val ranges = mutableListOf<String>()
    var i = 0
    while (i < n) {
        val start = nums[i]
        // i will stop at the end of the range when breaking the loop
        while (i + 1 < n && nums[i] + 1 == nums[i + 1]) i++
        val end = nums[i]
        if (start == end) {
            ranges.add("$start")
        } else {
            ranges.add("$start->$end")
        }
        i++
    }
    return ranges
}

// 靈神樣板
fun summaryRanges(nums: IntArray): List<String> {
    val n = nums.size
    val ranges = mutableListOf<String>()
    var i = 0
    while (i < n) {
        val start = nums[i]
        i++
        // i will stop at the start of the next range
        while (i < n && nums[i - 1] + 1 == nums[i]) {
            i++
        }
        val end = nums[i - 1]
        if (start == end) {
            ranges.add("$start")
        } else {
            ranges.add("$start->$end")
        }
    }
    return ranges
}

• Time Complexity: O(N) where N is the length of nums.
• Space Complexity: O(1) (excluding output list).

Edge Cases

• Array with only one number: should return a single-element list.
• All numbers are consecutive: should return one range.
• No consecutive numbers: should return each number as its own range.
• Large gaps at the start or end: ensure the first and last elements are handled.

Pitfalls

• Forgetting to add the last range after the loop.
• Off-by-one errors when checking the end of a range.
• Not handling single-element ranges correctly.