Next Greater Element I

🎯

Next Greater Element I

easySTACKAmazonGoogle

Imagine you have a list of stock prices and want to quickly find the next day when the price is higher for each day - this helps traders make decisions.

💡 This problem is about finding the next bigger number for each element in an array. Beginners often struggle because a naive approach is slow, and the efficient solution requires understanding how to use a stack to track candidates.

📋

Problem Statement

Given two arrays nums1 and nums2 where nums1 is a subset of nums2, for each element in nums1 find the next greater element in nums2. The next greater element of a number x in nums2 is the first greater number to the right of x in nums2. If it does not exist, output -1 for that number.

1 ≤ nums1.length ≤ nums2.length ≤ 10^50 ≤ nums1[i], nums2[i] ≤ 10^9All elements in nums2 are uniqueAll elements in nums1 appear in nums2

💡

Example

Input"nums1 = [4,1,2], nums2 = [1,3,4,2]"

Output[-1,3,-1]

For 4 in nums1, no greater element to the right in nums2; for 1, next greater is 3; for 2, no greater element.

Input"nums1 = [2,4], nums2 = [1,2,3,4]"

Output[3,-1]

For 2, next greater is 3; for 4, no greater element.

• nums1 and nums2 both have only one element → output is [-1]
• nums1 equals nums2 → output is next greater for all elements
• nums1 elements are at the end of nums2 → output is all -1
• nums2 is strictly decreasing → output is all -1 for nums1 elements

⚠️

Common Mistakes

Using nums2.index(x) inside a loop over nums1

Leads to O(m*n) time and TLE on large inputs

✅ Precompute next greater elements for all nums2 once using a stack

Not handling elements with no next greater element

Returns incorrect or missing values instead of -1

✅ Assign -1 to all elements left in stack after processing nums2

Pushing elements onto stack without popping smaller ones first

Stack does not maintain decreasing order, causing wrong results

✅ Pop all smaller elements before pushing current element

Using a stack but forgetting to map next greater elements for nums1

Cannot answer queries for nums1 efficiently

✅ Use a hashmap to store next greater for all nums2 elements and lookup for nums1

Breaking early from loop without ensuring all nums1 elements found

Some nums1 elements remain unmapped, causing errors

✅ Only break when all nums1 elements are found or after full iteration

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly checking each element's next greater element without any optimization. It helps understand the problem's requirements and why a better approach is needed.

Intuition

For each element in nums1, scan nums2 from the element's position to the right to find the first greater element.

Algorithm

1. For each element in nums1, find its index in nums2.
2. From that index, scan rightwards in nums2 to find the first element greater than the current element.
3. If found, record that element as the next greater; otherwise, record -1.
4. Return the list of next greater elements for all nums1 elements.

💡 The nested loops make it easy to understand but hide the inefficiency because you repeatedly scan parts of nums2.

</>

Code

from typing import List

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    result = []
    for x in nums1:
        index = nums2.index(x)  # find position of x in nums2
        next_greater = -1
        for j in range(index + 1, len(nums2)):
            if nums2[j] > x:
                next_greater = nums2[j]
                break
        result.append(next_greater)
    return result

# Driver code
if __name__ == '__main__':
    print(nextGreaterElement([4,1,2], [1,3,4,2]))  # Output: [-1,3,-1]

Line Notes

for x in nums1:Iterate over each element in nums1 to find its next greater element

index = nums2.index(x)Find the position of x in nums2 to know where to start scanning

for j in range(index + 1, len(nums2)):Scan rightwards from x's position to find a greater element

if nums2[j] > x:Check if current element is greater than x to update next_greater

import java.util.*;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int x = nums1[i];
            int index = -1;
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == x) {
                    index = j;
                    break;
                }
            }
            int nextGreater = -1;
            for (int j = index + 1; j < nums2.length; j++) {
                if (nums2[j] > x) {
                    nextGreater = nums2[j];
                    break;
                }
            }
            result[i] = nextGreater;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2});
        System.out.println(Arrays.toString(res)); // [-1,3,-1]
    }
}

Line Notes

for (int i = 0; i < nums1.length; i++) {Loop over each element in nums1

if (nums2[j] == x) {Find index of x in nums2 to start scanning

for (int j = index + 1; j < nums2.length; j++) {Scan rightwards for next greater element

if (nums2[j] > x) {Update nextGreater when a bigger element is found

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

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    vector<int> result;
    for (int x : nums1) {
        int index = -1;
        for (int i = 0; i < nums2.size(); i++) {
            if (nums2[i] == x) {
                index = i;
                break;
            }
        }
        int nextGreater = -1;
        for (int j = index + 1; j < nums2.size(); j++) {
            if (nums2[j] > x) {
                nextGreater = nums2[j];
                break;
            }
        }
        result.push_back(nextGreater);
    }
    return result;
}

int main() {
    vector<int> nums1 = {4,1,2};
    vector<int> nums2 = {1,3,4,2};
    vector<int> res = nextGreaterElement(nums1, nums2);
    for (int val : res) cout << val << ' '; // -1 3 -1
    cout << endl;
    return 0;
}

Line Notes

for (int x : nums1) {Iterate over each element in nums1

if (nums2[i] == x) {Find index of x in nums2 to start scanning

for (int j = index + 1; j < nums2.size(); j++) {Scan rightwards for next greater element

if (nums2[j] > x) {Update nextGreater when a bigger element is found

function nextGreaterElement(nums1, nums2) {
    const result = [];
    for (const x of nums1) {
        const index = nums2.indexOf(x); // find position of x in nums2
        let nextGreater = -1;
        for (let j = index + 1; j < nums2.length; j++) {
            if (nums2[j] > x) {
                nextGreater = nums2[j];
                break;
            }
        }
        result.push(nextGreater);
    }
    return result;
}

// Test
console.log(nextGreaterElement([4,1,2], [1,3,4,2])); // [-1,3,-1]

Line Notes

for (const x of nums1) {Loop over each element in nums1

const index = nums2.indexOf(x);Find index of x in nums2 to start scanning

for (let j = index + 1; j < nums2.length; j++) {Scan rightwards for next greater element

if (nums2[j] > x) {Update nextGreater when a bigger element is found

⏱

Complexity

TimeO(m * n) where m = length of nums1 and n = length of nums2

SpaceO(m) for the output array

For each element in nums1, we scan nums2 to find the next greater element, leading to nested loops and quadratic time in worst case.

💡 If nums1 and nums2 have 1000 elements each, this approach might do up to 1,000,000 comparisons, which is slow.

Interview Verdict: TLE for large inputs; acceptable only for small arrays or to explain the problem

This approach is too slow for big inputs but helps understand the problem and motivates better solutions.

🧠

Using Stack to Precompute Next Greater for nums2

💡 This approach uses a stack to efficiently find the next greater element for every number in nums2 once, then uses a hashmap to answer queries for nums1 quickly.

Intuition

Process nums2 from left to right, using a stack to keep track of elements waiting for their next greater element. When a bigger element appears, pop smaller elements and record their next greater.

Algorithm

1. Initialize an empty stack and a hashmap to store next greater elements.
2. Iterate over nums2:
3. While stack is not empty and current element is greater than stack top, pop from stack and record current element as next greater for popped element.
4. Push current element onto stack.
5. After iteration, elements left in stack have no next greater, map them to -1.
6. For each element in nums1, get its next greater from the hashmap.

💡 The stack maintains a decreasing sequence; popping happens only when a bigger element arrives, ensuring linear time.

</>

Code

from typing import List

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    stack = []
    next_greater_map = {}
    for num in nums2:
        while stack and num > stack[-1]:
            smaller = stack.pop()
            next_greater_map[smaller] = num
        stack.append(num)
    for num in stack:
        next_greater_map[num] = -1
    return [next_greater_map[x] for x in nums1]

# Driver code
if __name__ == '__main__':
    print(nextGreaterElement([4,1,2], [1,3,4,2]))  # Output: [-1,3,-1]

Line Notes

stack = []Initialize stack to keep track of elements waiting for next greater

while stack and num > stack[-1]:Pop smaller elements from stack when current num is bigger

next_greater_map[smaller] = numRecord current num as next greater for popped element

return [next_greater_map[x] for x in nums1]Build result by looking up precomputed next greater values

import java.util.*;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreaterMap = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                nextGreaterMap.put(stack.pop(), num);
            }
            stack.push(num);
        }
        while (!stack.isEmpty()) {
            nextGreaterMap.put(stack.pop(), -1);
        }
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreaterMap.get(nums1[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2});
        System.out.println(Arrays.toString(res)); // [-1,3,-1]
    }
}

Line Notes

Map<Integer, Integer> nextGreaterMap = new HashMap<>();Map to store next greater element for each number

while (!stack.isEmpty() && num > stack.peek()) {Pop smaller elements when current num is bigger

nextGreaterMap.put(stack.pop(), num);Record next greater for popped element

result[i] = nextGreaterMap.get(nums1[i]);Lookup next greater for nums1 elements

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> nextGreaterMap;
    stack<int> st;
    for (int num : nums2) {
        while (!st.empty() && num > st.top()) {
            nextGreaterMap[st.top()] = num;
            st.pop();
        }
        st.push(num);
    }
    while (!st.empty()) {
        nextGreaterMap[st.top()] = -1;
        st.pop();
    }
    vector<int> result;
    for (int x : nums1) {
        result.push_back(nextGreaterMap[x]);
    }
    return result;
}

int main() {
    vector<int> nums1 = {4,1,2};
    vector<int> nums2 = {1,3,4,2};
    vector<int> res = nextGreaterElement(nums1, nums2);
    for (int val : res) cout << val << ' '; // -1 3 -1
    cout << endl;
    return 0;
}

Line Notes

unordered_map<int, int> nextGreaterMap;Map to store next greater element for each number

while (!st.empty() && num > st.top()) {Pop smaller elements when current num is bigger

nextGreaterMap[st.top()] = num;Record next greater for popped element

result.push_back(nextGreaterMap[x]);Lookup next greater for nums1 elements

function nextGreaterElement(nums1, nums2) {
    const stack = [];
    const nextGreaterMap = new Map();
    for (const num of nums2) {
        while (stack.length && num > stack[stack.length - 1]) {
            nextGreaterMap.set(stack.pop(), num);
        }
        stack.push(num);
    }
    while (stack.length) {
        nextGreaterMap.set(stack.pop(), -1);
    }
    return nums1.map(x => nextGreaterMap.get(x));
}

// Test
console.log(nextGreaterElement([4,1,2], [1,3,4,2])); // [-1,3,-1]

Line Notes

const stack = [];Stack to keep track of elements waiting for next greater

while (stack.length && num > stack[stack.length - 1]) {Pop smaller elements when current num is bigger

nextGreaterMap.set(stack.pop(), num);Record next greater for popped element

return nums1.map(x => nextGreaterMap.get(x));Build result by mapping nums1 elements to their next greater

⏱

Complexity

TimeO(n + m) where n = length of nums2 and m = length of nums1

SpaceO(n) for stack and hashmap

Each element is pushed and popped at most once from the stack, making the iteration linear. Lookup for nums1 elements is O(1) each.

💡 For arrays of size 100,000, this approach is efficient and fast enough for interviews.

Interview Verdict: Accepted and optimal for this problem

This is the standard efficient solution expected in interviews.

🧠

Optimized Stack with Early Exit for nums1

💡 This approach is a minor optimization that stops processing nums2 early if all nums1 elements have found their next greater element, saving some unnecessary work.

Intuition

Track how many nums1 elements remain to find next greater; once all are found, stop processing nums2.

Algorithm

1. Create a set of nums1 elements to track which need next greater.
2. Initialize stack and hashmap as before.
3. Iterate over nums2:
4. While stack top is smaller than current num, pop and record next greater; if popped element is in nums1 set, remove it.
5. If nums1 set is empty, break early.
6. Push current num onto stack.
7. Assign -1 to remaining elements in stack.
8. Return next greater for nums1 elements from hashmap.

💡 This reduces unnecessary processing when nums1 is much smaller than nums2.

</>

Code

from typing import List

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    stack = []
    next_greater_map = {}
    nums1_set = set(nums1)
    for num in nums2:
        while stack and num > stack[-1]:
            smaller = stack.pop()
            next_greater_map[smaller] = num
            if smaller in nums1_set:
                nums1_set.remove(smaller)
                if not nums1_set:
                    break
        stack.append(num)
        if not nums1_set:
            break
    while stack:
        next_greater_map[stack.pop()] = -1
    return [next_greater_map[x] for x in nums1]

# Driver code
if __name__ == '__main__':
    print(nextGreaterElement([4,1,2], [1,3,4,2]))  # Output: [-1,3,-1]

Line Notes

nums1_set = set(nums1)Track which nums1 elements still need next greater

while stack and num > stack[-1]:Pop smaller elements and record next greater

if smaller in nums1_set:Remove found elements from tracking set

if not nums1_set: breakStop early if all nums1 elements found

import java.util.*;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Set<Integer> nums1Set = new HashSet<>();
        for (int num : nums1) nums1Set.add(num);
        Map<Integer, Integer> nextGreaterMap = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                int smaller = stack.pop();
                nextGreaterMap.put(smaller, num);
                if (nums1Set.contains(smaller)) {
                    nums1Set.remove(smaller);
                    if (nums1Set.isEmpty()) break;
                }
            }
            stack.push(num);
            if (nums1Set.isEmpty()) break;
        }
        while (!stack.isEmpty()) {
            nextGreaterMap.put(stack.pop(), -1);
        }
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreaterMap.get(nums1[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] res = nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2});
        System.out.println(Arrays.toString(res)); // [-1,3,-1]
    }
}

Line Notes

Set<Integer> nums1Set = new HashSet<>();Track nums1 elements needing next greater

while (!stack.isEmpty() && num > stack.peek()) {Pop smaller elements and record next greater

if (nums1Set.contains(smaller)) {Remove found elements from tracking set

if (nums1Set.isEmpty()) break;Stop early if all nums1 elements found

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
#include <unordered_set>
using namespace std;

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> nextGreaterMap;
    unordered_set<int> nums1Set(nums1.begin(), nums1.end());
    stack<int> st;
    for (int num : nums2) {
        while (!st.empty() && num > st.top()) {
            int smaller = st.top();
            st.pop();
            nextGreaterMap[smaller] = num;
            if (nums1Set.count(smaller)) {
                nums1Set.erase(smaller);
                if (nums1Set.empty()) break;
            }
        }
        st.push(num);
        if (nums1Set.empty()) break;
    }
    while (!st.empty()) {
        nextGreaterMap[st.top()] = -1;
        st.pop();
    }
    vector<int> result;
    for (int x : nums1) {
        result.push_back(nextGreaterMap[x]);
    }
    return result;
}

int main() {
    vector<int> nums1 = {4,1,2};
    vector<int> nums2 = {1,3,4,2};
    vector<int> res = nextGreaterElement(nums1, nums2);
    for (int val : res) cout << val << ' '; // -1 3 -1
    cout << endl;
    return 0;
}

Line Notes

unordered_set<int> nums1Set(nums1.begin(), nums1.end());Track nums1 elements needing next greater

while (!st.empty() && num > st.top()) {Pop smaller elements and record next greater

if (nums1Set.count(smaller)) {Remove found elements from tracking set

if (nums1Set.empty()) break;Stop early if all nums1 elements found

function nextGreaterElement(nums1, nums2) {
    const stack = [];
    const nextGreaterMap = new Map();
    const nums1Set = new Set(nums1);
    for (const num of nums2) {
        while (stack.length && num > stack[stack.length - 1]) {
            const smaller = stack.pop();
            nextGreaterMap.set(smaller, num);
            if (nums1Set.has(smaller)) {
                nums1Set.delete(smaller);
                if (nums1Set.size === 0) break;
            }
        }
        stack.push(num);
        if (nums1Set.size === 0) break;
    }
    while (stack.length) {
        nextGreaterMap.set(stack.pop(), -1);
    }
    return nums1.map(x => nextGreaterMap.get(x));
}

// Test
console.log(nextGreaterElement([4,1,2], [1,3,4,2])); // [-1,3,-1]

Line Notes

const nums1Set = new Set(nums1);Track nums1 elements needing next greater

while (stack.length && num > stack[stack.length - 1]) {Pop smaller elements and record next greater

if (nums1Set.has(smaller)) {Remove found elements from tracking set

if (nums1Set.size === 0) break;Stop early if all nums1 elements found

⏱

Complexity

TimeO(n + m) same as previous approach but with potential early exit

SpaceO(n) for stack and hashmap

Early exit can save time if nums1 is small compared to nums2, but worst case remains linear.

💡 This optimization is useful when nums1 is much smaller than nums2, reducing unnecessary work.

Interview Verdict: Accepted; minor optimization over standard stack approach

Good to mention if interviewer asks about improvements, but not required.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the stack-based precomputation approach is best; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m*n)	O(m)	No	N/A	Mention only - never code for large inputs
2. Stack Precompute Next Greater	O(n + m)	O(n)	No	N/A	Code this approach in 95% of interviews
3. Stack with Early Exit Optimization	O(n + m) with early break	O(n)	No	N/A	Mention if interviewer asks about improvements

💼

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 problem constraints and examples with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the stack-based approach to precompute next greater elements.Step 4: Code the stack approach carefully, explaining each step.Step 5: Test your code with sample inputs and edge cases.Step 6: Optionally mention early exit optimization if time permits.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your understanding of stacks, hash maps, and ability to optimize from brute force to linear time. Clear explanation and clean code are key.

Common Follow-ups

• What if nums2 is circular? → Use a modified stack approach iterating twice over nums2.
• Can you solve it without extra space? → No, because we need to store next greater info for random queries.

💡 These follow-ups test your ability to adapt the monotonic stack pattern and understand space-time tradeoffs.

🔍

Pattern Recognition

When to Use

1) Need to find next greater/smaller element for array elements; 2) Queries on subset of elements; 3) Elements are unique or can be mapped; 4) Efficient O(n) solution needed

Signature Phrases

next greater elementto the rightsubset of nums2first greater number

NOT This Pattern When

Problems asking for maximum subarray sums or LIS are different patterns.

Similar Problems

Next Greater Element II - circular array variant requiring two passesDaily Temperatures - find next warmer day using similar stack logic132 Pattern - uses monotonic stack to find constrained next greater

Practice

1. Consider the following Python function that computes the largest rectangle area in a histogram using a monotonic stack approach. Given the input heights = [2, 1, 5], what is the value of the variable right after computing the right boundaries (just before calculating max_area)?

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [1, 3, 3]

D. [3, 3, 3]

Solution

1. Step 1: Trace right boundary computation for i=2 (height=5)

   Stack is empty, so right[2] = n = 3, stack = [2]

2. Step 2: Trace i=1 (height=1)

   Pop indices with height >= 1: pop 2 (height=5), stack empty, right[1] = 3, stack = [1]

3. Step 3: Trace i=0 (height=2)

   Stack top is 1 (height=1) < 2, so right[0] = 1, stack = [1,0]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Right boundaries correctly reflect next smaller bar indices [OK]

Hint: Right boundaries found by scanning from right with stack [OK]

Common Mistakes:

• Confusing indices or off-by-one in right boundary
• Not clearing stack before right boundary pass

2. Consider the following buggy code for the basic calculator. Which line contains the subtle bug that causes incorrect results on multi-digit numbers?

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    num = 0
    for i, c in enumerate(s):
        if c.isdigit():
            num = int(c)  # Bug here
        elif c in '+-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':  # Push current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':  # Add last number and combine
            result += sign * num
            num = 0
            result *= stack.pop()
            result += stack.pop()
    result += sign * num
    return result

medium

A. Line with 'result += sign * num' inside the '+' or '-' check

B. Line with 'num = int(c)' inside the digit check

C. Line with 'stack.append(result)' inside the '(' check

D. Line with 'result *= stack.pop()' inside the ')' check

Solution

1. Step 1: Analyze digit processing

   Bug is in 'num = int(c)' which resets num instead of accumulating digits for multi-digit numbers.

2. Step 2: Effect of bug

   Multi-digit numbers are treated as single digits, causing incorrect calculation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct code uses 'num = num * 10 + int(c)' [OK]

Hint: Multi-digit numbers require accumulation, not reset [OK]

Common Mistakes:

• Resetting num instead of accumulating digits

3. The following code attempts to find the longest valid parentheses substring using a stack-based approach. Identify the line containing the subtle bug that causes incorrect results for inputs starting with valid parentheses at index 0.

def longestValidParentheses(s: str) -> int:
    stack = []
    max_len = 0
    stack.append(-1)  # Initialize stack with -1
    for i, ch in enumerate(s):
        if ch == '(': 
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

medium

A. Line 4: stack initialized with -1

B. Line 9: popping from stack without checking if empty

C. Line 3: stack initialized as empty list

D. Line 12: resetting stack with current index when empty

Solution

1. Step 1: Analyze stack pop operation

   Line 9 pops from stack without checking if stack is empty, which can cause runtime error or incorrect behavior if stack is empty.

2. Step 2: Understand initialization and reset logic

   Stack initialized with -1 (line 4) is correct to handle valid substrings starting at index 0; resetting stack with current index (line 12) is also correct.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pop without empty check leads to subtle bugs on edge cases [OK]

Hint: Popping stack without empty check causes subtle bugs [OK]

Common Mistakes:

• Forgetting to initialize stack with -1
• Not checking stack emptiness before pop
• Incorrect reset of stack after imbalance

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

5. Suppose the problem is modified so that the input string may contain wildcard characters '*' that can represent either an opening bracket, a closing bracket, or an empty string. Which of the following approaches correctly adapts the stack-based solution to handle this variant efficiently?

hard

A. Use a brute force approach to try all replacements of '*' and check validity

B. Replace all '*' with empty strings and run the original stack-based validation

C. Use two stacks to track possible opening and closing brackets positions and validate ranges

D. Ignore '*' characters and validate only the remaining brackets with the original stack approach

Solution

1. Step 1: Understand wildcard impact

   Wildcards can represent multiple bracket types or empty, so a single stack is insufficient to track all possibilities.

2. Step 2: Use two stacks approach

   One stack tracks positions of opening brackets, another tracks positions of '*'. This allows matching '*' as needed to balance brackets efficiently in one pass.

3. Step 3: Reject invalid sequences

   After processing, ensure all unmatched opening brackets can be matched by '*' positions appearing after them.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Two stacks track brackets and wildcards to handle all cases [OK]

Hint: Two stacks track brackets and wildcards for flexible matching [OK]

Common Mistakes:

• Replacing '*' blindly or ignoring them causes incorrect results