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