Good morning! Here's our prompt for today.

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:

1nextLargerNumber([3, 1, 3, 4])
2// [4, 3, 4, -1]
3// 3's next greater is 4
4// 1's next greater is 3
5// 3's next greater is 4 again
6// 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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

var assert = require('assert');

​

function nextLargerNumber(nums) {

  // implement this function

  return nums;

}

​

try {

  assert.deepEqual(nextLargerNumber([3, 1, 3, 4]), [4, 3, 4, -1]);

​

  console.log(

    'PASSED: assert.deepEqual(nextLargerNumber([3, 1, 3, 4]), [4, 3, 4, -1])'

  );

} catch (err) {

  console.log(err);

}

​

Here's a video of us explaining the solution.

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?

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.

xxxxxxxxxx

[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.

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

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.