Valid Parentheses - Practice Coding Problems

Valid Parentheses - Problem

String Stack Easy

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Input & Output

Example 1 — Valid Nested

$ Input: s = "()"

› Output: true

💡 Note: Simple pair: opening parenthesis followed by closing parenthesis

Example 2 — Mixed Valid

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

› Output: true

💡 Note: All brackets properly matched: () pair, then [{}] where {} is nested inside []

Example 3 — Invalid Order

$ Input: s = "(]"

› Output: false

💡 Note: Mismatched types: opening parenthesis ( cannot be closed by square bracket ]

Constraints

1 ≤ s.length ≤ 10⁴
s consists of parentheses only '()[]{}'.

Visualization

Tap to expand

Understanding the Visualization

Input

String containing only bracket characters

Process

Check if brackets are properly paired and nested

Output

Return true if valid, false otherwise

Key Takeaway

🎯 Key Insight: Use a stack to track opening brackets and match them with closing brackets in LIFO order

Asked in

G Google 85 a Amazon 92 M Microsoft 78 F Facebook 65

The key insight is that valid parentheses follow a Last-In-First-Out (LIFO) pattern - the most recently opened bracket must be closed first. A stack perfectly models this behavior. Best approach uses stack matching with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Replace Valid Pairs	O(n²)	O(n)	Repeatedly remove valid pairs until string is empty or no more pairs found
Stack-Based Matching	O(n)	O(n)	Use a stack to match opening brackets with their corresponding closing brackets

Brute Force - Replace Valid Pairs — Algorithm Steps

Scan string for any valid pair: '()', '[]', '{}'
Remove the first valid pair found
Repeat until string is empty or no pairs remain

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial String

Start with input string

Remove Pairs

Find and remove valid pairs

Check Result

Empty string = valid

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s) {
    int len = strlen(s);
    while (true) {
        int oldLen = len;
        char* pos;
        
        // Remove "()" pairs
        while ((pos = strstr(s, "()")) != NULL) {
            memmove(pos, pos + 2, strlen(pos + 2) + 1);
            len -= 2;
        }
        
        // Remove "[]" pairs
        while ((pos = strstr(s, "[]")) != NULL) {
            memmove(pos, pos + 2, strlen(pos + 2) + 1);
            len -= 2;
        }
        
        // Remove "{}" pairs
        while ((pos = strstr(s, "{}")) != NULL) {
            memmove(pos, pos + 2, strlen(pos + 2) + 1);
            len -= 2;
        }
        
        if (len == oldLen) {
            break;
        }
    }
    return len == 0;
}

int main() {
    char s[10001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    bool result = solution(s);
    printf("%s\n", result ? "true" : "false");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, each iteration removes one pair, requiring n/2 iterations, each scanning the string of length n

⚠ Quadratic Growth

Space Complexity

O(n)

String operations may create new string copies

⚡ Linearithmic Space

553.7K Views

Very High Frequency

~15 min Avg. Time

18.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Replace Valid Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler