Problem Statement in English

You’re given an array nums of positive integers.

You must find the next greater element for each element in the array, and if it does not exist, output -1. You’re allowed to look through the array in a circular manner. So, the next greater element index $2$ could be at index $0$, if it’s not after index $2$.

Approach

We use the concept of a monotonic stack to solve this problem. Check out this problem to get a better idea of it.

Add to that a second iteration of the array to simulate the circular nature of the array, and we’re done with the problem.

Solution in Python

  • Brute force solution

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        ans = []

        for i in range(len(nums)):
            j = i + 1

            found = False
            l = len(nums)

            while j % l != i:
                if nums[j % l] > nums[i]:
                    found = True
                    ans.append(nums[j % l])
                    break
                else:
                    j += 1

            if not found:
                ans.append(-1)

        return ans
  • Optimized solution

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        # store length of nums
        l = len(nums)

        # initialize answer
        ans = [-1] * l

        # index, value
        stack: list[tuple[int, int]] = []

        # iterate over the array twice
        # this gives that circular effect
        for i in range(len(nums) * 2):
            # the modulo index
            mi = i % l

            # if the stack is not empty
            # and the value at the top of the stack
            # is less than the current element
            while stack and stack[-1][1] < nums[mi]:
                # pop the element from the stack
                # and update the answer to store
                # this number at the correct index
                ans[stack.pop()[0]] = nums[mi]
            if i < l:
                # ensure we only append values once,
                # since there's no need to append the same value twice
                stack.append((i, nums[i]))

        # return the answer
        return ans

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(n)$
    Since we store the answer in a list of size $n$.

Mistakes I Made

I had to think about the circular nature of the array. Had to look that up :(

And we are done.