Algorithm-Day15-Rotate-Array-lc-189

Posted on In , Views:

🧩 Problem Description

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

Example:

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

💡 Naive Approach (Extra Array)

  • Copy elements into a new array

  • Place each element at (i + k) % n index

  • Copy back to nums

  • ✅ Works

  • ❌ Uses O(n) extra space

💡 Optimal Approach: Reverse Method

🧠 Key Idea

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

✅ Why It Works

Reversing segments restores them into rotated order.

🔢 Java Code

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;  // Handle k >= n

        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n)
  • Space Complexity: O(1)
    In-place rotation using reversals

✍️ Summary

  • This problem demonstrates an important array manipulation pattern.
  • The reverse trick is efficient and widely applicable in other rotation-related problems.
  • Avoid extra space when possible by reusing in-place algorithms.

Understand both the logic and implementation of reverse-in-place operations — this comes up in multiple array and string questions!