Ambiguous Coordinates - Practice Coding Problems

Ambiguous Coordinates - Problem

We had some 2-dimensional coordinates, like (1, 3) or (2, 0.5). Then, we removed all commas, decimal points, and spaces and ended up with the string s.

For example, (1, 3) becomes s = "(13)" and (2, 0.5) becomes s = "(205)".

Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with fewer digits. Also, a decimal point within a number never occurs without at least one digit occurring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order. All coordinates in the final answer have exactly one space between them (occurring after the comma).

Input & Output

Example 1 — Basic Case

$ Input: s = "(123)"

› Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

💡 Note: Split "123" at positions 1 and 2. For split "1|23": (1, 23) and (1, 2.3). For split "12|3": (12, 3) and (1.2, 3). All combinations are valid.

Example 2 — Leading Zero Constraint

$ Input: s = "(00011)"

› Output: ["(0.001, 1)", "(0, 0.011)"]

💡 Note: Split positions create parts with leading zeros. "0001" cannot be "0001" or "000.1" (invalid), but "0.001" is valid. "1" is valid, "0011" becomes "0.011".

Example 3 — Trailing Zero Constraint

$ Input: s = "(0123)"

› Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

💡 Note: "0" by itself is valid. "123" can be "123", "12.3", "1.23". "01" becomes "0.1" (since "01" has leading zero). "23" can be "23" or "2.3".

Constraints

4 ≤ s.length ≤ 12
s[0] == '(' and s[s.length - 1] == ')'
The rest of s are digits

Visualization

Tap to expand

Understanding the Visualization

Input

String with removed commas, spaces, and decimals: (123)

Process

Try all ways to split and add decimal points with validation

Output

All valid coordinate representations

Key Takeaway

🎯 Key Insight: Systematically try all split positions and decimal placements while validating number format rules

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to systematically split the string and validate number formats. Numbers cannot have leading zeros (except single '0'), cannot end with '0' after decimal, and must have digits before decimal point. Best approach uses enumeration to generate all valid combinations. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Pruning	O(n³)	O(n)	Systematically generate valid coordinate combinations with early pruning
Brute Force Enumeration	O(n³)	O(n)	Try every possible way to split the string and add decimal points

Backtracking with Pruning — Algorithm Steps

Split string into left and right parts
For each part, backtrack through decimal positions
Validate number format at each step
Prune invalid branches early

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Decision

Choose split position systematically

Decimal Placement

For each part, try decimal positions with validation

Prune Invalid

Skip branches that lead to invalid numbers early

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isValidNumber(const char* num) {
    int len = strlen(num);
    if (len == 0 || num[0] == '.' || num[len-1] == '.') {
        return false;
    }
    
    char* dotPos = strchr(num, '.');
    if (dotPos != NULL) {
        int dotIndex = dotPos - num;
        if (dotIndex == 0 || dotIndex == len - 1) return false;
        if (dotIndex > 1 && num[0] == '0') return false;
        if (num[len-1] == '0') return false;
    } else {
        if (len > 1 && num[0] == '0') return false;
    }
    
    return true;
}

int getValidNumbersBT(const char* s, char result[][20]) {
    int count = 0;
    int len = strlen(s);
    if (len == 0) return 0;
    
    if (isValidNumber(s)) {
        strcpy(result[count++], s);
    }
    
    for (int i = 1; i < len; i++) {
        char num[20];
        strncpy(num, s, i);
        num[i] = '.';
        strcpy(num + i + 1, s + i);
        if (isValidNumber(num)) {
            strcpy(result[count++], num);
        }
    }
    
    return count;
}

int solution(const char* s, char result[][50]) {
    int count = 0;
    int len = strlen(s);
    char inner[100];
    strncpy(inner, s + 1, len - 2);
    inner[len - 2] = '\0';
    int innerLen = strlen(inner);
    
    for (int i = 1; i < innerLen; i++) {
        char leftPart[20], rightPart[20];
        strncpy(leftPart, inner, i);
        leftPart[i] = '\0';
        strcpy(rightPart, inner + i);
        
        char leftNumbers[10][20], rightNumbers[10][20];
        int leftCount = getValidNumbersBT(leftPart, leftNumbers);
        int rightCount = getValidNumbersBT(rightPart, rightNumbers);
        
        for (int l = 0; l < leftCount; l++) {
            for (int r = 0; r < rightCount; r++) {
                sprintf(result[count++], "(%s, %s)", leftNumbers[l], rightNumbers[r]);
            }
        }
    }
    
    return count;
}

int main() {
    char s[100];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char result[100][50];
    int count = solution(s, result);
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("\"%s\"", result[i]);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Similar to brute force but with some pruning - still need to check all split and decimal positions

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack for backtracking plus result storage

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler