Array Manipulation

Beyond simple access, manipulating arrays involves operations like insertion, deletion, and rotation. These operations often require shifting elements, resulting in O(N) time complexity.

1. Common Operations

1. Insertion: Inserting at index i requires shifting elements from i to n-1 one position to the right.
2. Deletion: Deleting at index i requires shifting elements from i+1 to n-1 one position to the left.
3. Rotation: Shifting all elements left or right by k steps.

2. Interactive Visualizer: Array Rotation

This visualizer demonstrates rotating an array to the right by k steps using the Cyclic Replacement method. We pick an element, place it in its correct position, take the displaced element, and repeat until we circle back to the start.

Ready. Array: [1, 2, 3, 4, 5, 6, 7], k=3

3. Problem: Rotate Array

Difficulty: Medium

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

Example:

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

Solution 1: Cyclic Replacements

This approach (demonstrated above) moves elements to their correct position one by one in cycles. It uses O(1) extra space.

View Java Solution

class Solution {
  public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n; // Handle k > n

    int count = 0; // Number of elements placed

    for (int start = 0; count < n; start++) {
      int current = start;
      int prev = nums[start];

      do {
        int next = (current + k) % n;
        int temp = nums[next];

        nums[next] = prev;
        prev = temp;

        current = next;
        count++;
      } while (start != current);
    }
  }
}

View Go Solution

package main

func rotate(nums []int, k int) {
	n := len(nums)
	k %= n
	count := 0

	for start := 0; count < n; start++ {
		current := start
		prev := nums[start]

		for {
			next := (current + k) % n
			temp := nums[next]

			nums[next] = prev
			prev = temp

			current = next
			count++

			if start == current {
				break
			}
		}
	}
}

Solution 2: Array Reversal

A simpler approach that is also O(1) space:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the rest (n-k) elements.

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

1. Reverse All: [7,6,5,4,3,2,1]
2. Reverse First 3: [5,6,7, 4,3,2,1]
3. Reverse Rest: [5,6,7, 1,2,3,4] \u2192 Result

View Java Solution (Reversal)

class Solution {
  public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 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--;
    }
  }
}

---

4. Deep Dive Strategy Lab: Array Manipulation

Intuition Through Analogy

Think of this chapter like organizing items on a warehouse shelf. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?