In-place manipulation

1
2
3
4
5
6
7
8
9
10
11
12
13

Rotate array [1, 2, 3, 4, 5, 6, 7] right by k = 3 positions:
Goal: [5, 6, 7, 1, 2, 3, 4]

Step 1: Reverse entire array:
        [1, 2, 3, 4, 5, 6, 7]  -->  [7, 6, 5, 4, 3, 2, 1]

Step 2: Reverse first k = 3 elements:
        [7, 6, 5, 4, 3, 2, 1]  -->  [5, 6, 7, 4, 3, 2, 1]

Step 3: Reverse remaining n - k elements:
        [5, 6, 7, 4, 3, 2, 1]  -->  [5, 6, 7, 1, 2, 3, 4]

Time Complexity: O(n) | Auxiliary Space: O(1) | Zero extra buffer allocated!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// Algorithm 1: Rotate Array in O(n) time and O(1) space
public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1); // 1. Reverse all
    reverse(nums, 0, k - 1);            // 2. Reverse first k
    reverse(nums, k, nums.length - 1);  // 3. Reverse remaining
}

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

// Algorithm 2: Dutch National Flag (Sort 0s, 1s, and 2s in a single pass)
public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums, low++, mid++);
        } else if (nums[mid] == 1) {
            mid++;
        } else { // nums[mid] == 2
            swap(nums, mid, high--); // Notice: mid does NOT advance here!
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}