Next Greater Element I

📋

Next Greater Element I

Edge cases:

</>

IDE

def nextGreaterElement(nums1: list[int], nums2: list[int]) -> list[int]:public int[] nextGreaterElement(int[] nums1, int[] nums2)vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2)function nextGreaterElement(nums1, nums2)

def nextGreaterElement(nums1, nums2):
    # Write your solution here
    pass

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // Write your solution here
        return new int[nums1.length];
    }
}

#include <vector>
using namespace std;

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    // Write your solution here
    return vector<int>(nums1.size(), -1);
}

function nextGreaterElement(nums1, nums2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [-1, -1, -1]Brute force scanning fails to find next greater elements correctly or stops too early.✅ Implement monotonic stack to precompute next greater elements for nums2 and then map for nums1.

Wrong: [3, -1]Incorrect mapping of next greater elements from nums2 to nums1, possibly reversed indices or wrong hashmap keys.✅ Ensure hashmap keys are nums2 elements and values are their next greater elements; lookup nums1 elements in this map.

Wrong: [2]Fails on single-element input by returning element itself or wrong value instead of -1.✅ Return -1 when no next greater element exists, especially for single-element arrays.

Wrong: [2, 3, 3]Off-by-one error causing last element to incorrectly get a next greater element.✅ Ensure last element in nums2 maps to -1 as no elements to the right exist.

Wrong: TLE or timeoutUsing nested loops for each nums1 element scanning nums2 causing O(m*n) complexity.✅ Use monotonic stack to precompute next greater elements in O(n) and then map for nums1 in O(m).

✓

Test Cases

Try testing your solution on minimal inputs like single-element arrays and arrays where nums1 equals nums2.

Consider tricky cases like strictly decreasing arrays or inputs that might cause off-by-one errors.

Optimize your solution to avoid nested loops; use a monotonic stack to achieve linear time complexity.

t1_01basic

Input{"nums1":[4,1,2],"nums2":[1,3,4,2]}

Expected[-1,3,-1]

⏱ Performance - must finish in 2000ms

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

💡 Think about how to find the next greater element for each number efficiently.

💡 Use a stack to keep track of elements in decreasing order and a hashmap for lookups.

💡 Precompute next greater elements for nums2 using a monotonic stack, then map results for nums1.

Why it failed: Output incorrect: likely missed mapping next greater elements from nums2 to nums1 or incorrect stack logic. Fix by precomputing next greater for nums2 with a monotonic stack and then lookup for nums1.

✓ Correctly computed next greater elements using monotonic stack and hashmap.

t1_02basic

Input{"nums1":[2,4],"nums2":[1,2,3,4]}

Expected[3,-1]

⏱ Performance - must finish in 2000ms

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

💡 Remember to find the first greater element to the right in nums2 for each nums1 element.

💡 Stack helps track next greater elements in a single pass over nums2.

💡 After building the next greater map for nums2, simply retrieve values for nums1 elements.

Why it failed: Incorrect output due to scanning nums2 incorrectly or not using a stack to optimize. Fix by implementing monotonic stack to precompute next greater elements.

✓ Successfully found next greater elements for all nums1 elements.

t2_01edge

Input{"nums1":[1],"nums2":[1]}

Expected[-1]

⏱ Performance - must finish in 2000ms

Single element in both arrays; no next greater element exists.

💡 Check behavior when arrays have only one element.

💡 Next greater element for the last or only element should be -1.

💡 Ensure code handles single-element arrays without errors.

Why it failed: Fails on single-element input: likely index out of range or missing base case. Fix by returning -1 when no greater element found.

✓ Handles single-element arrays correctly.

t2_02edge

Input{"nums1":[1,2,3],"nums2":[1,2,3]}

Expected[2,3,-1]

⏱ Performance - must finish in 2000ms

nums1 equals nums2; next greater elements are next elements in nums2 or -1 if none.

💡 Test when nums1 and nums2 are identical.

💡 Next greater element for each is the next bigger number to the right in the same array.

💡 Use monotonic stack to find next greater for all elements in nums2.

Why it failed: Incorrect output due to not handling full array or missing last element case. Fix by ensuring last element maps to -1.

✓ Correctly computes next greater elements when nums1 equals nums2.

t2_03edge

Input{"nums1":[4,5],"nums2":[1,2,3,4,5]}

Expected[-1,-1]

⏱ Performance - must finish in 2000ms

nums1 elements are at the end of nums2; no next greater elements exist.

💡 Check elements at the end of nums2 have no next greater element.

💡 Stack should correctly assign -1 for elements with no greater to the right.

💡 Verify mapping from nums2 to nums1 handles end elements.

Why it failed: Fails to assign -1 for elements at the end of nums2. Fix by ensuring stack empties properly and assigns -1 when no greater element found.

✓ Correctly returns -1 for elements at the end of nums2.

t2_04edge

Input{"nums1":[],"nums2":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input arrays; output should be empty list.

💡 Check behavior when input arrays are empty.

💡 Function should handle empty inputs gracefully without errors.

💡 Return empty list when nums1 is empty.

Why it failed: Fails on empty input by throwing error or returning non-empty output. Fix by returning empty list when nums1 is empty.

✓ Handles empty input arrays correctly.

t3_01corner

Input{"nums1":[2,4],"nums2":[4,3,2,1]}

Expected[-1,-1]

⏱ Performance - must finish in 2000ms

nums2 is strictly decreasing; no next greater elements for any nums1 elements.

💡 Test with strictly decreasing nums2 array.

💡 Stack should never find a greater element to the right in decreasing sequence.

💡 Ensure code does not mistakenly assign wrong next greater values.

Why it failed: Incorrect output due to assuming next greater exists in decreasing array. Fix by correctly using stack to assign -1 when no greater element found.

✓ Correctly handles strictly decreasing nums2 with all -1 outputs.

t3_02corner

Input{"nums1":[3,1],"nums2":[1,3,2]}

Expected[-1,3]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors: next greater for 3 is -1; for 1 is 3.

💡 Check indexing carefully when scanning for next greater elements.

💡 Off-by-one errors can cause wrong next greater assignments.

💡 Use monotonic stack to avoid manual scanning and off-by-one mistakes.

Why it failed: Off-by-one error causes wrong next greater element for some inputs. Fix by using stack-based approach instead of manual scanning.

✓ Correctly handles off-by-one indexing for next greater elements.

t3_03corner

Input{"nums1":[1,2],"nums2":[1,2,1,2]}

Expected[]

⏱ Performance - must finish in 2000ms

Invalid input: nums2 contains duplicates which violates problem constraints; behavior undefined.

💡 Problem states nums2 elements are unique; duplicates break hashmap keys.

💡 Check input validity before processing.

💡 If duplicates present, solution may fail or produce incorrect results.

Why it failed: Fails due to duplicate elements in nums2 breaking hashmap keys. Fix by enforcing uniqueness or rejecting invalid input.

✓ No valid output due to invalid input; ensure input uniqueness.

t4_01performance

Input{"nums1":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"nums2":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) or O(n+m) solution must complete within 2 seconds; brute force O(m*n) will time out.

💡 Use a monotonic stack to achieve O(n) time complexity.

💡 Avoid nested loops scanning nums2 for each nums1 element.

💡 Precompute next greater elements for nums2 once, then map for nums1.

Why it failed: TLE due to nested loops O(m*n) complexity. Fix by implementing monotonic stack approach with O(n+m) complexity.

✓ Efficient monotonic stack solution runs within time limits.

Practice

1. You are given an integer array and need to determine if there exists a subsequence of three indices i < j < k such that nums[i] < nums[k] < nums[j]. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force triple nested loops checking all triplets

B. Greedy approach scanning from left to right picking local minima and maxima

C. Using a monotonic stack to track potential '3' and '2' values while iterating backwards

D. Dynamic programming with prefix minimum and suffix maximum arrays

Solution

1. Step 1: Understand the 132 pattern condition

   The problem requires finding a subsequence i < j < k with nums[i] < nums[k] < nums[j], which is the 132 pattern.

2. Step 2: Identify the approach that achieves O(n) time

   The monotonic stack approach iterates from right to left, maintaining candidates for the '3' and '2' elements efficiently, achieving linear time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack approach is known optimal for 132 pattern detection [OK]

Hint: Monotonic stack solves 132 pattern in O(n) [OK]

Common Mistakes:

• Thinking brute force is acceptable for large inputs
• Confusing greedy with monotonic stack
• Assuming DP is needed

2. Consider the following Python code that evaluates Reverse Polish Notation expressions. What is the final output when the input tokens are ["4", "13", "5", "/", "+"]?

class Solution:
    def evalRPN(self, tokens):
        import operator
        ops = {
            '+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': lambda x, y: int(x / y),
        }
        stack = []
        for token in tokens:
            if token in ops:
                right = stack.pop()
                left = stack.pop()
                stack.append(ops[token](left, right))
            else:
                stack.append(int(token))
        return stack.pop()

sol = Solution()
print(sol.evalRPN(["4", "13", "5", "/", "+"]))

easy

A. 2

B. 6

C. 8

D. 10

Solution

1. Step 1: Trace stack operations

   Push 4, push 13, push 5; then '/' operator pops 5 and 13, computes int(13/5) = 2, push 2; then '+' operator pops 2 and 4, computes 4+2=6, push 6.

2. Step 2: Final stack pop

   Pop the last element 6 as the result.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Stack correctly reflects intermediate results [OK]

Hint: Remember integer division truncates toward zero [OK]

Common Mistakes:

• Swapping left and right operands
• Using float division instead of int
• Off-by-one in stack pops

3. Given the following code for a queue implemented with two stacks, what is the output of the last print statement?

q = MyQueue()
q.push(10)
q.push(20)
print(q.pop())
q.push(30)
print(q.peek())

easy

A. 30

B. 20

C. 10

D. Error due to empty stack

Solution

1. Step 1: Trace pop() after pushing 10 and 20

   pop_stack is empty, transfer push_stack [10,20] reversed to pop_stack [20,10], pop() returns 10.

2. Step 2: After pushing 30, peek() checks pop_stack which has [20], so peek returns 20

   After pop(), pop_stack has [20], push_stack has [30]. peek() does not transfer because pop_stack is not empty, so peek returns 20.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   pop() returns 10, peek() returns 20 [OK]

Hint: pop transfers once, peek uses existing pop_stack [OK]

Common Mistakes:

• Assuming peek returns 10 after pop
• Forgetting transfer only when pop_stack empty

4. What is the time complexity of the optimized stack simulation algorithm for the asteroid collision problem, given n asteroids in the input list?

medium

A. O(n) because each asteroid is pushed and popped at most once

B. O(n log n) due to sorting implicit in stack operations

C. O(n^2) because each asteroid can cause multiple pops in the stack

D. O(n) for iteration plus O(n) for auxiliary space, total O(n)

Solution

1. Step 1: Analyze iteration over asteroids

   The algorithm iterates over each asteroid once.

2. Step 2: Analyze stack operations

   Each asteroid can be pushed once and popped once, so total stack operations are O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each asteroid processed at most twice (push/pop) [OK]

Hint: Each asteroid pushed and popped once max [OK]

Common Mistakes:

• Assuming nested while loop causes O(n^2)
• Confusing stack operations with sorting
• Ignoring amortized analysis of stack pops

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