LC-2454 Hard LeetCode

2454. Next Greater Element IV

Array Binary Search Stack Sorting Heap (Priority Queue) Monotonic Stack

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 40% Topics: Array, Binary Search, Stack, Sorting, Heap (Priority Queue), Monotonic Stack

Reading material

Arrays & Hashing 12 min Binary Search 12 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

# mono stack
class Solution(object):
    def secondGreaterElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result, stk1, stk2 = [-1]*len(nums), [], []
        for i, x in enumerate(nums):
            while stk2 and nums[stk2[-1]] < x:
                result[stk2.pop()] = x
            tmp = []
            while stk1 and nums[stk1[-1]] < x:
                tmp.append(stk1.pop())
            stk1.append(i)
            for x in reversed(tmp):
                stk2.append(x)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT