Galactic Coordinate Parser — Problem Statement & Solution Guide
Problem Description
You are tasked with validating a stream of telemetry data encoded as a string s. The data represents a hierarchical structure of coordinate pairs, where each pair is enclosed in parentheses and formatted as (x, y). The string may contain multiple top-level pairs or pairs nested within other pairs. Your objective is to determine if the parentheses in the string are syntactically balanced and correctly nested.
A string is considered valid if and only if every opening parenthesis ( has a corresponding closing parenthesis ) that appears after it, and the pairs do not cross. Specifically, the sequence of parentheses must form a well-formed bracket structure. The content between the parentheses (the coordinates and commas) is irrelevant to the validation logic; only the balance and nesting order of the parentheses matter.
Return true if the parentheses in s are balanced and properly nested; otherwise, return false.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Coordinate Parser"
WHY DOES IT MATTER?
Balanced‑parentheses validation is a foundational pattern for parsing any nested syntax, from source code compilers to JSON/XML validators, making it a must‑know tool for robust input handling.
OPTIMIZATION CHALLENGE
The key insight is that you only need to know the current depth of nesting, not the entire history, allowing a simple integer counter (or a stack of constant‑size tokens) to replace costly recursive descent parsers.
REAL-WORLD CONNECTION
Think of a network packet framing protocol where start‑ and end‑markers must align; a mismatched marker corrupts the entire transmission, similar to how an unmatched parenthesis corrupts a data structure.
During an interview, write the stack‑based solution first, then discuss the O(1) counter optimization and explicitly state the assumptions that permit it; this shows both correctness and performance awareness.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem reduces to checking whether every opening parenthesis '(' has a matching closing parenthesis ')' in the correct order, which is a classic instance of the balanced‑parentheses problem. A naive scan that counts '(' and ')' separately fails because it cannot detect mis‑ordered pairs such as ")(" or cases where a closing parenthesis appears before its corresponding opening one. The optimal paradigm uses a stack (or a simple counter for this specific case) to simulate the push‑pop behavior of nested structures, guaranteeing linear time validation while correctly handling arbitrary nesting depth. On large inputs (up to 10⁶ characters) this approach avoids the exponential blow‑up of recursive parsing and keeps memory usage proportional to the maximum nesting level rather than the entire string length.
Interview Questions on This Problem
Q1How would you modify the solution if the string could also contain square brackets '[' and ']' that must be matched independently?
Use a single stack and push the opening symbol; when encountering a closing symbol, pop and verify it matches the expected opening type. This extends the same O(n) logic while handling multiple bracket types.
Q2What is the time and space complexity of validating a string with only parentheses using a counter instead of a stack, and when is this optimization safe?
Using a counter yields O(n) time and O(1) space because we only need to track the net balance; it is safe when the language guarantees that only one type of bracket is used and nesting depth does not need to be reported.
Q3In a distributed telemetry pipeline, why might you prefer a streaming validation approach rather than loading the entire string into memory?
Streaming validation processes characters as they arrive, keeping only the current balance (or stack depth) in memory, which reduces peak memory usage and enables early rejection of malformed streams, crucial for high‑throughput systems.
Examples
Input
s = "(1, 2)"
Output
true
Explanation: The string contains one opening parenthesis at index 0 and one closing parenthesis at index 5. The stack starts empty. Push `(`. Pop `(` when `)` is encountered. The stack is empty at the end, and no mismatches occurred. The structure is valid.
Input
s = "(1, (2, 3))"
Output
true
Explanation: The string has nested parentheses. Sequence: `(`, `(`, `)`, `)`. Push first `(`. Push second `(`. Pop second `(` when first `)` is seen. Pop first `(` when second `)` is seen. The stack is empty at the end. The nesting is correct.
Input
s = "(1, 2)(3, 4)"
Output
true
Explanation: The string contains two separate, non-nested tuples. Sequence: `(`, `)`, `(`, `)`. Push `(`, pop on `)`. Stack is empty. Push `(`, pop on `)`. Stack is empty. All parentheses are matched in order.
Input
s = "(1, 2)3, 4)"
Output
false
Explanation: The string has an extra closing parenthesis. Sequence: `(`, `)`, `)`. Push `(`. Pop on first `)`. Stack is empty. Encounter second `)` when stack is empty. This indicates an unmatched closing parenthesis. Return false.
Constraints
- 1 <= s.length <= 10^5
- s consists of digits, commas, spaces, and parentheses
- s contains at least one parenthesis
- The integers x and y within the tuples are between -10^9 and 10^9
- The string does not contain any other types of brackets like [] or {}
Optimal Approach & Strategy
Traverse the string once, using a stack or counter to ensure each '(' is closed in the correct order, achieving linear time and minimal extra space.
Brute Force Approach
Check every possible substring for matching pairs, which leads to exponential time as you repeatedly re‑scan overlapping sections.
Verified Code Solutions
function isBalanced(s) {
let stack = [];
for (let char of s) {
if (char === '(') {
stack.push(char);
} else if (char === ')') {
if (stack.length === 0) {
return false;
}
stack.pop();
}
}
return stack.length === 0;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (s) => {
console.log(isBalanced(s));
rl.close();
});#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool isBalanced(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(') {
st.push(c);
} else if (c == ')') {
if (st.empty()) {
return false;
}
st.pop();
}
}
return st.empty();
}
int main() {
string s;
getline(cin, s);
cout << (isBalanced(s) ? "true" : "false") << endl;
return 0;
}import java.util.Scanner;
import java.util.Stack;
public class Main {
public static boolean isBalanced(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
System.out.println(isBalanced(s));
scanner.close();
}
}def is_balanced(s: str) -> bool:
stack = []
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack:
return False
stack.pop()
return len(stack) == 0
if __name__ == "__main__":
s = input().strip()
print(str(is_balanced(s)).lower())function isBalanced(s) {
let stack = [];
for (let char of s) {
if (char === '(') {
stack.push(char);
} else if (char === ')') {
if (stack.length === 0) {
return false;
}
stack.pop();
}
}
return stack.length === 0;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (s) => {
console.log(isBalanced(s));
rl.close();
});Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.