algoadvance

Leetcode 816. Ambiguous Coordinates Certainly! Let’s break it down step-by-step.

Problem Statement

You are given a string representing coordinates. The string will be in the format "(x, y)". You need to return a list of all possible valid coordinates that can be formed by inserting commas and ensuring no leading zeroes (unless the number is “0”). For example, strings like "0001" can only produce the coordinates [0, 0.001] as 0.001 is the only valid decimal configuration without leading awkward zeroes.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the input string?
    • Is the format of the input string guaranteed (always enclosed in parentheses, always with a comma)?
  2. Output Requirements:
    • Do we need to maintain any specific order of the coordinates in the output list?
    • Should the coordinates be unique or might there be duplicates?

Strategy

  1. Extract the Digits:
    • Remove parentheses and separate the string by the comma to handle x and y coordinates separately.
  2. Generate Possible Valid Numbers:
    • For each substring, generate all valid numbers that can be formed by placing a decimal point at different positions.
    • Ensure no leading zeroes unless the substring is exactly “0”.
  3. Combine Coordinates:
    • Combine each possible valid x with each possible valid y to form coordinate pairs.

Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> generateValidNumbers(string s) {
    vector<string> result;
    if (s.empty()) return result;
    
    if (s[0] == '0' && s.size() > 1) {
        // If the string starts with '0' and its length is > 1
        // it must be "0.xxxx" format to be valid
        if (s[s.size() - 1] != '0') {
            result.push_back("0." + s.substr(1));
        }
    } else {
        result.push_back(s); // whole number case
        for (int i = 1; i < s.size(); ++i) {
            // add the decimal point at position i
            string left = s.substr(0, i);
            string right = s.substr(i);
            if (right.back() != '0') { // no trailing zeroes in fractional part
                result.push_back(left + "." + right);
            }
        }
    }
    return result;
}

vector<string> ambiguousCoordinates(string s) {
    vector<string> result;
    
    // Remove the outer parentheses
    s = s.substr(1, s.size()-2);
    
    for (int i = 1; i < s.size(); ++i) {
        string left = s.substr(0, i);
        string right = s.substr(i);
        
        vector<string> leftParts = generateValidNumbers(left);
        vector<string> rightParts = generateValidNumbers(right);
        
        for (string& l : leftParts) {
            for (string& r : rightParts) {
                result.push_back("(" + l + ", " + r + ")");
            }
        }
    }
    
    return result;
}

// Main function for testing
int main() {
    string input = "(123)";
    vector<string> coordinates = ambiguousCoordinates(input);
    
    for (string& coord : coordinates) {
        cout << coord << endl;
    }
    
    // Test for other cases
    vector<string> testCases = {"(0123)", "(100)", "(00011)", "(0010)"};
    
    for (const string& testCase : testCases) {
        vector<string> coordinates = ambiguousCoordinates(testCase);
        cout << "Coordinates for " << testCase << ":" << endl;
        for (const string& coord : coordinates) {
            cout << coord << endl;
        }
        cout << endl;
    }
    
    return 0;
}

Time Complexity

Therefore, the time complexity is O(n^3) due to the nested operations involved in combining valid numbers. The space complexity is also similar in the worst case.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI