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.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

var assert = require('assert');

​

function nextLargerNumber(nums) {

  const result = [];

  const stack = [];

  for (let j = 0; j < nums.length; j++) {

    result.push(-1);

  }

  for (let i = 0; i < nums.length * 2; i++) {

    let num = nums[i % nums.length];

    while (stack.length && nums[stack[stack.length - 1]] < num) {

      result[stack.pop()] = num;

    }

    if (i < nums.length) {

      stack.push(i);

    }

  }

  return result;

}

​

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

}

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.