Rotate Array by K Steps

Rotate an array to the right by k steps where k is non-negative

Language Selection

Choose your preferred programming language

Showing: Python

Rotate Array by K Steps

Problem Statement

Given an array, rotate the array to the right by k steps, where k is non-negative. The rotation should be done in-place with O(1) extra space.

Input/Output Specifications

  • Input: An array of integers nums where 1 <= nums.length <= 10^5 and -2^31 <= nums[i] <= 2^31 - 1, and an integer k where 0 <= k <= 10^5
  • Output: The array rotated to the right by k steps (modified in-place)

Constraints

  • Must modify the array in-place
  • k can be larger than the array length
  • The array contains at least one element
  • Optimize for space complexity O(1)

Examples

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation: Rotate right by 3 steps:
[1,2,3,4,5,6,7] -> [7,1,2,3,4,5,6] -> [6,7,1,2,3,4,5] -> [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: Rotate right by 2 steps:
[-1,-100,3,99] -> [99,-1,-100,3] -> [3,99,-1,-100]

Example 3:

Input: nums = [1,2], k = 3
Output: [2,1]
Explanation: k=3 is equivalent to k=1 for array of length 2.

Solution Approaches

Approach 1: Array Reversal (Optimal)

Algorithm Explanation:

  1. Handle edge cases and normalize k using modular arithmetic
  2. Reverse the entire array
  3. Reverse the first k elements
  4. Reverse the remaining n-k elements
  5. The array is now rotated by k positions

Implementation:

Python:

def rotate_array(nums, k):
    """
    Rotate array using reversal approach
    Time: O(n)
    Space: O(1)
    """
    if not nums or k == 0:
        return
    
    n = len(nums)
    k = k % n  # Handle k > n
    
    if k == 0:
        return
    
    # Helper function to reverse array segment
    def reverse(start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
    
    # Step 1: Reverse entire array
    reverse(0, n - 1)
    
    # Step 2: Reverse first k elements
    reverse(0, k - 1)
    
    # Step 3: Reverse remaining elements
    reverse(k, n - 1)

# Alternative using list slicing (creates new array)
def rotate_array_slicing(nums, k):
    """
    Rotate array using slicing (not in-place)
    Time: O(n)
    Space: O(n)
    """
    if not nums or k == 0:
        return nums
    
    n = len(nums)
    k = k % n
    
    return nums[-k:] + nums[:-k] if k > 0 else nums

Java:

class Solution {
    /**
     * Rotate array using reversal approach
     * Time: O(n)
     * Space: O(1)
     */
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k == 0) {
            return;
        }
        
        int n = nums.length;
        k = k % n;  // Handle k > n
        
        if (k == 0) {
            return;
        }
        
        // Step 1: Reverse entire array
        reverse(nums, 0, n - 1);
        
        // Step 2: Reverse first k elements
        reverse(nums, 0, k - 1);
        
        // Step 3: Reverse remaining elements
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
    
    // Alternative using extra array
    public void rotateExtraArray(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k == 0) {
            return;
        }
        
        int n = nums.length;
        k = k % n;
        
        int[] temp = new int[n];
        
        // Copy elements to their new positions
        for (int i = 0; i < n; i++) {
            temp[(i + k) % n] = nums[i];
        }
        
        // Copy back to original array
        System.arraycopy(temp, 0, nums, 0, n);
    }
}

Go:

// rotateArray - Rotate array using reversal approach
// Time: O(n)
// Space: O(1)
func rotateArray(nums []int, k int) {
    if len(nums) <= 1 || k == 0 {
        return
    }
    
    n := len(nums)
    k = k % n  // Handle k > n
    
    if k == 0 {
        return
    }
    
    // Helper function to reverse slice segment
    reverse := func(start, end int) {
        for start < end {
            nums[start], nums[end] = nums[end], nums[start]
            start++
            end--
        }
    }
    
    // Step 1: Reverse entire array
    reverse(0, n-1)
    
    // Step 2: Reverse first k elements
    reverse(0, k-1)
    
    // Step 3: Reverse remaining elements
    reverse(k, n-1)
}

// Alternative using append (creates new slice)
func rotateArraySlice(nums []int, k int) []int {
    if len(nums) <= 1 || k == 0 {
        return nums
    }
    
    n := len(nums)
    k = k % n
    
    if k == 0 {
        return nums
    }
    
    return append(nums[n-k:], nums[:n-k]...)
}

JavaScript:

/**
 * Rotate array using reversal approach
 * Time: O(n)
 * Space: O(1)
 */
function rotate(nums, k) {
    if (!nums || nums.length <= 1 || k === 0) {
        return;
    }
    
    const n = nums.length;
    k = k % n;  // Handle k > n
    
    if (k === 0) {
        return;
    }
    
    // Helper function to reverse array segment
    const reverse = (start, end) => {
        while (start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]];
            start++;
            end--;
        }
    };
    
    // Step 1: Reverse entire array
    reverse(0, n - 1);
    
    // Step 2: Reverse first k elements
    reverse(0, k - 1);
    
    // Step 3: Reverse remaining elements
    reverse(k, n - 1);
}

// Alternative using splice
function rotateSplice(nums, k) {
    if (!nums || nums.length <= 1 || k === 0) {
        return;
    }
    
    const n = nums.length;
    k = k % n;
    
    if (k === 0) {
        return;
    }
    
    const rotated = nums.splice(-k).concat(nums);
    nums.length = 0;
    nums.push(...rotated);
}

// Alternative using unshift and pop
function rotateUnshift(nums, k) {
    if (!nums || nums.length <= 1 || k === 0) {
        return;
    }
    
    k = k % nums.length;
    
    for (let i = 0; i < k; i++) {
        nums.unshift(nums.pop());
    }
}

C#:

public class Solution {
    /// <summary>
    /// Rotate array using reversal approach
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public void Rotate(int[] nums, int k) {
        if (nums == null || nums.Length <= 1 || k == 0) {
            return;
        }
        
        int n = nums.Length;
        k = k % n;  // Handle k > n
        
        if (k == 0) {
            return;
        }
        
        // Step 1: Reverse entire array
        Reverse(nums, 0, n - 1);
        
        // Step 2: Reverse first k elements
        Reverse(nums, 0, k - 1);
        
        // Step 3: Reverse remaining elements
        Reverse(nums, k, n - 1);
    }
    
    private void Reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
    
    // Alternative using LINQ (creates new array)
    public int[] RotateLinq(int[] nums, int k) {
        if (nums == null || nums.Length <= 1 || k == 0) {
            return nums;
        }
        
        int n = nums.Length;
        k = k % n;
        
        return nums.Skip(n - k).Concat(nums.Take(n - k)).ToArray();
    }
}

Complexity Analysis:

  • Time Complexity: O(n) - We reverse the array segments, each element is moved exactly once
  • Space Complexity: O(1) - Only using a constant amount of extra space

Trade-offs:

  • Optimal space complexity with in-place modification
  • Three simple reversal operations
  • Easy to understand and implement
  • Works for any value of k

Approach 2: Cyclic Replacement

Algorithm Explanation:

  1. Start from index 0 and place each element in its final position
  2. Follow the cycle until we return to the starting position
  3. If we haven’t moved all elements, start a new cycle
  4. Continue until all elements are in their correct positions

Implementation:

Python:

def rotate_cyclic(nums, k):
    """
    Rotate array using cyclic replacement
    Time: O(n)
    Space: O(1)
    """
    if not nums or k == 0:
        return
    
    n = len(nums)
    k = k % n
    
    if k == 0:
        return
    
    count = 0  # Number of elements moved
    start = 0
    
    while count < n:
        current = start
        prev = nums[start]
        
        # Follow the cycle
        while True:
            next_idx = (current + k) % n
            nums[next_idx], prev = prev, nums[next_idx]
            current = next_idx
            count += 1
            
            # If we're back to start, break the cycle
            if start == current:
                break
        
        # Move to next cycle if needed
        start += 1

Java:

class Solution {
    /**
     * Rotate array using cyclic replacement
     * Time: O(n)
     * Space: O(1)
     */
    public void rotateCyclic(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k == 0) {
            return;
        }
        
        int n = nums.length;
        k = k % n;
        
        if (k == 0) {
            return;
        }
        
        int count = 0;  // Number of elements moved
        int start = 0;
        
        while (count < n) {
            int current = start;
            int prev = nums[start];
            
            // Follow the cycle
            do {
                int nextIdx = (current + k) % n;
                int temp = nums[nextIdx];
                nums[nextIdx] = prev;
                prev = temp;
                current = nextIdx;
                count++;
            } while (start != current);
            
            // Move to next cycle if needed
            start++;
        }
    }
}

Go:

// rotateCyclic - Rotate array using cyclic replacement
// Time: O(n)
// Space: O(1)
func rotateCyclic(nums []int, k int) {
    if len(nums) <= 1 || k == 0 {
        return
    }
    
    n := len(nums)
    k = k % n
    
    if k == 0 {
        return
    }
    
    count := 0  // Number of elements moved
    start := 0
    
    for count < n {
        current := start
        prev := nums[start]
        
        // Follow the cycle
        for {
            nextIdx := (current + k) % n
            nums[nextIdx], prev = prev, nums[nextIdx]
            current = nextIdx
            count++
            
            // If we're back to start, break the cycle
            if start == current {
                break
            }
        }
        
        // Move to next cycle if needed
        start++
    }
}

JavaScript:

/**
 * Rotate array using cyclic replacement
 * Time: O(n)
 * Space: O(1)
 */
function rotateCyclic(nums, k) {
    if (!nums || nums.length <= 1 || k === 0) {
        return;
    }
    
    const n = nums.length;
    k = k % n;
    
    if (k === 0) {
        return;
    }
    
    let count = 0;  // Number of elements moved
    let start = 0;
    
    while (count < n) {
        let current = start;
        let prev = nums[start];
        
        // Follow the cycle
        do {
            const nextIdx = (current + k) % n;
            [nums[nextIdx], prev] = [prev, nums[nextIdx]];
            current = nextIdx;
            count++;
        } while (start !== current);
        
        // Move to next cycle if needed
        start++;
    }
}

C#:

public class Solution {
    /// <summary>
    /// Rotate array using cyclic replacement
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public void RotateCyclic(int[] nums, int k) {
        if (nums == null || nums.Length <= 1 || k == 0) {
            return;
        }
        
        int n = nums.Length;
        k = k % n;
        
        if (k == 0) {
            return;
        }
        
        int count = 0;  // Number of elements moved
        int start = 0;
        
        while (count < n) {
            int current = start;
            int prev = nums[start];
            
            // Follow the cycle
            do {
                int nextIdx = (current + k) % n;
                int temp = nums[nextIdx];
                nums[nextIdx] = prev;
                prev = temp;
                current = nextIdx;
                count++;
            } while (start != current);
            
            // Move to next cycle if needed
            start++;
        }
    }
}

Complexity Analysis:

  • Time Complexity: O(n) - Each element is moved exactly once
  • Space Complexity: O(1) - Only using a constant amount of extra space

Trade-offs:

  • More complex logic but still optimal
  • Directly places elements in final positions
  • Requires understanding of cycle detection
  • Good for understanding mathematical properties of rotation

Key Insights

  • Modular Arithmetic: Using k % n handles cases where k > array length
  • Reversal Strategy: Three reversals achieve rotation efficiently
  • Cycle Detection: Understanding how elements form cycles during rotation
  • In-Place Requirement: Achieving O(1) space complexity is the main challenge

Edge Cases

  1. k = 0: No rotation needed → [1,2,3] stays [1,2,3]
  2. k = n: Full rotation → [1,2,3] stays [1,2,3]
  3. k > n: k=5, n=3 → equivalent to k=2
  4. Single Element: [5], k=3 → stays [5]
  5. Two Elements: [1,2], k=1 → becomes [2,1]
  6. All Same: [3,3,3], k=2 → stays [3,3,3]

How Solutions Handle Edge Cases:

  • Modular arithmetic normalizes k to valid range
  • Early returns for trivial cases
  • Proper boundary checks prevent index errors
  • Works correctly for all edge cases

Test Cases

def test_rotate_array():
    # Basic rotation
    nums = [1,2,3,4,5,6,7]
    rotate_array(nums, 3)
    assert nums == [5,6,7,1,2,3,4]
    
    # Small array
    nums = [-1,-100,3,99]
    rotate_array(nums, 2)
    assert nums == [3,99,-1,-100]
    
    # k larger than array
    nums = [1,2]
    rotate_array(nums, 3)
    assert nums == [2,1]
    
    # No rotation
    nums = [1,2,3]
    rotate_array(nums, 0)
    assert nums == [1,2,3]
    
    # Full rotation
    nums = [1,2,3]
    rotate_array(nums, 3)
    assert nums == [1,2,3]
    
    # Single element
    nums = [1]
    rotate_array(nums, 1)
    assert nums == [1]
    
    # Large k
    nums = [1,2,3,4,5]
    rotate_array(nums, 12)  # 12 % 5 = 2
    assert nums == [4,5,1,2,3]
    
    print("All tests passed!")

test_rotate_array()

Follow-up Questions

  1. Left Rotation: How would you rotate to the left instead?
  2. Minimum Rotations: Find minimum rotations to sort an array
  3. Rotation Detection: Check if one array is rotation of another
  4. 2D Rotation: How would you rotate a 2D matrix?
  5. Linked List: How would you rotate a linked list?

Common Mistakes

  1. Not Handling k > n: Forgetting modular arithmetic

    • Problem: Unnecessary rotations when k exceeds array length
    • Solution: Use k = k % n at the beginning

  2. Index Out of Bounds: Incorrect boundary calculations

    • Problem: Accessing invalid array indices
    • Solution: Careful validation of start/end indices

  3. Incomplete Cycles: Not handling all elements in cyclic approach

    • Problem: Some elements remain in wrong positions
    • Solution: Use counter to track moved elements

  4. Modifying During Iteration: Changing array while iterating incorrectly

    • Problem: Lost or duplicated elements
    • Solution: Use proper temporary variables or algorithms

Interview Tips

  1. Clarify Direction: Ask if rotation is left or right
  2. Discuss Constraints: Confirm in-place requirement and space constraints
  3. Start Simple: Begin with reversal approach - it’s intuitive and optimal
  4. Handle Edge Cases: Discuss k=0, k>n, and small arrays
  5. Multiple Approaches: Mention cyclic replacement as alternative

Concept Explanations

Array Rotation Pattern: This problem demonstrates fundamental array manipulation techniques including reversal, modular arithmetic, and cycle detection. These patterns appear in many array problems.

Modular Arithmetic: Understanding how (i + k) % n works is crucial for circular array problems and helps handle edge cases elegantly.

When to Apply: Use these rotation techniques for problems involving circular arrays, sliding windows, or any scenario where elements need to be shifted in a cyclic manner.