Ambiguous Coordinates: Generating Valid Number Pairs

LeetCode 816: Ambiguous Coordinates gives you a string like "(123)" and asks you to return all possible coordinate representations "(x, y)" that can be formed from the digits inside. You can split the digits into two parts (left and right) at any position, and you can optionally insert a decimal point into either part. The catch is that both numbers must be valid: no leading zeros (unless the number is just "0"), and no trailing zeros after a decimal point.

For example, given "(123)", the valid outputs are ["(1, 23)", "(1, 2.3)", "(12, 3)", "(1.2, 3)"].

Why this problem matters

Ambiguous Coordinates is a clean exercise in systematic enumeration. You are not searching for a single answer or optimizing a value. You are generating all valid possibilities from a constrained space. This pattern appears across many string and parsing problems: break the input into parts, generate candidates for each part, filter invalid ones, and combine the valid ones.

The problem also forces you to think carefully about number validity rules. Leading zeros, trailing zeros after decimal points, and single-character edge cases all need to be handled. These validation checks are the kind of detail that trips people up under interview pressure, making it a good problem to drill until the rules are automatic.

The key insight

The problem has two layers of enumeration, and they are independent of each other.

First, you split the digit string into a left part and a right part. For a string of length n, there are n - 1 possible split points.

Second, for each part, you generate all valid decimal insertions. A string of length k can have a decimal placed after any of its first k - 1 characters, or no decimal at all. That gives up to k candidates per part, but validity rules prune most of them.

Because the two layers are independent, you can solve them separately. Write a helper that takes a digit string and returns all valid number representations. Then, for each split, take the Cartesian product of valid left numbers and valid right numbers.

Solution approach

The algorithm works in three stages:

1. Strip the outer parentheses from the input to get the raw digit string.
2. For each way to split the string into two non-empty parts, generate all valid numbers from both the left part and the right part.
3. Combine every valid left number with every valid right number, formatting the result as "(x, y)".

The number generation helper tries every possible decimal placement in a digit string. A number is valid if it satisfies two rules:

• No leading zeros: if the string has more than one character and starts with "0", it must have a decimal point immediately after the leading zero (like "0.123").
• No trailing zeros after a decimal: "1.20" is invalid because the last digit after the dot is zero.

def ambiguousCoordinates(s):
    digits = s[1:-1]
    result = []

    def valid_numbers(part):
        nums = []
        if part == "0" or part[0] != "0":
            nums.append(part)
        for i in range(1, len(part)):
            left = part[:i]
            right = part[i:]
            if len(left) > 1 and left[0] == "0":
                continue
            if right[-1] == "0":
                continue
            nums.append(left + "." + right)
        return nums

    for i in range(1, len(digits)):
        left_part = digits[:i]
        right_part = digits[i:]
        for x in valid_numbers(left_part):
            for y in valid_numbers(right_part):
                result.append(f"({x}, {y})")

    return result

Walk through what happens:

1. Strip the parentheses to get digits. For input "(123)", you get "123".
2. The valid_numbers helper takes a digit string and returns all valid number representations. It first checks if the string works as a plain integer (no leading zeros). Then it tries every decimal placement, skipping any that create leading zeros before the decimal or trailing zeros after it.
3. The outer loop splits digits at every position. For "123", the splits are ("1", "23") and ("12", "3").
4. For each split, generate valid numbers for both parts and take their Cartesian product. Format each pair as "(x, y)".

Visual walkthrough

Here is a step-by-step trace of the algorithm on input "(123)". Each card shows one stage of the process.

Notice how the validity checks prune the space early. For a string like "100", only the plain integer "100" survives. Decimal placements "1.00" and "10.0" both fail the trailing-zero rule. This pruning keeps the output size manageable even for longer inputs.

Complexity analysis

The cubic bound is loose. In practice, validity checks eliminate most candidates, and the number of valid pairs is much smaller than the theoretical maximum.

The building blocks

This problem is built from two reusable techniques that appear across many string and enumeration problems.

Constrained string partitioning

The outer loop splits a string into two parts and processes each part independently. This same partitioning pattern appears in Restore IP Addresses (splitting into four segments) and Palindrome Partitioning (splitting into palindromic substrings). The key idea is always the same: enumerate split points, validate each piece, and combine valid pieces into results.

Validity-based filtering

The valid_numbers helper generates candidates and filters them based on structural rules (no leading zeros, no trailing zeros after a decimal). This generate-then-filter pattern shows up wherever you need to enumerate formatted strings: IP address segments, numeric conversions, and expression evaluation problems. Writing a clean, correct validation function is the core skill.

Edge cases

All zeros: "(00)". The only split is ("0", "0"). The plain integer "0" is valid for both parts. Decimal placement "0.0" fails the trailing-zero rule. So the only result is ["(0, 0)"].

Single digits on each side: "(12)". The only split is ("1", "2"). Each part is a single digit, so no decimal can be placed. The result is ["(1, 2)"].

Leading zeros block integers: "(0123)". For the split ("01", "23"), the left part "01" is invalid as a plain integer (leading zero with more than one digit). But "0.1" is valid. So valid left numbers are ["0.1"], and valid right numbers are ["23", "2.3"], giving ["(0.1, 23)", "(0.1, 2.3)"] from this split.

Trailing zeros block decimals: "(100)". For the split ("10", "0"), the left part "10" is a valid integer, but "1.0" fails the trailing-zero rule. The right part "0" is valid. This split yields ["(10, 0)"]. The split ("1", "00") produces no valid right numbers because "00" has a leading zero and "0.0" has a trailing zero.

From understanding to recall

You can read this solution and follow every step. The two validity rules make sense. The split-and-enumerate structure is clear. But under interview pressure, the details slip: do you check leading zeros on the whole string or just the part before the decimal? Does "0" count as having a leading zero? What about trailing zeros on the integer part versus the decimal part?

Spaced repetition locks these details in. You drill the valid_numbers helper as one brick and the split-enumerate-combine pattern as another. Each rep takes a minute or two. After a few rounds at increasing intervals, the leading-zero check (len(left) > 1 and left[0] == "0") and the trailing-zero check (right[-1] == "0") are automatic. When you see a string enumeration problem in an interview, you snap together the bricks without second-guessing the edge cases.

Related posts

• Restore IP Addresses - Another string partitioning problem where you split a digit string into valid segments. The validation rules differ (0-255 range vs. decimal validity), but the enumerate-and-filter structure is the same.
• Generate Parentheses - A constrained enumeration problem where you generate all valid combinations. Both problems share the theme of producing every valid output from a structured space.
• Palindrome Number - A number validation problem that requires careful handling of digits, zeros, and numeric structure.

CodeBricks breaks Ambiguous Coordinates into its string partitioning and validity filtering building blocks, then drills them independently with spaced repetition. You write the split loop and the valid_numbers helper from scratch until they are automatic. When a string enumeration problem shows up in your interview, you do not hesitate. You just write it.