Skip to main content

189. Rotate Array

medium

Rotate an array right by k steps, in-place, with O(1) extra space. The elegant solve uses three reversals — a trick that surprises candidates the first time they see it.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Constraints

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10^5

Examples

Example 1

Input
nums = [1,2,3,4,5,6,7], k = 3
Output
[5,6,7,1,2,3,4]

Explanation: rotate 1 step right: [7,1,2,3,4,5,6]; rotate 2: [6,7,1,2,3,4,5]; rotate 3: [5,6,7,1,2,3,4].

Example 2

Input
nums = [-1,-100,3,99], k = 2
Output
[3,99,-1,-100]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Allocate a copy: easy, but uses O(n) extra space.

Hint 2

k can be larger than n. Always start with k = k % n.

Hint 3

Reverse the entire array, then reverse the first k elements, then reverse the remaining n-k elements. That's three O(n) passes and O(1) extra space.

Solution approach

Reveal approach

Normalize k = k % n (since rotating by n is a no-op). Then perform three in-place reversals: reverse the whole array, reverse nums[0..k-1], and reverse nums[k..n-1]. The combined effect is a right-rotation by k. O(n) time and O(1) extra space. Alternative approaches include using an extra array (O(n) space) or cyclic replacements with a position-tracking algorithm (correct but trickier to implement cleanly).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • array-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta

More Arrays practice problems

See all Arrays problems →