Skip to main content
Talentd

Ambiguous Coordinates - Solution & Explanation

MediumStringBacktrackingEnumeration9 min readAsked at: Google
Practice this problem

Problem Statement

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.)

 

Example 1:

Input: s = "(123)"
Output: ["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]

Example 2:

Input: s = "(0123)"
Output: ["(0, 1.23)","(0, 12.3)","(0, 123)","(0.1, 2.3)","(0.1, 23)","(0.12, 3)"]
Explanation: 0.0, 00, 0001 or 00.01 are not allowed.

Example 3:

Input: s = "(00011)"
Output: ["(0, 0.011)","(0.001, 1)"]

 

Constraints:

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

Approach Overview

Problem Overview: The input is a string like "(123)" where commas, spaces, and decimal points were removed from the original coordinate pair. Your job is to reconstruct every valid coordinate in the form (x, y). Each side may contain a decimal point, but numbers cannot have leading zeros (except "0") or trailing zeros after a decimal.

Approach 1: Brute Force Split and Validate (O(n^3) time, O(n^2) space)

Remove the surrounding parentheses and try every possible split of the string into a left and right part. For each substring, generate all valid numeric representations by optionally inserting a decimal point. Validation follows two rules: integers cannot have leading zeros unless the value is exactly "0", and decimal numbers cannot end with zero. This produces all valid candidates for the left coordinate and all candidates for the right coordinate. Combine every left candidate with every right candidate to form valid coordinate strings. The approach relies heavily on string operations and systematic enumeration of decimal placements.

Approach 2: Dynamic Generation with String Manipulation (O(n^3) time, O(n^2) space)

Instead of generating all substrings first, dynamically build valid numbers while scanning the characters. For each split index, process the left and right substrings independently and construct possible numeric forms directly using string slicing and rule checks. For example, treat the whole substring as an integer candidate, then try inserting a decimal point at each internal position if it doesn't violate the leading or trailing zero constraints. This avoids unnecessary intermediate strings and keeps the validation logic localized. The technique resembles controlled backtracking over decimal placements while enforcing formatting rules.

Recommended for interviews: The brute force split‑and‑validate approach is what most interviewers expect. It clearly demonstrates how you enumerate splits, enforce numeric formatting rules, and combine candidate lists. The dynamic generation variant is cleaner in implementation but conceptually the same complexity. Showing the brute force first proves correctness; explaining how you reduce redundant checks shows deeper string‑handling skill.

Approach 1: Brute Force Split and Validate

This approach involves splitting the string at every possible position to generate potential x and y coordinate pairs, then validating each potential number. The validation checks ensure no extra leading zeros and proper placement of decimal points according to the problem constraints.

The Python solution first strips the parentheses and attempts to split the string at every possible place. For each possible split, it generates all valid decimal representations for both parts and combines them into coordinate pairs.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n^3), where n is the length of the string without parentheses. The combination of each split leads to n^2 pairs, and validating each part could take O(n) time.
Space Complexity: O(n^3), accounts for storing all possible valid coordinates.

Try this approach in the editor →

Approach 2: Dynamic Generation with String Manipulation

This approach entails directly manipulating potential placements of decimal points while adhering to constraints about digits and format validation. It dynamically generates valid representations of left and right parts without separately validating every substring.

The JavaScript solution directly generates valid parts by evaluating each possible division of the number string, and checking inline conditions for valid splitting, thus efficiently producing the valid coordinates.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(n^3), due to multiple levels of iterations and validations. Space Complexity: O(n^3), because all possible coordinates are stored.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Split and Validate

Time Complexity: O(n^3), where n is the length of the string without parentheses. The combination of each split leads to n^2 pairs, and validating each part could take O(n) time.
Space Complexity: O(n^3), accounts for storing all possible valid coordinates.

Dynamic Generation with String Manipulation

Time Complexity: O(n^3), due to multiple levels of iterations and validations. Space Complexity: O(n^3), because all possible coordinates are stored.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Split and ValidateO(n^3)O(n^2)Best for clarity. Easy to reason about and commonly expected in interviews.
Dynamic Generation with String ManipulationO(n^3)O(n^2)Cleaner implementation when generating decimal placements directly without extra validation passes.

Video Solution

Ambiguous Coordinates | Live Coding with Explanation | Leetcode - 816 • Algorithms Made Easy • 1,780 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Ambiguous Coordinates easy or hard?
Ambiguous Coordinates is rated Medium on LeetCode. The algorithm itself is straightforward enumeration, but handling edge cases such as leading zeros and trailing zeros after decimals often trips up candidates during interviews.
Ambiguous Coordinates Python/Java solution
Both Python and Java implementations follow the same structure: remove parentheses, iterate over split positions, generate valid numbers for each substring, and combine them into coordinate pairs. Helper functions usually validate leading zeros and decimal formatting before adding candidates.
How to solve Ambiguous Coordinates in O(n)?
An O(n) solution is not practical because every possible split and decimal placement must be checked to verify formatting rules. The problem inherently requires enumerating candidate numbers, which leads to roughly O(n^3) time in the worst case.
What is the best approach for Ambiguous Coordinates?
The standard solution splits the digits string at every possible index and generates all valid numeric representations for each side. Each substring can either stay an integer or contain one decimal point, while respecting leading and trailing zero rules. This brute force enumeration runs in O(n^3) time and is typically the approach expected in interviews.
Is Ambiguous Coordinates asked at Google/Amazon/Meta?
Ambiguous Coordinates is a medium-level string enumeration problem similar to interview questions asked at companies like Amazon and Google. It tests string manipulation, edge‑case validation, and systematic candidate generation rather than advanced data structures.
What data structure is used in Ambiguous Coordinates?
The solution primarily uses strings and arrays (or lists) to store candidate numbers generated from each substring. No complex data structures are required; the core difficulty lies in validating number formatting rules and combining candidates efficiently.
What is the time complexity of Ambiguous Coordinates?
The typical implementation runs in O(n^3) time. You try O(n) split positions, generate up to O(n) decimal placements for each substring, and build coordinate strings. Space complexity is about O(n^2) excluding the final output list.

Ready to solve this problem?

Practice Ambiguous Coordinates with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring