Next Permutation

Description

doc

Solutions

First Idea

function sortSubArrayInPlace(start, nums) {
  for (let i = start; i < nums.length; i++) {
    let minIdx = i
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIdx]) {
        minIdx = j
      }
    }
    if (minIdx !== i) {
      let tmp = nums[minIdx]
      nums[minIdx] = nums[i]
      nums[i] = tmp
    }
  }
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  let idx = nums.length - 1
  while (idx > 0) {
    if (nums[idx - 1] < nums[idx]) {
      break
    }

    idx--
  }

  const prev = idx - 1
  if (prev < 0) {
    return sortSubArrayInPlace(idx, nums)
  }

  sortSubArrayInPlace(idx, nums)
  while (idx < nums.length) {
    if (nums[idx] > nums[prev]) {
      break
    }
    idx++
  }

  const tmp = nums[idx]
  nums[idx] = nums[prev]
  nums[prev] = tmp
  return nums
}