AlgoDaily - Next Greater Element in a Circular Array

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.

xxxxxxxxxx
 
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]))

OUTPUT

Results will appear here.