189.js

/** ------------------------------------------------------------------------------
 *
 * 189. Rotate Array
 * Topics: Array, Math, Two Pointers
 * https://leetcode.com/problems/rotate-array/description/
 *
 ------------------------------------------------------------------------------ */
/**
 *
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  for (let i = nums.length - 1; i >= 0; i--) {
    nums[i + k] = nums[i]
  }

  for (let j = k - 1; j >= 0; j--) {
    nums[j] = nums.pop()
  }
}

const a1 = [1, 2, 3, 4, 5, 6, 7]
rotate(a1, 3)
console.log(a1) // [5, 6, 7, 1, 2, 3, 4]

/** ------------------------------------------------------------------------------
 *
 * 모듈러 + 별도 배열 — i 번째는 (i + k) % n 위치로
 * 시간 O(n), 공간 O(n). 큰 k 도 k % n 으로 자동 처리.
 *
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void}
 */
var rotateModular = function (nums, k) {
  const n = nums.length
  k = k % n
  const result = new Array(n)

  for (let i = 0; i < n; i++) {
    result[(i + k) % n] = nums[i]
  }

  for (let i = 0; i < n; i++) nums[i] = result[i]
}

const a2 = [1, 2, 3, 4, 5, 6, 7]
rotateModular(a2, 3)
console.log(a2) // [5, 6, 7, 1, 2, 3, 4]

/** ------------------------------------------------------------------------------
 *
 * Reverse 3번 ⭐ in-place 정답
 * 시간 O(n), 공간 O(1). 면접에서 노리는 풀이.
 *
 *   원본:        [1, 2, 3, 4, 5, 6, 7]   k = 3
 *   1) 전체:     [7, 6, 5, 4, 3, 2, 1]
 *   2) 앞 3개:   [5, 6, 7, 4, 3, 2, 1]
 *   3) 뒤 4개:   [5, 6, 7, 1, 2, 3, 4]
 *
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void}
 */
var rotateReverse = function (nums, k) {
  k = k % nums.length

  reverse(nums, 0, nums.length - 1)
  reverse(nums, 0, k - 1)
  reverse(nums, k, nums.length - 1)
}

function reverse(arr, left, right) {
  while (left < right) {
    ;[arr[left], arr[right]] = [arr[right], arr[left]]
    left++
    right--
  }
}

const a3 = [1, 2, 3, 4, 5, 6, 7]
rotateReverse(a3, 3)
console.log(a3) // [5, 6, 7, 1, 2, 3, 4]

/** ------------------------------------------------------------------------------
 *
 * Cyclic Replacement — 인덱스 사이클 추적
 * 시간 O(n), 공간 O(1). gcd(n, k) 만큼의 사이클을 한 바퀴씩 채워나감.
 *
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void}
 */
var rotateCyclic = function (nums, k) {
  const n = nums.length
  k = k % n
  let count = 0

  for (let start = 0; count < n; start++) {
    let current = start
    let prev = nums[start]

    do {
      const next = (current + k) % n
      ;[nums[next], prev] = [prev, nums[next]]
      current = next
      count++
    } while (start !== current)
  }
}

const a4 = [1, 2, 3, 4, 5, 6, 7]
rotateCyclic(a4, 3)
console.log(a4) // [5, 6, 7, 1, 2, 3, 4]