Valid Parentheses

📋

Problem

Imagine you are building a code editor that needs to instantly check if the parentheses typed by a user are balanced and correctly nested.

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1) Open brackets must be closed by the same type of brackets. 2) Open brackets must be closed in the correct order. Return true if the string is valid, and false otherwise.

1 ≤ s.length ≤ 10^5s consists only of the characters '(', ')', '{', '}', '[' and ']'

Edge cases: Empty string → trueSingle opening bracket '(' → falseSingle closing bracket ')' → false

</>

IDE

def isValid(s: str) -> bool:public boolean isValid(String s)bool isValid(string s)function isValid(s)

def isValid(s: str) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean isValid(String s) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

bool isValid(string s) {
    // Write your solution here
    return false;
}

function isValid(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueReturning true when stack is not empty at end, missing unclosed brackets.✅ Add a final check: return stack.empty() to ensure all brackets matched.

Wrong: trueNot verifying that closing bracket matches the last opening bracket on stack.✅ Before popping, check if stack top matches current closing bracket type; return false if not.

Wrong: falseIncorrectly returning false on empty string input.✅ Return true immediately if input string is empty or stack is empty after processing.

Wrong: timeoutUsing repeated string replacements or nested loops causing O(n^2) complexity.✅ Implement stack-based O(n) solution to avoid timeouts.

✓

Test Cases

Focus on handling empty and minimal inputs correctly to avoid base case errors.

Test your solution against tricky nesting and ordering cases to catch logical bugs.

Optimize your solution to run in linear time to handle large inputs efficiently.

t1_01basic

Input{"s":"()[]{}"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Each opening bracket is matched correctly and in order.

💡 Use a stack to track opening brackets and match them with closing ones.

💡 Check that each closing bracket matches the last opening bracket on the stack.

💡 Return false immediately if a mismatch occurs or stack is empty when closing bracket found.

Why it failed: Returned false or mismatched result on canonical input. Fix by ensuring stack matches pairs correctly and returns true only if stack empty at end.

✓ Correctly matches all pairs and returns true for balanced input.

t1_02basic

Input{"s":"([{}])"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Nested brackets are properly matched in correct order.

💡 Stack must handle nested structures by pushing and popping in correct order.

💡 Verify that closing bracket matches the top of the stack before popping.

💡 Return false if any mismatch or stack empty when expecting to pop.

Why it failed: Incorrectly returns false or true for nested balanced input. Fix by correctly checking top of stack matches closing bracket before popping.

✓ Correctly handles nested balanced brackets.

t2_01edge

Input{"s":""}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty string is trivially balanced.

💡 Consider what an empty input means for your stack.

💡 An empty string means no brackets to match, so should return true.

💡 Ensure your code returns true when input length is zero or stack remains empty.

Why it failed: Returns false on empty string input. Fix by returning true if input is empty or stack is empty after processing.

✓ Correctly returns true for empty input.

t2_02edge

Input{"s":"("}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single opening bracket without closing is invalid.

💡 Check if stack is empty at the end of processing.

💡 If stack is not empty, it means some opening brackets were not closed.

💡 Return false if stack is not empty after processing all characters.

Why it failed: Returns true for single opening bracket input. Fix by verifying stack emptiness at end and returning false if not empty.

✓ Correctly returns false for unclosed single opening bracket.

t2_03edge

Input{"s":")"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single closing bracket without opening is invalid.

💡 If a closing bracket appears when stack is empty, return false immediately.

💡 Check stack before popping to avoid errors.

💡 Return false if closing bracket found but stack empty.

Why it failed: Returns true or crashes on single closing bracket input. Fix by checking stack emptiness before popping and returning false if empty.

✓ Correctly returns false for single closing bracket.

t3_01corner

Input{"s":"((("}

Expectedfalse

⏱ Performance - must finish in 2000ms

Multiple opening brackets without closing are invalid.

💡 Stack should contain all opening brackets until matched.

💡 If stack not empty at end, return false.

💡 Do not prematurely return true; ensure all brackets matched.

Why it failed: Returns true for multiple unclosed opening brackets. Fix by ensuring stack emptiness check at end and returning false if not empty.

✓ Correctly returns false for multiple unclosed opening brackets.

t3_02corner

Input{"s":"([)]"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Incorrectly nested brackets are invalid even if counts match.

💡 Order of closing brackets must match the last opened bracket.

💡 Check top of stack matches current closing bracket type.

💡 Return false immediately if mismatch occurs.

Why it failed: Returns true for incorrectly nested brackets. Fix by verifying top of stack matches closing bracket before popping.

✓ Correctly returns false for incorrectly nested brackets.

t3_03corner

Input{"s":"([]{})"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Mixed types of brackets correctly nested and matched.

💡 Stack must handle multiple bracket types simultaneously.

💡 Match each closing bracket with corresponding opening bracket.

💡 Return false if any mismatch or leftover openings.

Why it failed: Returns false for valid mixed bracket types. Fix by mapping each closing bracket to correct opening bracket and checking stack top.

✓ Correctly returns true for mixed bracket types.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000, solution must run in O(n) time within 2 seconds.

💡 Use a stack-based approach with O(n) time complexity.

💡 Avoid nested loops or repeated string replacements.

💡 Early exit on mismatch to optimize performance.

Why it failed: Solution times out due to O(n^2) or worse complexity. Fix by implementing O(n) stack-based matching algorithm.

✓ Solution runs within time limit using O(n) stack approach.

Practice

1. You receive a continuous stream of lowercase letters and need to report the first character that appears exactly once at each step. Which approach guarantees an optimal O(n) time solution with constant space for this problem?

easy

A. Use a dynamic programming approach to store subproblems of unique characters at each prefix of the stream.

B. Use a brute force scan of the entire stream so far to find the first unique character after each new letter.

C. Maintain a fixed-size frequency array for all lowercase letters and a queue to track potential unique characters, updating both as new letters arrive.

D. Use a greedy approach that picks the first character that hasn't appeared before without tracking frequencies.

Solution

1. Step 1: Understand problem constraints

   The stream consists of lowercase letters only, so a fixed-size frequency array of length 26 suffices.

2. Step 2: Identify optimal approach

   Using a frequency array plus a queue to track candidates for first unique character allows O(1) updates per character and O(n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency array + queue approach is standard for this problem [OK]

Hint: Frequency array + queue yields O(n) time and O(1) space [OK]

Common Mistakes:

• Thinking brute force scanning is efficient enough
• Assuming DP applies here
• Using greedy without frequency tracking

2. Consider the following Python code implementing the optimized next greater element algorithm. What is the final output when calling nextGreaterElement([4,1,2], [1,3,4,2])?

easy

A. [-1, -1, 3]

B. [-1, 3, -1]

C. [3, -1, -1]

D. [3, 4, -1]

Solution

1. Step 1: Trace stack and map updates for nums2

   Process nums2: push 1, then 3 > 1 so pop 1 -> map[1]=3; push 3; 4 > 3 pop 3 -> map[3]=4; push 4; 2 < 4 push 2. Stack ends with [4,2].

2. Step 2: Assign -1 for remaining stack elements and build result

   Pop 2 -> map[2]=-1; pop 4 -> map[4]=-1. Result for nums1=[4,1,2] is [map[4], map[1], map[2]] = [-1,3,-1].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Matches expected output from code comments and manual trace [OK]

Hint: Stack pops smaller elements when a bigger one arrives [OK]

Common Mistakes:

• Confusing order of popping leading to wrong map values
• Forgetting to assign -1 for elements with no next greater
• Mixing up indices when building the final result

3. What is the time and space complexity of the optimal stack-less solution for evaluating a Basic Calculator II expression of length n?

medium

A. O(n) time and O(1) space because it processes the string once and uses only a few variables.

B. O(n^2) time and O(n) space due to repeated string slicing and stack usage.

C. O(n) time and O(n) space because it uses a stack to store intermediate results.

D. O(n log n) time due to sorting operators by precedence and O(1) space.

Solution

1. Step 1: Identify time complexity

   The algorithm scans the input string once, performing constant-time operations per character, so time is O(n).

2. Step 2: Identify space complexity

   Only a fixed number of variables are used (total, last_num, current_num, current_op), so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass and constant variables confirm O(n) time and O(1) space [OK]

Hint: Single pass with fixed vars means O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming stack usage means O(n) space
• Confusing recursion stack with iteration
• Thinking sorting operators is needed

4. What is the time complexity of the optimal iterative stack-based algorithm to evaluate a Reverse Polish Notation expression with n tokens?

medium

A. O(n) because each token is processed exactly once with constant-time stack operations

B. O(n) for processing tokens plus O(n) for recursion stack space

C. O(n log n) due to sorting or priority queue operations involved

D. O(n^2) because each operator requires scanning the stack to find operands

Solution

1. Step 1: Identify operations per token

   Each token is processed once; operands are pushed, operators pop two operands and push one result.

2. Step 2: Analyze stack operations

   Stack push/pop are O(1), so total time is proportional to number of tokens n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No nested loops or recursion in iterative approach [OK]

Hint: Stack operations are O(1), so linear time overall [OK]

Common Mistakes:

• Assuming O(n^2) due to repeated stack scans
• Confusing recursion stack space with time
• Thinking sorting is involved

5. Suppose you want to implement a queue using two stacks, but now the queue must support a 'reuse' operation that re-enqueues the last dequeued element. Which modification ensures correctness and efficiency?

hard

A. Use a third stack to hold reused elements and merge it with push_stack during transfers.

B. After every pop, immediately push the popped element back onto pop_stack to allow reuse, effectively making pop a peek operation.

C. Clear both stacks and re-insert all elements including the reused element to maintain order.

D. Store the last dequeued element separately and push it back onto the push_stack when reuse is called, without changing pop_stack.

Solution

1. Step 1: Understand reuse operation

   Reuse means re-enqueueing the last dequeued element, so it should be treated as a new push.

2. Step 2: Choose efficient modification

   Storing the last popped element separately and pushing it onto push_stack on reuse preserves order and amortized efficiency.

3. Step 3: Analyze other options

   After every pop, immediately push the popped element back onto pop_stack to allow reuse, effectively making pop a peek operation, breaks queue semantics by not removing element. Clearing both stacks and re-inserting all elements including the reused element is inefficient. Using a third stack to hold reused elements and merging it with push_stack during transfers adds unnecessary complexity.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reuse as push to push_stack keeps order and efficiency [OK]

Hint: Reuse = push last popped element onto push_stack [OK]

Common Mistakes:

• Trying to reuse by pushing onto pop_stack
• Rebuilding stacks on reuse causing inefficiency