SpaceComplexity

The 3-Line Valid Parentheses Solution That Gets You Rejected

May 25, 20264 min read
interview-prepdsaleetcodealgorithms
The 3-Line Valid Parentheses Solution That Gets You Rejected
TL;DR
  • The golf trap: the 3-line str.replace solution passes all LeetCode tests but runs in O(n²) because deeply nested strings require up to n/2 passes
  • Why it's O(n²): each replace call scans the full string, and nested input forces one collapse per pass
  • Complexity is a scored dimension: Google, Meta, and Amazon evaluate complexity analysis separately from correctness on the interview rubric
  • Interview-optimal means narrate-able: the 12-line stack solution can be explained line by line in 30 seconds, which is what the write-up captures
  • Misanalyzing complexity is a red flag: stating O(n) for an O(n²) solution goes in the feedback notes with negative weight
  • Correct framing beats clever code: naming the O(n²) accurately and offering to fix it signals stronger engineering judgment than a misanalyzed one-liner

Valid Parentheses. You've solved it twenty times. You could write it in your sleep, probably have, definitely have called it "too easy." Here's a three-line Python version that passes every single LeetCode test case and will cost you real points in an actual interview. Guaranteed.

The Standard Solution

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    return not stack

Twelve lines. O(n) time, O(n) space. Readable, narrate-able, correct. Boring, honestly. Which is exactly what makes people want to "improve" it.

The Challenge

Can you write a correct solution in three lines? Not a trick. There's a real elegant version hiding in the structure of the problem. Spend 60 seconds on it.

.

..

...

Ready?

The Golf

def isValid(s: str) -> bool:
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '').replace('[]', '').replace('{}', '')
    return not s

Three lines. Works on "()[]{}". Works on "([{}])". Works on every test case LeetCode ships. Looks absolutely brilliant in a tweet. Gets upvoted on every "clever solutions" thread. Your friends send it to each other.

It's O(n²).

Valid Parentheses Time Complexity: Why the Golf Is O(n²)

Here is what actually happens on "(((())))".

str.replace('()', '') scans the full string and strips every (). But on a deeply nested string it only peels the innermost pair per pass:

"(((())))" → "((()))" → "(())" → "()" → ""

Four passes on a string of length 8. For a string of length n, you need up to n/2 passes. Each pass is O(n). Total: O(n²).

LeetCode's test suite does not include a deeply nested string long enough to time out. The solution passes. Your interviewer has a rubric with a complexity analysis dimension. Those two facts occupy completely different universes, and conflating them is where people get hurt.

What This Costs You

If you wrote the three-line version and correctly called it O(n²), fine. You showed pattern recognition and honest trade-off awareness. The interviewer notes it. Good outcome.

If you said "it's O(n) because replace is fast", you just demonstrated, live, on camera, that you don't understand how string operations work internally. That goes in the write-up. Not as a compliment.

Clever code you cannot analyze is worse than boring code you understand completely. Google, Meta, and Amazon score complexity analysis as its own rubric dimension. Character count does not appear anywhere on it. The same trap shows up across harder problems: five interview questions where your first instinct isn't optimal.

Gru plan meme: "Finally understand coding language" → "Start writing complex algorithms" → "Fall victim to Dunning-Kruger effect" → "Fall victim to Dunning-Kruger effect"

Learned a cool trick. Called it O(n). Now explaining it to a hiring committee.

What Interview-Optimal Actually Looks Like

Not the shortest solution. The one you can talk through while writing it.

Every line of the twelve-line version is explainable in one sentence. The stack accumulates openers. When you hit a closer, you check the top. The sentinel '#' handles the empty-stack case without a separate guard. At the end, anything left unmatched returns false.

You can narrate all of that in 30 seconds. The interviewer follows every step. They're not counting your lines. They're building a model of how you reason under pressure. That model is what gets written down and defended in the hiring committee meeting you will never attend.

The Actual Optimization Target

Code golf optimizes for fitting the most logic into the fewest characters. Interview code optimizes for making your reasoning visible to another human in real time. These are opposite objectives. Confusing them is remarkably easy when you've been practicing on a platform that only scores pass/fail.

Write the clearest solution you can fully analyze out loud, then optimize if the interviewer asks. Not the cleverest solution you can barely explain after the fact.

This is why correct code still gets you the no hire. What you write and what you can defend are two separate signals. Interviewers score both. A solution whose O(n²) you misstate is worse than a solution whose O(n²) you name accurately and offer to improve.

The three-line version is a fun party trick. In an interview, the twelve-line version, narrated confidently, wins.

If you want to practice narrating solutions out loud as much as writing them, SpaceComplexity runs voice-based mock interviews with rubric-graded feedback on complexity analysis and communication together.