Scale Engineer

Ambiguous Coordinates

Med
#0770Time: O(N^4), where N is the length of the digit string. The main loop runs N-1 times. Inside, generating possibilities for a substring of length k takes O(k^2). Combining results from two lists of size O(i) and O(N-i) takes O(i * (N-i) * N) time. The total time is dominated by this combination step, summing to O(N^4).Space: O(N^4), where N is the length of the digit string. The output list can contain O(N^3) coordinate strings, each of length O(N).
Patterns
BacktrackingEnumeration
Data structures
String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically explores all possibilities. The core idea is to split the input digit string into two parts, x_str and y_str, which will form the x and y coordinates. For each split, we generate all valid numerical interpretations for x_str and y_str. A number can be an integer or a decimal, subject to certain rules about leading and trailing zeros. Finally, we combine every valid x-interpretation with every valid y-interpretation to form the final coordinate pairs.

Algorithm

  • Extract the digit string digits from the input s by removing the parentheses. Let its length be n.
  • Create a list result to store the final coordinate strings.
  • Loop with an index i from 1 to n-1. This i represents the split point.
  • In each iteration, split digits into two substrings: s1 = digits.substring(0, i) and s2 = digits.substring(i).
  • Call a helper function generateValidNumbers(str) for both s1 and s2 to get lists of their valid number representations, list1 and list2.
  • The generateValidNumbers(str) function works as follows:
    • It checks if str itself is a valid integer (no leading zeros unless it's just "0"). If so, add str to its results.
    • It then iterates through all possible decimal point positions in str. For each split into an integer part int_part and a fractional part frac_part:
      • It checks if int_part is a valid integer part (no leading zeros unless it's "0").
      • It checks if frac_part is a valid fractional part (no trailing zeros).
      • If both are valid, it combines them as "int_part.frac_part" and adds to its results.
    • It returns the list of valid representations.
  • After getting list1 and list2, iterate through all pairs (x, y) where x is in list1 and y is in list2.
  • For each pair, format it as "(x, y)" and add it to the result list.
  • Return result.

Walkthrough

First, we remove the outer parentheses from the input string s to get a string of digits. We then iterate through all possible split points of this digit string. A split divides the string into two non-empty substrings, s1 and s2. For each substring (s1 and s2), we find all the ways it can be interpreted as a valid number. This is done by a helper function, generateValidNumbers. The generateValidNumbers function considers two cases for a given digit string t:

  1. Integer: t is a valid integer if it's "0" or doesn't start with '0'.
  2. Decimal: t can be split into an integer part i and a fractional part f. This is a valid decimal if i is a valid integer and f does not end with '0'. The function tries all possible positions for the decimal point. The helper function returns a list of all valid string representations for s1 and s2. We then take the Cartesian product of these two lists. Each pair (x, y) is formatted into the string "(x, y)" and added to our final answer list. The code snippet below illustrates this logic.
class Solution {    public List<String> ambiguousCoordinates(String s) {        List<String> result = new ArrayList<>();        String digits = s.substring(1, s.length() - 1);        int n = digits.length();         for (int i = 1; i < n; i++) {            String s1 = digits.substring(0, i);            String s2 = digits.substring(i);             List<String> list1 = generateValidNumbers(s1);            List<String> list2 = generateValidNumbers(s2);             if (!list1.isEmpty() && !list2.isEmpty()) {                for (String x : list1) {                    for (String y : list2) {                        result.add("(" + x + ", " + y + ")");                    }                }            }        }        return result;    }     private List<String> generateValidNumbers(String t) {        List<String> res = new ArrayList<>();        int n = t.length();        if (n == 0) {            return res;        }         // Case 1: Integer        if (isValidInteger(t)) {            res.add(t);        }         // Case 2: Decimal        for (int i = 1; i < n; i++) {            String intPart = t.substring(0, i);            String fracPart = t.substring(i);            if (isValidInteger(intPart) && isValidFractional(fracPart)) {                res.add(intPart + "." + fracPart);            }        }        return res;    }     private boolean isValidInteger(String s) {        // Not a valid integer if it has a leading zero (and is not "0")        return s.length() <= 1 || s.charAt(0) != '0';    }     private boolean isValidFractional(String s) {        // Not a valid fractional part if it has a trailing zero        return s.charAt(s.length() - 1) != '0';    }}

Complexity

Time

O(N^4), where N is the length of the digit string. The main loop runs N-1 times. Inside, generating possibilities for a substring of length k takes O(k^2). Combining results from two lists of size O(i) and O(N-i) takes O(i * (N-i) * N) time. The total time is dominated by this combination step, summing to O(N^4).

Space

O(N^4), where N is the length of the digit string. The output list can contain O(N^3) coordinate strings, each of length O(N).

Trade-offs

Pros

  • It's a straightforward and easy-to-understand implementation that correctly covers all cases.

  • The logic directly translates the problem statement into code.

Cons

  • It can be inefficient for inputs where the same substring is processed multiple times in different splits (e.g., in (1212)).

  • The time and space complexity are polynomial of a high degree, which might be a concern for larger constraints, though it's acceptable for this problem.

Solutions

class Solution {public  List<String> ambiguousCoordinates(String s) {    int n = s.length();    List<String> ans = new ArrayList<>();    for (int i = 2; i < n - 1; ++i) {      for (String x : f(s, 1, i)) {        for (String y : f(s, i, n - 1)) {          ans.add(String.format("(%s, %s)", x, y));        }      }    }    return ans;  }private  List<String> f(String s, int i, int j) {    List<String> res = new ArrayList<>();    for (int k = 1; k <= j - i; ++k) {      String l = s.substring(i, i + k);      String r = s.substring(i + k, j);      boolean ok = ("0".equals(l) || !l.startsWith("0")) && !r.endsWith("0");      if (ok) {        res.add(l + (k < j - i ? "." : "") + r);      }    }    return res;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem