Summary Ranges

📋

Summary Ranges

Edge cases:

</>

IDE

def summaryRanges(nums: list[int]) -> list[str]:public List<String> summaryRanges(int[] nums)vector<string> summaryRanges(vector<int> &nums)function summaryRanges(nums)

def summaryRanges(nums: list[int]) -> list[str]:
    # Write your solution here
    pass

class Solution {
    public List<String> summaryRanges(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> summaryRanges(vector<int> &nums) {
    // Write your solution here
    return {};
}

function summaryRanges(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ["0->1","2","4->5","7"]Fails to merge all consecutive numbers into one range; stops range too early.✅ Extend range while next number equals current + 1 before outputting range.

Wrong: ["0","1","2","4","5","7"]Treats every number as single element; does not detect consecutive sequences.✅ Implement logic to track start and end of consecutive sequences and output ranges accordingly.

Wrong: ["5->5"]Outputs range format even for single elements.✅ Check if start == end; if so, output just the number as string without arrow.

Wrong: ["-3","-2","-1","0","2->4","6"]Fails to merge negative consecutive numbers into ranges.✅ Use numeric comparisons without sign assumptions to detect consecutive sequences.

Wrong: Solution uses nested loops causing timeout on large input.✅ Use single pass linear scan to achieve O(n) time complexity.

✓

Test Cases

Try testing your code on empty and single-element arrays to handle base cases.

Consider negative numbers and non-consecutive elements to catch subtle bugs.

Optimize your solution to run in linear time for large inputs.

t1_01basic

Input{"nums":[0,1,2,4,5,7]}

Expected["0->2","4->5","7"]

⏱ Performance - must finish in 2000ms

The numbers 0,1,2 form a consecutive range, 4,5 form another, and 7 stands alone.

💡 Look for consecutive sequences by comparing adjacent numbers.

💡 Track the start of each range and extend it while numbers are consecutive.

💡 When a break in sequence occurs, record the range and start a new one.

Why it failed: Output missing or incorrect ranges; likely not tracking range boundaries properly. Fix by updating range end only when consecutive and output range when sequence breaks.

✓ Correctly identifies and outputs all consecutive ranges.

t1_02basic

Input{"nums":[1,3,4,5,7,8,10]}

Expected["1","3->5","7->8","10"]

⏱ Performance - must finish in 2000ms

Single element 1, ranges 3-5 and 7-8, and single element 10.

💡 Check each pair of adjacent numbers for consecutive increments.

💡 Use a pointer to mark the start of each range and extend it while consecutive.

💡 Output single numbers as strings and ranges as 'start->end'.

Why it failed: Fails to separate single elements from ranges or merges non-consecutive numbers. Fix by checking if start equals end before formatting output.

✓ Properly distinguishes single elements and consecutive ranges.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array should return empty list.

💡 Consider what happens when input array is empty.

💡 Your code should handle zero-length input without errors.

💡 Return an empty list immediately if input is empty.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a check for empty input at start.

✓ Handles empty input gracefully by returning empty list.

t2_02edge

Input{"nums":[5]}

Expected["5"]

⏱ Performance - must finish in 2000ms

Single element array outputs that element as a string.

💡 Check how your code handles arrays with only one element.

💡 Single elements should be output as strings without arrows.

💡 Ensure no range extension logic breaks with single element.

Why it failed: Outputs empty or incorrect range for single element. Fix by handling single element case explicitly or via general logic.

✓ Correctly outputs single element as string.

t2_03edge

Input{"nums":[1,2,3,4,5]}

Expected["1->5"]

⏱ Performance - must finish in 2000ms

All elements consecutive form one big range.

💡 Test if your code can handle a single continuous range covering all elements.

💡 Make sure the range extends to the last element without premature termination.

💡 Output should be 'start->end' when start != end.

Why it failed: Stops range early or outputs multiple ranges instead of one. Fix by continuing range until no longer consecutive or end of array.

✓ Correctly outputs one continuous range for all consecutive elements.

t2_04edge

Input{"nums":[10,20,30,40]}

Expected["10","20","30","40"]

⏱ Performance - must finish in 2000ms

No consecutive elements; all single-element ranges.

💡 Check if your code handles arrays with no consecutive numbers.

💡 Each element should be output as a single string.

💡 Avoid merging non-consecutive numbers into ranges.

Why it failed: Merges non-consecutive numbers into ranges. Fix by checking if next number is exactly current + 1 before extending range.

✓ Correctly outputs all single-element ranges when no consecutive numbers.

t3_01corner

Input{"nums":[-3,-2,-1,0,2,3,4,6]}

Expected["-3->0","2->4","6"]

⏱ Performance - must finish in 2000ms

Negative and positive numbers with multiple ranges.

💡 Check if your code handles negative numbers correctly.

💡 Consecutive detection should work regardless of sign.

💡 Ensure range boundaries are tracked properly across negative to positive.

Why it failed: Fails to handle negative numbers or breaks ranges incorrectly. Fix by using numeric comparisons without sign assumptions.

✓ Correctly handles negative and positive numbers in ranges.

t3_02corner

Input{"nums":[1,3,5,7,9]}

Expected["1","3","5","7","9"]

⏱ Performance - must finish in 2000ms

No consecutive elements; all single-element ranges.

💡 Test if your code can handle no consecutive numbers.

💡 Each element should be output as a single string.

💡 Avoid merging non-consecutive numbers into ranges.

Why it failed: Merges non-consecutive numbers into ranges. Fix by checking if next number is exactly current + 1 before extending range.

✓ Correctly outputs all single-element ranges when no consecutive numbers.

t3_03corner

Input{"nums":[0,1,2,4,5,6,8,9,10,12]}

Expected["0->2","4->6","8->10","12"]

⏱ Performance - must finish in 2000ms

Multiple consecutive ranges separated by gaps.

💡 Check if your code correctly starts new ranges after gaps.

💡 Ensure no off-by-one errors in range boundaries.

💡 Verify that ranges are output immediately after sequence breaks.

Why it failed: Off-by-one errors cause incorrect range ends or starts. Fix by careful index and value checks when detecting breaks.

✓ Correctly outputs multiple ranges separated by gaps.

t4_01performance

Input{"nums":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=200; solution must run in O(n) time within 2 seconds.

💡 Use a single pass linear scan to detect ranges efficiently.

💡 Avoid nested loops or repeated scanning of the array.

💡 Track start and end indices and output ranges once per sequence.

Why it failed: Brute force or nested loops cause TLE on large input. Fix by implementing single pass linear scan with O(n) complexity.

✓ Solution runs in O(n) time and handles large input efficiently.

Practice

1. Given the following Python code implementing the optimal approach for longest consecutive sequence, what is the value of max_len returned when the input is [1, 9, 3, 10, 4, 20, 2]?

def longestConsecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in num_set:
        if num - 1 not in num_set:
            current = num
            length = 1
            while current + 1 in num_set:
                current += 1
                length += 1
            max_len = max(max_len, length)
    return max_len

easy

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Identify sequence starts

   Numbers without predecessor: 1 (0 not in set), 9 (8 not in set), 20 (19 not in set).

2. Step 2: Trace sequences from starts

   From 1: sequence is 1,2,3,4 -> length 4; from 9: 9,10 -> length 2; from 20: 20 -> length 1. Max length is 4.

3. Step 3: Re-examine carefully

   Check if 1,2,3,4 is the longest. Actually, 1,2,3,4 is length 4, but 1,2,3,4,5 is not present. So max length is 4.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Longest consecutive sequence length is 4 [OK]

Hint: Only count sequences starting at numbers without predecessor [OK]

Common Mistakes:

• Counting sequences from every number
• Off-by-one in length calculation
• Ignoring duplicates

2. What is the time complexity of the optimal hash map with prefix sum remainders approach for the Continuous Subarray Sum problem, assuming the input array length is n and the divisor is k?

medium

A. O(n * k) due to nested loops over array and modulo values

B. O(n^2) because of checking all subarrays implicitly via prefix sums

C. O(n) because each element is processed once and hash map operations are O(1) on average

D. O(k) since the remainder map size is limited by k

Solution

1. Step 1: Analyze the loop and hash map operations

   The algorithm iterates over the array once (O(n)) and performs O(1) average-time hash map lookups and insertions.

2. Step 2: Consider the size of the remainder map

   The remainder map size is at most min(n, k), but this does not increase the iteration count beyond O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with constant-time map ops -> O(n) time [OK]

Hint: Hash map lookups are O(1) average, so linear time [OK]

Common Mistakes:

• Confusing prefix sums with nested loops
• Assuming modulo k adds multiplicative factor
• Ignoring average O(1) hash map operations

3. Consider the following buggy code for finding the longest consecutive sequence. Which line contains the subtle bug that can cause incorrect results on inputs with duplicates?

def longestConsecutive(nums):
    num_set = set(nums)
    max_len = 0
    for num in nums:
        if num - 1 not in num_set:
            current = num
            length = 1
            while current + 1 in num_set:
                current += 1
                length += 1
            max_len = max(max_len, length)
    return max_len

medium

A. Line 9: Updating max_len inside the while loop instead of after.

B. Line 4: Checking if num - 1 not in num_set instead of nums.

C. Line 3: Using nums instead of num_set in the for loop.

D. Line 7: Incrementing current before checking if current + 1 is in num_set.

Solution

1. Step 1: Identify iteration source

   The for loop iterates over nums, which may contain duplicates, causing redundant sequence counting.

2. Step 2: Understand impact of duplicates

   Iterating over nums instead of num_set leads to repeated work and incorrect max_len updates, inflating counts.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing to iterate over num_set fixes duplicate handling [OK]

Hint: Iterate over unique elements to avoid duplicate counting [OK]

Common Mistakes:

• Iterating over original list with duplicates
• Updating max_len inside inner loop
• Incorrect boundary checks

4. Identify the bug in the following code snippet for the Minimum Operations to Reduce X to Zero problem:

medium

A. Line with 'if target == 0: return -1' should return len(nums) instead.

B. The while loop condition should be 'current_sum >= target' instead of '>'.

C. The initialization of max_len should be 0 instead of -1.

D. The final return should be 'max_len' instead of 'len(nums) - max_len'.

Solution

1. Step 1: Understand the edge case when target == 0

   If target == 0, it means totalSum == x, so removing all elements is needed, so minimum operations = length of array.

2. Step 2: Identify incorrect return value

   The code returns -1 incorrectly, which signals no solution, but the correct answer is to remove all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning -1 here causes wrong output on full removal case [OK]

Hint: Check edge cases where x equals total sum [OK]

Common Mistakes:

• Returning -1 instead of full length when target == 0
• Misinterpreting no solution vs full removal
• Ignoring edge cases in initial checks

5. Suppose the problem is modified so that the input array can contain duplicate numbers and you want to find the length of the longest consecutive sequence considering duplicates as separate elements (e.g., [1,2,2,3] counts as length 4). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Use a hash map to store counts of each number and sum counts for consecutive numbers to find the longest run.

B. Use the original hash set approach but multiply the length by the count of duplicates for each number.

C. Sort the array and count consecutive runs including duplicates by scanning linearly.

D. Ignore duplicates and apply the original hash set approach since duplicates don't affect sequence length.

Solution

1. Step 1: Understand the variant

   Duplicates count as separate elements, so sequences can include repeated numbers increasing length.

2. Step 2: Evaluate approaches

   Original hash set approach ignores duplicates; multiplying length by counts is incorrect because duplicates may be non-consecutive; sorting and scanning works but is O(n log n).

3. Step 3: Correct approach

   Using a hash map to store counts allows summing counts of consecutive numbers to find the longest run including duplicates efficiently.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map counting handles duplicates correctly and efficiently [OK]

Hint: Count duplicates explicitly using a hash map [OK]

Common Mistakes:

• Ignoring duplicates
• Multiplying length by counts incorrectly
• Assuming sorting is always best