Next Greater Element in a Circular Array

A circular array is one where the next element of the last element is the first element.

You know how standard arrays look. Instead of [1, 2, 3, 4], imagine the following, where after index 7, we'd move back to index 0.

Can you write a method nextLargerNumber(nums: array) to print the next immediate larger number for every element in the array?

Note: for any element within the circular array, the next immediate larger number could be found circularly-- past the end and before it. If there is no number greater, return -1.

Take the following example, with an analysis for each index:

nextLargerNumber([3, 1, 3, 4])
// [4, 3, 4, -1]
// 3's next greater is 4
// 1's next greater is 3
// 3's next greater is 4 again
// 4 will look to the beginning, but find nothing, so -1

Constraints

• Length of the array <= 100000
• The array will contain values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(n)

```js
function nextLargerNumber(nums) {
  // implement this function
	return nums;
};
```

In a normal array, there's an easy way to acquire the next immediate larger element. We'd stay on one element, and then would simply keep moving up on the indices, performing a comparison against each.

This would continue until we hit the end of the array.

```js
[5, 4, 3, 6]
// starting at 5, we'd check each number
// 5 > 4...
// 5 > 3...
// eventually we'd see 6 > 5
```

The part we need to concern ourselves with in regards to circular arrays is the expectation that each element will not only look to the end, but also require checking against the numbers prior to it as well.

To solve for that, there are a few approaches. Press Next to see what they are!

Double Iteration

One intuitive way is that we can simply iterate through 2*(nums.length) elements in the array (essentially iterating through it twice), and store the next greater than elements in a separate array.

What this does is guarantee that every element gets to be compared with every other one.

This double length array method would work, but has a time complexity of O(n^2)! This is because you not only iterate through each element, but at each step are checking for its existence in an array of 2 * nums.length size.

Let's try to avoid this method and find a faster one.

```py
def next_greater_than(nums):
    if not nums:
        return []
    n = len(nums)
    res = [-1 for _ in range(n)]
    for i in range(n):
        j = i + 1
        while j % n != i:
            if nums[i] < nums[j % n]:
                res[i] = nums[j % n]
                break
            j += 1
    return res


print(next_greater_than([5, 4, 3, 1, 2]))
```

Using a Stack

To speed things up, what we can do is use an auxiliary data structure that helps us keep track of comparisons. Why don't we use a stack?

With a stack, instead of nested loop, we can do one pass instead. This is done by using the follow pseudocode:

Step 1 Push the first element to the stack.

Step 2/3 Iterate through the rest of the elements in a for-loop. - Mark the iterated on/current element as the next element. - If stack is not empty, compare top element of the stack with next. - If next is greater than the top element, pop the element from the stack. What this means is that we've determined next is the next greater element for the popped number. - While the popped element is smaller than next, keep popping off the top of the stack. As the logic follows, next becomes the next greater element for all the popped elements.

Step 3 After iterating through all the other elements, push the next variable onto the stack.

Step 4 When the loop in step 2 is done, pop all the elements from stack and set -1 as the next greater element for them.

One Pager Cheat Sheet

• Write a method nextLargerNumber(nums: array) to print the next immediate larger number for every element in a circular array, managing constraints of time & space complexity of O(n).
• We iterate through the normal array until we find the next immediate larger element.
• Using any of the established solutions such as ring buffers or circular queues, we can effectively utilize a circular array to check each element against numbers both before and after.
• We can avoid double iteration with a big time complexity of O(n^2) by finding a faster way to compare each element with every other one.
• We can improve the speed of our comparison by using a stack to do one pass instead of nested loop.
• Using a for-loop to iteratively pop and compare elements, the algorithm determines the next greater element for each element in the array in a circular fashion.
• The final step is to push the next element onto the stack and then pop all remaining elements, setting -1 as the next greater element for them.