LeetCode 163: Missing Ranges Solution in Python Explained

Problem Statement

In LeetCode 163, you’re given a sorted integer array nums (with unique elements), an inclusive lower bound lower, and an inclusive upper bound upper. Your task is to return a list of strings representing all missing ranges in [lower, upper] not present in nums. A range a->b is formatted as "a->b" if a != b, or "a" if a == b. This differs from peak finding like LeetCode 162: Find Peak Element, focusing on range identification rather than element selection.

Constraints

• 0 <= nums.length <= 100
• -10^9 <= nums[i] <= 10^9
• nums is sorted in ascending order with unique elements
• -10^9 <= lower <= upper <= 10^9

Example

Let’s see some cases:

Copy codeInput: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation:
<ul>
<li>0 to 1: Missing 2.</li>
<li>1 to 3: Missing 4 to 49.</li>
<li>3 to 50: Missing 51 to 74.</li>
<li>50 to 75: Missing 76 to 99.</li>
</ul>

Copy codeInput: nums = [], lower = 1, upper = 4
Output: ["1->4"]
Explanation: No numbers, entire range missing.

Copy codeInput: nums = [1,2,3], lower = 1, upper = 3
Output: []
Explanation: No gaps, all present.

These examples show we’re identifying missing ranges.

Understanding the Problem

How do you solve LeetCode 163: Missing Ranges in Python? Take nums = [0,1,3,50,75], lower = 0, upper = 99. We need to find gaps: 2, 4-49, 51-74, 76-99. For an empty array with lower=1, upper=4, the range "1->4" is missing. If nums covers [lower, upper], return an empty list. This isn’t a string edit task like LeetCode 161: One Edit Distance; it’s about array range analysis. We’ll use: 1. Linear Scan with Range Formatting: O(n) time, O(1) space (excluding output)—our best solution. 2. Two-Pointer with Range Building: O(n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Linear Scan with Range Formatting Approach

Explanation

Linear Scan with Range Formatting scans the array linearly, identifying gaps between consecutive elements and bounds:

• Start with prev = lower - 1 to handle the first range.
• Iterate through nums, using each element as the current end.
• Check gaps between prev + 1 and curr - 1, formatting ranges.
• After the loop, check the gap to upper.

This is the best solution due to its O(n) time complexity (n = array length), O(1) space usage (excluding output), and straightforward logic, making it efficient and clear.

For [0,1,3,50,75], lower=0, upper=99:

• Prev=-1 to 0: No gap.
• 0 to 1: Gap 2.
• 1 to 3: Gap 4-49.
• 3 to 50: Gap 51-74.
• 50 to 75: Gap 76-99.

Step-by-Step Example

Example 1: nums = [0,1,3,50,75], lower = 0, upper = 99

Goal: Return ["2","4->49","51->74","76->99"].

• Start: result = [], prev = lower - 1 = -1.
• Step 1: curr = 0.
• start = prev + 1 = 0, end = curr - 1 = -1, no range.
• prev = 0.
• Step 2: curr = 1.
• start = 1, end = 0, no range.
• prev = 1.
• Step 3: curr = 3.
• start = 2, end = 2, result = ["2"].
• prev = 3.
• Step 4: curr = 50.
• start = 4, end = 49, result = ["2","4->49"].
• prev = 50.
• Step 5: curr = 75.
• start = 51, end = 74, result = ["2","4->49","51->74"].
• prev = 75.
• Step 6: Check upper.
• start = 76, end = 99, result = ["2","4->49","51->74","76->99"].
• Finish: Return ["2","4->49","51->74","76->99"].

Example 2: nums = [], lower = 1, upper = 4

Goal: Return ["1->4"].

• Start: result = [], prev = 0.
• Step 1: No elements, check upper.
• start = 1, end = 4, result = ["1->4"].
• Finish: Return ["1->4"].

Example 3: nums = [1,2,3], lower = 1, upper = 3

Goal: Return [].

• Start: result = [], prev = 0.
• Steps: 1, 2, 3 match 1-3, no gaps.
• Finish: Return [].

How the Code Works (Linear Scan with Range Formatting) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef findMissingRanges(nums: list[int], lower: int, upper: int) -> list[str]:
    # Line 1: Initialize result and prev
    result = []
    # List of missing ranges (e.g., [])
    prev = lower - 1
    # Previous value (e.g., -1 for lower=0)

    # Line 2: Helper to format range
    def format_range(start: int, end: int) -> str:
        # Format "start->end" or "start" (e.g., "4->49")
        if start == end:
            return str(start)
        return f"{start{->{end{"

    # Line 3: Iterate through nums
    for i in range(len(nums) + 1):
        # Include upper check (e.g., 0 to 5)
        curr = nums[i] if i < len(nums) else upper + 1
        # Current value or upper+1 (e.g., 0, 1, 3, 50, 75, 100)

        # Line 4: Check gap between prev and curr
        if curr - prev > 1:
            # If gap exists (e.g., 3-1=2 > 1)
            start = prev + 1
            # Start of range (e.g., 2)
            end = curr - 1
            # End of range (e.g., 2)
            result.append(format_range(start, end))
            # Add range (e.g., "2")

        # Line 5: Update prev
        prev = curr
        # Move prev (e.g., 1)

    # Line 6: Return missing ranges
    return result
    # e.g., ["2","4->49","51->74","76->99"]

This detailed breakdown clarifies how linear scan with range formatting efficiently identifies missing ranges.

Alternative: Two-Pointer with Range Building Approach

Explanation

Two-Pointer with Range Building uses two pointers to traverse the array and bounds:

• Left pointer starts at lower, right at first element or upper + 1.
• Build ranges between pointers, advancing as needed.
• Adjust for array elements and bounds.

It’s a practical alternative, O(n) time with O(1) space (excluding output), but slightly more complex due to pointer management.

For [0,1,3,50,75], lower=0, upper=99:

• 0-0, 1-1, 2-3, 4-50, 51-75, 76-99.

Step-by-Step Example (Alternative)

For [0,1,3,50,75], lower=0, upper=99:

• Step 1: left=0, right=0, match, left=1.
• Step 2: right=1, match, left=2.
• Step 3: right=3, "2", left=3.
• Step 4: right=50, "4->49", left=51.
• Step 5: right=75, "51->74", left=76.
• Step 6: right=100, "76->99".
• Finish: ["2","4->49","51->74","76->99"].

How the Code Works (Two-Pointer)

Copy codedef findMissingRangesTwoPointer(nums: list[int], lower: int, upper: int) -> list[str]:
    result = []
    left = lower
    i = 0

    while i <= len(nums):
        right = nums[i] if i < len(nums) else upper + 1
        if left < right:
            if left == right - 1:
                result.append(str(left))
            else:
                result.append(f"{left{->{right-1{")
        left = right + 1
        i += 1

    return result

Complexity

• Linear Scan with Range Formatting:
• Time: O(n) – single pass.
• Space: O(1) – constant space (excluding output).
• Two-Pointer with Range Building:
• Time: O(n) – single pass.
• Space: O(1) – constant space (excluding output).

Efficiency Notes

Linear Scan with Range Formatting is the best solution with O(n) time and O(1) space, offering clarity and simplicity—Two-Pointer with Range Building matches complexity but requires more pointer juggling, making it slightly less intuitive.

Key Insights

• Linear Scan: Prev-curr gaps.
• Two-Pointer: Left-right ranges.
• Formatting: Consistent output.

Additional Example

For nums = [1,3], lower=0, upper=4:

• Goal: ["0","2","4"].
• Linear: Gaps 0, 2, 4.

Edge Cases

• Empty: [], 1,4 → ["1->4"].
• Full: [1,2], 1,2 → [].
• Single: [2], 1,3 → ["1","3"].

Both solutions handle these well.

Final Thoughts

LeetCode 163: Missing Ranges in Python is a practical range-finding challenge. The Linear Scan with Range Formatting solution excels with its efficiency and clarity, while Two-Pointer with Range Building offers an alternative perspective. Want more? Try LeetCode 228: Summary Ranges for range summarization or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 163 on LeetCode with [0,1,3,50,75], lower=0, upper=99, aiming for ["2","4->49","51->74","76->99"]—test your skills now!