Array Rotation Techniques in DSA Go - Time & Space Complexity

Time Complexity: Array Rotation Techniques

O(n)

Understanding Time Complexity

When we rotate an array, we move elements around to new positions. Understanding how long this takes helps us choose the best method.

We want to know how the time needed changes as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func rotateArray(arr []int, k int) []int {
    n := len(arr)
    k = k % n
    rotated := make([]int, n)
    for i := 0; i < n; i++ {
        rotated[(i+k)%n] = arr[i]
    }
    return rotated
}
    

This code rotates an array to the right by k steps by creating a new array and placing elements at their new positions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through each element of the array once.
• How many times: Exactly n times, where n is the size of the array.

How Execution Grows With Input

As the array size grows, the number of steps grows directly with it.

Input Size (n)	Approx. Operations
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: Doubling the array size doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to rotate grows in direct proportion to the array size.

Common Mistake

[X] Wrong: "Rotating an array by k steps takes constant time because we only move k elements."

[OK] Correct: Even though k might be small, we must reposition every element to build the rotated array, so the work depends on the whole array size.

Interview Connect

Knowing how array rotation scales helps you explain your approach clearly and choose efficient methods in real coding tasks.

Self-Check

"What if we rotated the array in place without using extra space? How would the time complexity change?"

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