#189

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Rotate Array

Rotate Array challenges you to shift elements right by k steps using precise two-pointer scanning and invariant tracking techniques.

array math two pointers

Problem Statement

Given an integer array nums, rotate its elements to the right by k positions. Each element should end up in the correct shifted index while handling potential overwrites efficiently. The rotation must work even when k is larger than the array length.

For example, rotating nums = [1,2,3,4,5,6,7] by k = 3 should produce [5,6,7,1,2,3,4]. Another case, nums = [-1,-100,3,99] with k = 2 results in [3,99,-1,-100]. Constraints include array lengths up to 105, integer values within -231 to 231 - 1, and non-negative k up to 105.

Examples

Example 1

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

Output: [5,6,7,1,2,3,4]

rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2

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

Output: [3,99,-1,-100]

rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Constraints

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

Solution Approach

Use Extra Array for Direct Rotation

Allocate a new array of the same size and place each element at its target index calculated by (current index + k) % n. This simple method avoids in-place overwriting issues and demonstrates the two-pointer invariant concept in a straightforward manner.

In-place Cyclic Replacement

Treat the array as cycles and move each element to its rotated position in-place using a two-pointer technique. Track the start of each cycle to prevent infinite loops and ensure every element is moved exactly once, preserving the original array's invariants.

Reverse Segments for Efficient Rotation

Reverse the entire array, then reverse the first k elements and finally reverse the remaining n-k elements. This uses the two-pointer scanning pattern twice per reversal and effectively shifts elements to their correct rotated positions while avoiding extra memory allocation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach: extra array method is O(n), in-place cyclic replacement is O(n), and reversal method is O(n). Space complexity ranges from O(n) for the extra array to O(1) for in-place or reversal approaches.

What Interviewers Usually Probe

Look for a solution that moves elements efficiently without overwriting unprocessed values.
Pay attention if k exceeds array length and discuss modulo behavior.
Expect discussion on trade-offs between extra memory versus in-place rotation.

Common Pitfalls or Variants

Common pitfalls

Overwriting elements before their new position is set in in-place methods.
Failing to account for k values larger than the array size, causing incorrect indexing.
Mismanaging cycle starts, resulting in infinite loops or missing elements during cyclic replacement.

Follow-up variants

Rotate the array to the left instead of the right using similar two-pointer scanning logic.
Rotate a multidimensional array row-wise or column-wise by k steps.
Rotate only a subarray segment while leaving other elements intact.

FAQ

What is the easiest way to rotate an array using extra memory?

Create a new array of the same length and assign each element to index (i + k) % n, then copy back to the original array.

How do I handle k values greater than the array length?

Use modulo: effective rotation is k % n, ensuring indices wrap correctly without overflow.

Can I rotate the array in-place without extra space?

Yes, use cyclic replacement or the reverse method to move elements using two-pointer scanning while preserving values.

Why does cyclic replacement require tracking cycles?

Without tracking cycles, elements may be overwritten or moved multiple times, breaking the invariant of each element reaching its target position.

How does two-pointer scanning relate to Rotate Array?

It allows controlled movement of elements in-place or within subarrays, ensuring no overwrites occur and every element reaches its final rotated index.

terminal

Solution

Solution 1: Reverse three times

We can assume the length of the array is $n$ and calculate the actual number of steps needed by taking the module of $k$ and $n$, which is $k \bmod n$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(i: int, j: int):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1

        n = len(nums)
        k %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

Continue Practicing

#167 two sum ii input array is sorted #268 missing number #287 find the duplicate number