Array Rotation Techniques in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is array rotation?

Array rotation means shifting the elements of an array to the left or right by a certain number of positions, wrapping around the ends.

intermediate

Explain the 'Rotate by Reversal' method.

Rotate by Reversal rotates an array by reversing parts of the array in three steps: reverse the first part, reverse the second part, then reverse the whole array.

intermediate

What is the time complexity of rotating an array using the reversal method?

The time complexity is O(n), where n is the number of elements in the array, because each element is reversed at most twice.

advanced

Describe the 'Rotate by Juggling' algorithm.

Rotate by Juggling divides the array into sets based on the greatest common divisor (GCD) of array size and rotation count, then moves elements within each set to rotate the array efficiently.

beginner

Why is it important to use modulo operation when rotating arrays?

Modulo helps handle rotation counts larger than the array size by wrapping the rotation count within the array length, preventing unnecessary full rotations.

What does rotating an array to the left by 2 positions do to the array [1, 2, 3, 4, 5]?

A [3, 4, 5, 1, 2]

B [4, 5, 1, 2, 3]

C [2, 3, 4, 5, 1]

D [5, 1, 2, 3, 4]

Rotating left by 2 moves the first two elements to the end, resulting in [3, 4, 5, 1, 2].

Which step is NOT part of the reversal method for array rotation?

A Reverse the first part of the array

B Reverse the entire array

C Reverse the second part of the array

D Sort the array

Sorting is not involved in the reversal method; it only uses reversing parts of the array.

In the juggling algorithm, what mathematical concept helps divide the array into sets?

A Greatest common divisor (GCD)

B Least common multiple (LCM)

C Prime factorization

D Fibonacci sequence

The GCD of the array size and rotation count determines the number of sets in juggling.

If you rotate an array of size 5 by 7 positions to the right, what is the effective rotation?

A 5 positions

B 2 positions

C 7 positions

D 0 positions

7 modulo 5 equals 2, so rotating by 7 is the same as rotating by 2.

What is the space complexity of the reversal method for array rotation?

A O(n)

B O(log n)

C O(1)

D O(n^2)

Reversal method rotates the array in place using constant extra space.

Explain how the reversal method rotates an array step-by-step.

Think about reversing parts before the full array.

Describe the juggling algorithm and how it uses the greatest common divisor (GCD) to rotate an array.

Focus on how sets are formed and elements moved.

Practice

1. What does rotating an array to the left by 1 position do to the elements?

easy

A. Reverses the entire array

B. Moves the last element to the front and shifts others right by one

C. Moves the first element to the end and shifts others left by one

D. Sorts the array in ascending order

Solution

1. Step 1: Understand left rotation

   Left rotation by 1 means the element at index 0 moves to the end.

2. Step 2: Effect on array elements

   All other elements shift one position to the left.

3. Final Answer:

   Moves the first element to the end and shifts others left by one -> Option C

4. Quick Check:

   Left rotate 1 = first element to end [OK]

Hint: Left rotate by 1 moves front element to back [OK]

Common Mistakes:

• Confusing left rotation with right rotation
• Thinking rotation sorts the array
• Assuming rotation reverses the array

2. Which of the following Go code snippets correctly rotates an array arr to the right by 1 position?

easy

A. arr = append(arr[len(arr)-1:], arr[:len(arr)-1])

B. arr = append(arr[1:], arr[0])

C. arr = append(arr[:len(arr)-1], arr[len(arr)-1])

D. arr = append([]int{arr[len(arr)-1]}, arr[:len(arr)-1]...)

Solution

1. Step 1: Understand right rotation by 1

   Right rotation by 1 moves last element to front.

2. Step 2: Check code correctness

   arr = append([]int{arr[len(arr)-1]}, arr[:len(arr)-1]...) prepends last element to the rest correctly using slicing and append.

3. Final Answer:

   arr = append([]int{arr[len(arr)-1]}, arr[:len(arr)-1]...) -> Option D

4. Quick Check:

   Right rotate 1 = last element front [OK]

Hint: Right rotate by 1 prepends last element [OK]

Common Mistakes:

• Using wrong slice indices
• Appending single element without slice expansion
• Confusing left and right rotation code

3. What is the output of the following Go code?

arr := []int{10, 20, 30, 40, 50}
k := 2
n := len(arr)
k = k % n
rotated := append(arr[n-k:], arr[:n-k]...)
fmt.Println(rotated)

medium

A. [40 50 10 20 30]

B. [30 40 50 10 20]

C. [20 30 40 50 10]

D. [50 10 20 30 40]

Solution

1. Step 1: Calculate effective rotation

   k=2, n=5, so k%5=2 means rotate right by 2.

2. Step 2: Perform rotation

   arr[n-k:] = arr[3:] = [40,50], arr[:n-k] = arr[:3] = [10,20,30]. Append gives [40,50,10,20,30].

3. Final Answer:

   [40 50 10 20 30] -> Option A

4. Quick Check:

   Right rotate 2 = last 2 front [OK]

Hint: Right rotate by k = last k elements front [OK]

Common Mistakes:

• Not using modulo for k
• Swapping slice indices incorrectly
• Confusing left and right rotation

4. Identify the error in this Go code that attempts to left rotate an array by 3 positions:

arr := []int{1, 2, 3, 4, 5}
k := 3
rotated := append(arr[k:], arr[k:]...)
fmt.Println(rotated)

medium

A. The slice is appended twice from the same index, missing first part

B. The variable k is not used correctly for rotation

C. The array length is not considered for rotation

D. The append function is used incorrectly without slice expansion

Solution

1. Step 1: Analyze append arguments

   Both slices are arr[k:], so elements from index 3 to end repeated twice.

2. Step 2: Identify missing part

   Left rotation requires appending arr[:k] after arr[k:], but code repeats arr[k:] instead.

3. Final Answer:

   The slice is appended twice from the same index, missing first part -> Option A

4. Quick Check:

   Left rotate needs arr[k:] + arr[:k] [OK]

Hint: Append arr[k:] then arr[:k] for left rotation [OK]

Common Mistakes:

• Appending same slice twice
• Ignoring first k elements in rotation
• Not using slice expansion operator

5. Given an array arr = []int{5, 10, 15, 20, 25, 30}, how would you rotate it left by 4 positions using Go slices? Choose the correct code snippet.

hard

A. rotated := append(arr[:4], arr[4:]...)

B. rotated := append(arr[4:], arr[:4]...)

C. rotated := append(arr[len(arr)-4:], arr[:len(arr)-4]...)

D. rotated := append(arr[len(arr)-4:], arr[len(arr)-4:]...)

Solution

1. Step 1: Understand left rotation by 4

   Left rotation by 4 moves first 4 elements to the end.

2. Step 2: Use slicing correctly

   arr[4:] gives elements from index 4 to end, arr[:4] gives first 4 elements. Append arr[4:] + arr[:4] rotates left by 4.

3. Final Answer:

   rotated := append(arr[4:], arr[:4]...) -> Option B

4. Quick Check:

   Left rotate 4 = arr[4:] + arr[:4] [OK]

Hint: Left rotate k = arr[k:] + arr[:k] [OK]

Common Mistakes:

• Swapping slice order
• Using wrong slice indices
• Confusing left and right rotation