Longest Valid Parentheses

🎯

Longest Valid Parentheses

hardSTACKAmazonFacebookGoogle

Imagine you are building a code editor that highlights the longest balanced parentheses substring to help developers spot syntax errors quickly.

💡 This problem asks for the longest substring of parentheses that is valid (balanced and properly nested). Beginners often struggle because it requires tracking indices and matching pairs, which is not straightforward with simple loops or counters.

📋

Problem Statement

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

1 ≤ s.length ≤ 10^5s consists only of '(' and ')'

💡

Example

Input"\"(()\""

Output2

The longest valid parentheses substring is "()" with length 2.

Input"\")()())\""

Output4

The longest valid parentheses substring is "()()" with length 4.

Input"\"\""

Output0

Empty string has no valid parentheses.

• All '(' characters → 0
• All ')' characters → 0
• Alternating parentheses but no valid pairs, e.g. ')(' → 0
• Entire string is valid, e.g. '()()()' → length of entire string

⚠️

Common Mistakes

Not initializing stack with -1 in stack approach

Incorrect length calculations for valid substrings starting at index 0

✅ Always push -1 onto stack before iteration

Checking all substrings without skipping odd lengths in brute force

Wasted computations on substrings that cannot be valid

✅ Only check substrings of even length

In two-pass approach, forgetting to reset counters when imbalance occurs

Incorrect max length calculation due to counting invalid sequences

✅ Reset left and right counters when imbalance detected

Using stack to store characters instead of indices

Cannot calculate length of valid substrings correctly

✅ Store indices in stack, not characters

Not scanning from right to left in two-pass approach

Misses valid substrings with extra '(' at the end

✅ Perform both left-to-right and right-to-left scans

🧠

Brute Force (Check All Substrings)

💡 This approach exists to build intuition by trying every possible substring and checking if it is valid. It is simple but inefficient, helping beginners understand the problem's requirements deeply.

Intuition

Try every substring and check if it forms a valid parentheses sequence by counting and matching parentheses.

Algorithm

1. Generate all possible substrings of the input string.
2. For each substring, check if it is a valid parentheses string by using a stack or counter.
3. Keep track of the maximum length of valid substrings found.
4. Return the maximum length after checking all substrings.

💡 The nested loops and validation step make this approach easy to understand but inefficient, which is why we improve it later.

</>

Code

def longestValidParentheses(s: str) -> int:
    def isValid(sub: str) -> bool:
        stack = []
        for ch in sub:
            if ch == '(': 
                stack.append(ch)
            else:
                if not stack:
                    return False
                stack.pop()
        return len(stack) == 0

    max_len = 0
    n = len(s)
    for i in range(n):
        for j in range(i + 2, n + 1, 2):  # only even length substrings
            if isValid(s[i:j]):
                max_len = max(max_len, j - i)
    return max_len

# Driver code
if __name__ == '__main__':
    test_cases = ["(()", ")()())", "", "()()()", "((((", "))))"]
    for tc in test_cases:
        print(f"Input: {tc} -> Longest Valid Parentheses: {longestValidParentheses(tc)}")

Line Notes

def isValid(sub: str) -> bool:Helper function to check if a substring is valid parentheses

stack = []Initialize stack to track '(' characters

if ch == '(':Push '(' onto stack to match later

if not stack:If stack empty when encountering ')', substring invalid

for i in range(n):Outer loop to select start index of substring

for j in range(i + 2, n + 1, 2):Inner loop to select end index, only even lengths

if isValid(s[i:j]):Check validity of current substring

max_len = max(max_len, j - i)Update max length if valid substring found

public class Solution {
    public static boolean isValid(String sub) {
        java.util.Stack<Character> stack = new java.util.Stack<>();
        for (char ch : sub.toCharArray()) {
            if (ch == '(') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    public static int longestValidParentheses(String s) {
        int maxLen = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 2; j <= n; j += 2) {
                if (isValid(s.substring(i, j))) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        String[] testCases = {"(()", ")()())", "", "()()()", "((((", "))))"};
        for (String tc : testCases) {
            System.out.println("Input: " + tc + " -> Longest Valid Parentheses: " + longestValidParentheses(tc));
        }
    }
}

Line Notes

public static boolean isValid(String sub)Helper method to check validity of substring

java.util.Stack<Character> stack = new java.util.Stack<>();Stack to track '(' characters

if (ch == '(')Push '(' onto stack

if (stack.isEmpty()) return false;Invalid if ')' found without matching '('

for (int i = 0; i < n; i++)Outer loop for substring start

for (int j = i + 2; j <= n; j += 2)Inner loop for substring end, even length only

if (isValid(s.substring(i, j)))Check if substring is valid

maxLen = Math.max(maxLen, j - i);Update max length if valid

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(const string& sub) {
    stack<char> st;
    for (char ch : sub) {
        if (ch == '(') {
            st.push(ch);
        } else {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

int longestValidParentheses(string s) {
    int maxLen = 0;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 2; j <= n; j += 2) {
            if (isValid(s.substr(i, j - i))) {
                maxLen = max(maxLen, j - i);
            }
        }
    }
    return maxLen;
}

int main() {
    string testCases[] = {"(()", ")()())", "", "()()()", "((((", "))))"};
    for (auto& tc : testCases) {
        cout << "Input: " << tc << " -> Longest Valid Parentheses: " << longestValidParentheses(tc) << endl;
    }
    return 0;
}

Line Notes

bool isValid(const string& sub)Helper function to check substring validity

stack<char> st;Stack to track '(' characters

if (ch == '(')Push '(' onto stack

if (st.empty()) return false;Invalid if ')' without matching '('

for (int i = 0; i < n; i++)Outer loop for substring start

for (int j = i + 2; j <= n; j += 2)Inner loop for substring end, even length only

if (isValid(s.substr(i, j - i)))Check validity of substring

maxLen = max(maxLen, j - i);Update max length if valid

function isValid(sub) {
    const stack = [];
    for (const ch of sub) {
        if (ch === '(') {
            stack.push(ch);
        } else {
            if (stack.length === 0) return false;
            stack.pop();
        }
    }
    return stack.length === 0;
}

function longestValidParentheses(s) {
    let maxLen = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 2; j <= n; j += 2) {
            if (isValid(s.slice(i, j))) {
                maxLen = Math.max(maxLen, j - i);
            }
        }
    }
    return maxLen;
}

// Test cases
const testCases = ["(()", ")()())", "", "()()()", "((((", "))))"];
for (const tc of testCases) {
    console.log(`Input: ${tc} -> Longest Valid Parentheses: ${longestValidParentheses(tc)}`);
}

Line Notes

function isValid(sub)Helper function to check if substring is valid

const stack = [];Stack to track '(' characters

if (ch === '(')Push '(' onto stack

if (stack.length === 0) return false;Invalid if ')' without matching '('

for (let i = 0; i < n; i++)Outer loop for substring start

for (let j = i + 2; j <= n; j += 2)Inner loop for substring end, even length only

if (isValid(s.slice(i, j)))Check validity of substring

maxLen = Math.max(maxLen, j - i);Update max length if valid

⏱

Complexity

TimeO(n^3)

SpaceO(n)

There are O(n^2) substrings and each substring validity check takes O(n) in worst case.

💡 For n=20, this means roughly 20^3=8000 operations, which is slow but still manageable for small inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Stack Based Approach

💡 This approach uses a stack to track indices of characters, allowing us to efficiently find valid substrings by matching parentheses and calculating lengths.

Intuition

Use a stack to store indices of '(' characters and unmatched ')' indices to calculate lengths of valid substrings between them.

Algorithm

1. Initialize a stack with -1 to mark the base for valid substring calculations.
2. Iterate over the string characters with their indices.
3. If character is '(', push its index onto the stack.
4. If character is ')', pop from the stack; if stack is empty after pop, push current index as base; else calculate length from current index to top of stack and update max length.
5. Return the maximum length found.

💡 The stack helps track the last unmatched index, so the difference between current index and stack top gives length of valid substring.

</>

Code

def longestValidParentheses(s: str) -> int:
    stack = [-1]
    max_len = 0
    for i, ch in enumerate(s):
        if ch == '(':  # push index of '('
            stack.append(i)
        else:  # ch == ')'
            stack.pop()  # pop matching '('
            if not stack:  # stack empty means no base for valid substring
                stack.append(i)  # set new base
            else:
                max_len = max(max_len, i - stack[-1])  # length between current and last unmatched
    return max_len

# Driver code
if __name__ == '__main__':
    test_cases = ["(()", ")()())", "", "()()()", "((((", "))))"]
    for tc in test_cases:
        print(f"Input: {tc} -> Longest Valid Parentheses: {longestValidParentheses(tc)}")

Line Notes

stack = [-1]Initialize stack with -1 as base index for valid substring calculations

for i, ch in enumerate(s):Iterate over string with index to track positions

if ch == '(':Push index of '(' to stack to match later

stack.pop()Pop last '(' index when ')' found to form a pair

if not stack:If stack empty after pop, no valid base, push current index

max_len = max(max_len, i - stack[-1])Calculate length of current valid substring

import java.util.Stack;

public class Solution {
    public static int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        String[] testCases = {"(()", ")()())", "", "()()()", "((((", "))))"};
        for (String tc : testCases) {
            System.out.println("Input: " + tc + " -> Longest Valid Parentheses: " + longestValidParentheses(tc));
        }
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Stack to store indices of '(' and unmatched positions

stack.push(-1);Initialize stack with -1 as base index

if (ch == '(')Push index of '(' onto stack

stack.pop();Pop last '(' index when ')' found

if (stack.isEmpty())If stack empty after pop, push current index as new base

maxLen = Math.max(maxLen, i - stack.peek());Calculate length of valid substring

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1);
    int maxLen = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            st.pop();
            if (st.empty()) {
                st.push(i);
            } else {
                maxLen = max(maxLen, i - st.top());
            }
        }
    }
    return maxLen;
}

int main() {
    string testCases[] = {"(()", ")()())", "", "()()()", "((((", "))))"};
    for (auto& tc : testCases) {
        cout << "Input: " << tc << " -> Longest Valid Parentheses: " << longestValidParentheses(tc) << endl;
    }
    return 0;
}

Line Notes

stack<int> st;Stack to store indices for matching parentheses

st.push(-1);Initialize stack with -1 as base index

if (s[i] == '(')Push index of '(' onto stack

st.pop();Pop last '(' index when ')' found

if (st.empty())If stack empty after pop, push current index as new base

maxLen = max(maxLen, i - st.top());Calculate length of valid substring

function longestValidParentheses(s) {
    const stack = [-1];
    let maxLen = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.length === 0) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }
    return maxLen;
}

// Test cases
const testCases = ["(()", ")()())", "", "()()()", "((((", "))))"];
for (const tc of testCases) {
    console.log(`Input: ${tc} -> Longest Valid Parentheses: ${longestValidParentheses(tc)}`);
}

Line Notes

const stack = [-1];Initialize stack with -1 as base index

if (s[i] === '(')Push index of '(' onto stack

stack.pop();Pop last '(' index when ')' found

if (stack.length === 0)If stack empty after pop, push current index as new base

maxLen = Math.max(maxLen, i - stack[stack.length - 1]);Calculate length of valid substring

⏱

Complexity

TimeO(n)

SpaceO(n)

Each character is pushed and popped at most once, so linear time. Stack space is at most n.

💡 For n=10^5, this means about 200,000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews for this problem.

🧠

Two-Pass Counter Approach (Left-Right Scan)

💡 This approach uses two passes with counters to track the number of '(' and ')' seen, allowing us to find valid substrings without extra space.

Intuition

Scan from left to right counting '(' and ')'. When counts match, update max length. If ')' count exceeds '(', reset counters. Repeat scanning from right to left to catch valid substrings missed in first pass.

Algorithm

1. Initialize left and right counters to zero.
2. Scan string from left to right: increment left for '(' and right for ')'.
3. When left equals right, update max length; if right exceeds left, reset counters.
4. Reset counters and scan from right to left similarly, incrementing counters accordingly.
5. Return the maximum length found.

💡 Two passes ensure all valid substrings are counted, including those with unmatched '(' at the start or end.

</>

Code

def longestValidParentheses(s: str) -> int:
    left = right = max_len = 0
    # Left to right scan
    for ch in s:
        if ch == '(': left += 1
        else: right += 1
        if left == right:
            max_len = max(max_len, 2 * right)
        elif right > left:
            left = right = 0
    left = right = 0
    # Right to left scan
    for ch in reversed(s):
        if ch == ')': right += 1
        else: left += 1
        if left == right:
            max_len = max(max_len, 2 * left)
        elif left > right:
            left = right = 0
    return max_len

# Driver code
if __name__ == '__main__':
    test_cases = ["(()", ")()())", "", "()()()", "((((", "))))"]
    for tc in test_cases:
        print(f"Input: {tc} -> Longest Valid Parentheses: {longestValidParentheses(tc)}")

Line Notes

left = right = max_len = 0Initialize counters and max length

for ch in s:Left to right scan over string

if ch == '(': left += 1Count '(' characters

elif right > left: left = right = 0Reset counters if ')' exceed '('

for ch in reversed(s):Right to left scan to catch missed valid substrings

if left == right: max_len = max(max_len, 2 * left)Update max length when balanced

public class Solution {
    public static int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLen = 0;
        // Left to right scan
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') left++;
            else right++;
            if (left == right) maxLen = Math.max(maxLen, 2 * right);
            else if (right > left) left = right = 0;
        }
        left = right = 0;
        // Right to left scan
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == ')') right++;
            else left++;
            if (left == right) maxLen = Math.max(maxLen, 2 * left);
            else if (left > right) left = right = 0;
        }
        return maxLen;
    }

    public static void main(String[] args) {
        String[] testCases = {"(()", ")()())", "", "()()()", "((((", "))))"};
        for (String tc : testCases) {
            System.out.println("Input: " + tc + " -> Longest Valid Parentheses: " + longestValidParentheses(tc));
        }
    }
}

Line Notes

int left = 0, right = 0, maxLen = 0;Initialize counters and max length

for (int i = 0; i < s.length(); i++)Left to right scan

if (s.charAt(i) == '(') left++;Count '(' characters

else if (right > left) left = right = 0;Reset counters if ')' exceed '('

for (int i = s.length() - 1; i >= 0; i--)Right to left scan

if (left == right) maxLen = Math.max(maxLen, 2 * left);Update max length when balanced

#include <iostream>
#include <string>
using namespace std;

int longestValidParentheses(string s) {
    int left = 0, right = 0, maxLen = 0;
    // Left to right scan
    for (char ch : s) {
        if (ch == '(') left++;
        else right++;
        if (left == right) maxLen = max(maxLen, 2 * right);
        else if (right > left) left = right = 0;
    }
    left = right = 0;
    // Right to left scan
    for (int i = (int)s.size() - 1; i >= 0; i--) {
        if (s[i] == ')') right++;
        else left++;
        if (left == right) maxLen = max(maxLen, 2 * left);
        else if (left > right) left = right = 0;
    }
    return maxLen;
}

int main() {
    string testCases[] = {"(()", ")()())", "", "()()()", "((((", "))))"};
    for (auto& tc : testCases) {
        cout << "Input: " << tc << " -> Longest Valid Parentheses: " << longestValidParentheses(tc) << endl;
    }
    return 0;
}

Line Notes

int left = 0, right = 0, maxLen = 0;Initialize counters and max length

for (char ch : s)Left to right scan

if (ch == '(') left++;Count '(' characters

else if (right > left) left = right = 0;Reset counters if ')' exceed '('

for (int i = (int)s.size() - 1; i >= 0; i--)Right to left scan

if (left == right) maxLen = max(maxLen, 2 * left);Update max length when balanced

function longestValidParentheses(s) {
    let left = 0, right = 0, maxLen = 0;
    // Left to right scan
    for (const ch of s) {
        if (ch === '(') left++;
        else right++;
        if (left === right) maxLen = Math.max(maxLen, 2 * right);
        else if (right > left) left = right = 0;
    }
    left = right = 0;
    // Right to left scan
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === ')') right++;
        else left++;
        if (left === right) maxLen = Math.max(maxLen, 2 * left);
        else if (left > right) left = right = 0;
    }
    return maxLen;
}

// Test cases
const testCases = ["(()", ")()())", "", "()()()", "((((", "))))"];
for (const tc of testCases) {
    console.log(`Input: ${tc} -> Longest Valid Parentheses: ${longestValidParentheses(tc)}`);
}

Line Notes

let left = 0, right = 0, maxLen = 0;Initialize counters and max length

for (const ch of s)Left to right scan

if (ch === '(') left++;Count '(' characters

else if (right > left) left = right = 0;Reset counters if ')' exceed '('

for (let i = s.length - 1; i >= 0; i--)Right to left scan

if (left === right) maxLen = Math.max(maxLen, 2 * left);Update max length when balanced

⏱

Complexity

TimeO(n)

SpaceO(1)

Two passes over the string with constant extra space for counters.

💡 For n=10^5, this means about 200,000 operations, very efficient and minimal memory use.

Interview Verdict: Accepted

This approach is optimal in space and time, making it a great alternative to the stack method.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the stack approach is usually best due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(n)	No	Yes	Mention only - never code
2. Stack Based Approach	O(n)	O(n)	No	Yes	Code this approach
3. Two-Pass Counter Approach	O(n)	O(1)	No	No (length only)	Good alternative, mention or code if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Present the brute force approach to show understanding.Step 3: Explain the stack-based approach as an efficient solution.Step 4: Mention the two-pass counter approach as a space-optimized alternative.Step 5: Code the stack approach or two-pass approach depending on interviewer preference.Step 6: Test your code with edge cases and explain your reasoning.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force, knowledge of stack usage, and handling of edge cases.

Common Follow-ups

• What if the input contains other characters? → Ignore or preprocess to filter parentheses.
• Can you return the substring itself? → Track start indices during computation.

💡 These follow-ups test your ability to adapt the solution to variations and extend functionality.

🔍

Pattern Recognition

When to Use

1. Problem involves parentheses or brackets. 2. Need to find longest valid or balanced substring. 3. Requires tracking indices or counts. 4. Stack or two-pointer techniques are applicable.

Signature Phrases

longest valid parentheses substringwell-formed parenthesesbalanced parentheses

NOT This Pattern When

Problems asking for counting total valid substrings or different bracket types without longest substring focus

Similar Problems

Valid Parentheses - checks if entire string is validMinimum Add to Make Parentheses Valid - counts insertions neededLongest Valid Substring - similar substring length problem

Practice

1. Given an integer array, you need to find the sum of the minimum values of all possible contiguous subarrays. Which algorithmic approach guarantees an optimal O(n) time complexity solution?

easy

A. Monotonic stack to find previous less and next less elements for each array element

B. Greedy approach selecting minimum elements from left to right

C. Dynamic programming with memoization of subarray minimums

D. Brute force nested loops checking all subarrays and their minimums

Solution

1. Step 1: Understand problem constraints

   The problem requires summing minimums of all subarrays efficiently, which brute force cannot do in O(n).

2. Step 2: Identify the pattern

   Monotonic stack helps find previous less and next less elements in O(n), enabling counting subarrays where each element is minimum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is known optimal for this problem [OK]

Hint: Monotonic stack finds boundaries for minimums in O(n) [OK]

Common Mistakes:

• Assuming greedy or DP solves this in O(n)
• Confusing with maximum subarray problems

2. The following code attempts to detect the 132 pattern using the optimal approach. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line 4: for num in reversed(nums):

B. Line 5: if num <= third:

C. Line 7: while stack and stack[-1] < num:

D. Line 9: stack.append(num)

Solution

1. Step 1: Analyze the condition on line 5

   The original correct condition is num < third. Using num <= third incorrectly returns True when num equals third, which violates strict inequality in 132 pattern.

2. Step 2: Confirm other lines are correct

   Iteration order, stack operations, and append are correct and necessary for the algorithm.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Using <= instead of < causes false positives [OK]

Hint: Strict inequality is required for pattern detection [OK]

Common Mistakes:

• Using <= instead of <
• Confusing iteration direction
• Not popping smaller elements

3. 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

4. Suppose the calculator expression can contain multiplication '*' and division '/' operators in addition to plus, minus, and parentheses. Which modification to the stack-based approach correctly handles operator precedence and parentheses?

hard

A. Use two stacks: one for numbers and one for operators, applying operators with higher precedence immediately before pushing lower precedence operators

B. Continue using a single stack and apply all operators in the order they appear, ignoring precedence

C. Convert the expression to postfix notation first, then evaluate using a stack

D. Evaluate recursively without any stack, relying on Python's eval() function

Solution

1. Step 1: Understand operator precedence

   Multiplication and division have higher precedence than addition and subtraction, so evaluation order matters.

2. Step 2: Modify stack approach

   Using two stacks (numbers and operators) allows applying higher precedence operators immediately, preserving correct order.

3. Step 3: Why other options fail

   Single stack ignoring precedence leads to wrong results; postfix conversion is valid but more complex; relying on eval() is unsafe and not interview-appropriate.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two-stack approach is standard for precedence and parentheses [OK]

Hint: Two stacks handle precedence and parentheses correctly [OK]

Common Mistakes:

• Ignoring precedence or relying on single stack only

5. Suppose the sliding window maximum problem is modified so that the window size k can vary dynamically during the iteration. Which of the following approaches correctly adapts the monotonic deque solution to handle this efficiently?

hard

A. Adjust the window boundary checks and remove indices outside the current window size dynamically without rebuilding the deque

B. Rebuild the deque from scratch each time the window size changes

C. Switch to a max heap data structure since deque cannot handle variable window sizes

D. Use a brute force approach for variable window sizes to avoid complexity

Solution

1. Step 1: Understand dynamic window size impact

   Window boundaries change, so indices outside the current window must be removed accordingly.

2. Step 2: Adapt monotonic deque maintenance

   Instead of rebuilding, update boundary checks and pop indices outside the new window size dynamically.

3. Step 3: Evaluate alternatives

   Rebuilding deque or switching to heap is inefficient; brute force is too slow.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Dynamic boundary checks maintain O(n) amortized complexity [OK]

Hint: Update boundary removals dynamically, avoid rebuilding [OK]

Common Mistakes:

• Rebuilding deque wastes time
• Assuming heap is better for variable k