LeetCode 189: Rotate Array Explained (In-Place O(1) Space Solution)

Rotate Array – LeetCode 189 (In-Place O(1) Space Solution)

The Rotate Array problem from LeetCode 189 is a classic array manipulation question frequently asked in coding interviews. The goal is to rotate an array to the right by k steps while modifying the array in-place.

This problem helps build a strong understanding of array indexing, space optimization, and algorithmic thinking.

Problem Statement

Given an integer array nums, rotate the array to the right by k steps. The rotation must be done in-place, meaning no new array should be returned.

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

Key Observations

• If k is greater than the array length, rotation repeats
• We can optimize using k = k % n
• Extra memory usage should be minimized

---

Approach 1: Brute Force Rotation

A simple solution is to move the last element to the front, repeating the process k times.

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k %= n
        for _ in range(k):
            nums.insert(0, nums.pop())

Complexity

• Time Complexity: O(n × k)
• Space Complexity: O(1)

Although this approach works correctly, it is inefficient for large inputs and is not recommended for interviews.

---

Approach 2: Using Array Slicing

This method splits the array into two parts and rearranges them.

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k %= n
        nums[:] = nums[-k:] + nums[:-k]

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

This solution is clean and readable, but it uses extra memory, which violates the strict in-place requirement.

---

Best Approach: Reverse Method (O(1) Space)

The most optimal solution for LeetCode 189 Rotate Array uses the reverse technique. This method avoids slicing and works in constant extra space.

Algorithm Steps

1. Reverse the entire array
2. Reverse the first k elements
3. Reverse the remaining n - k elements

class Solution:
    def rotate(self, nums, k):
        n = len(nums)
        k %= n

        def reverse(left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

This is the best solution for rotating an array in-place and is highly preferred in technical interviews.

---

Why This Solution Is Important for Interviews

• Demonstrates in-place array manipulation
• Uses constant extra space
• Applies a reusable reverse-based pattern

The reverse technique used here also appears in string rotation, cyclic shifts, and memory-efficient transformations.

---

Conclusion

The Rotate Array problem (LeetCode 189) can be solved in multiple ways, but the reverse-based approach is the most efficient and interview-ready solution. Mastering this pattern will help you solve many similar array problems with confidence.