LC 503. Next Greater Element II

The problem

First solution - $O(n)$ Time

While this is very similar to the first one, the trick is handling the circular array which I had to learn how to do. One option I thought of was to duplicate the array and slice the answer for nums.length, but this seemed inefficient. In the end, I googled more about circular arrays and found the idx % arr.length trick which works by doubling the length of the array in my for loop rules. That way, indices greater than the input array's length are reduced to the actual indices in the array.

Example: If nums.length is 6 and the starting index is 0, here is how the modulo trick will iterate circularly compared to the actual index (i):

i loops as $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$

i % nums.length loops as $0 \rightarrow 1 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 2$

function nextGreaterElements(nums: number[]): number[] {
  let ans = Array(nums.length).fill(-1)
  let stack = []
  for (let i = 0; i < nums.length * 2; i++) {
    while (stack.length && nums[i % nums.length] > nums[stack[stack.length - 1]]) {
      let numIdx = stack.pop()
      ans[numIdx] = nums[i % nums.length]
    }
    stack.push(i % nums.length)
  }

  return ans.slice(0, nums.length)
}

Clean up and Improvements

function nextGreaterElements(nums: number[]): number[] {
  let answer = new Array(nums.length).fill(-1)
  let stack = []
  for (let i = 0; i < nums.length * 2; i++) {
    let circularIdx = i % nums.length
    while (stack.length && nums[circularIdx] > nums[stack[stack.length - 1]]) {
      let smallerElementIdx = stack.pop()
      answer[smallerElementIdx] = nums[circularIdx]
    }
    stack.push(circularIdx)
  }
  return answer
}