Next Permutation

Today's Leetcode problem is quite interesting and, personally, I found the in-line array mutation tricky to get right.

We are asked to return the next highest number possible with a given array, falling back to sorting it by ascending order if the source value is the highest possible for that set of numbers.

Sound like a couple of loops to me!

var nextPermutation = function(nums) {
  for (let i = nums.length; i > 0; i--) {
    if (nums[i - 1] < nums[i]) {
      let nextHigherIdx = Infinity;
      for (let j = i; j < nums.length; j++) {
        if (nums[j] > nums[i - 1] && nums[j] <= (nums[nextHigherIdx] || Infinity)) {
          nextHigherIdx = j;
        }
      }
      //replacement must be in-place and use only constant extra memory
      [nums[i - 1], nums[nextHigherIdx]] = [nums[nextHigherIdx], nums[i - 1]];      
      nums.splice(i, nums.length - i, ...nums.splice(i).reverse());
      return;
    }
  }
  //sorted in ascending order as fallback
  nums.sort((a, b) => a - b);
};

//Runtime: 52 ms, faster than 99.41% of JavaScript online submissions
//Memory Usage: 35 MB, less than 33.33% of JavaScript online submissions

Blog

JP Antunes

Join Our Newsletter. No Spam, Only the good stuff.

Related