Array Rotation Techniques in DSA Typescript - 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 elements that go past the end back to the start.

beginner

Explain the difference between left rotation and right rotation of an array.

Left rotation moves elements towards the start of the array, pushing the first elements to the end. Right rotation moves elements towards the end, pushing the last elements to the start.

intermediate

What is the time complexity of rotating an array by d positions using the reversal algorithm?

The reversal algorithm rotates the array in O(n) time, where n is the length of the array, because it reverses parts of the array a few times but only once each element is touched.

intermediate

Describe the reversal algorithm for rotating an array to the left by d positions.

1. Reverse the first d elements.
2. Reverse the remaining elements.
3. Reverse the whole array.
This results in the array rotated left by d positions.

beginner

Why is using a temporary array to rotate an array less efficient in terms of space?

Using a temporary array requires extra space proportional to the number of positions rotated (d), which increases memory usage compared to in-place methods like the reversal algorithm.

What happens to the elements that move past the end of the array during rotation?

A They wrap around to the beginning of the array

B They are lost and removed

C They stay at the end and create empty spaces

D They are duplicated at the start

In array rotation, elements that move past the end wrap around to the start to keep the array size constant.

Which algorithm rotates an array in-place without extra space?

A Selection sort

B Using a temporary array

C Reversal algorithm

D Bubble sort

The reversal algorithm rotates the array in-place by reversing parts of the array without needing extra space.

If you rotate an array of length 7 by 10 positions to the left, how many effective rotations happen?

A 7

B 3

C 10

D 0

Rotating by more than the array length is the same as rotating by the remainder of division: 10 % 7 = 3.

Which of these is NOT a step in the reversal algorithm for left rotation?

A Reverse the first d elements

B Reverse the last n-d elements

C Reverse the entire array

D Sort the array

Sorting is unrelated to rotation; the reversal algorithm only involves reversing parts of the array.

What is the space complexity of rotating an array using a temporary array of size d?

A O(d)

B O(1)

C O(n)

D O(n*d)

Using a temporary array of size d requires O(d) extra space.

Explain how to rotate an array to the left by d positions using the reversal algorithm.

Think about reversing parts of the array step by step.

Describe the difference between rotating an array using a temporary array and using the reversal algorithm.

Consider space usage and how elements are moved.

Practice

1. What does rotating an array to the right by 1 position mean?
Example: [1, 2, 3, 4] rotated right by 1 becomes?

easy

A. [4, 1, 2, 3]

B. [2, 3, 4, 1]

C. [1, 2, 3, 4]

D. [3, 4, 1, 2]

Solution

1. Step 1: Understand right rotation

   Right rotation by 1 means the last element moves to the front, shifting others right.

2. Step 2: Apply to example array

   Last element 4 moves to front, rest shift right: [4, 1, 2, 3].

3. Final Answer:

   [4, 1, 2, 3] -> Option A

4. Quick Check:

   Right rotate by 1 = last element front [OK]

Hint: Right rotate by 1 means last element moves front [OK]

Common Mistakes:

• Confusing right rotation with left rotation
• Not moving the last element to front
• Shifting elements incorrectly

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

easy

A. arr.push(arr.shift()!)

B. arr.unshift(arr.pop()!)

C. arr.pop(); arr.unshift(arr.pop()!)

D. arr.shift(); arr.push(arr.shift()!)

Solution

1. Step 1: Understand left rotation by 1

   Left rotation by 1 means first element moves to the end.

2. Step 2: Check code snippets

   arr.push(arr.shift()!) uses arr.shift() to remove first element and arr.push() to add it at end, correct for left rotation.

3. Final Answer:

   arr.push(arr.shift()!) -> Option A

4. Quick Check:

   Left rotate = shift then push [OK]

Hint: Left rotate by 1 = remove first, add to end [OK]

Common Mistakes:

• Using pop instead of shift for left rotation
• Using unshift with pop for left rotation
• Calling shift or pop twice incorrectly

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

const arr = [10, 20, 30, 40, 50];
const k = 2;
const rotated = arr.slice(-k).concat(arr.slice(0, arr.length - k));
console.log(rotated);

medium

A. [50, 10, 20, 30, 40]

B. [40, 50, 10, 20, 30]

C. [20, 30, 40, 50, 10]

D. [30, 40, 50, 10, 20]

Solution

1. Step 1: Understand slicing for rotation

   arr.slice(-k) takes last 2 elements: [40, 50]. arr.slice(0, arr.length - k) takes first 3 elements: [10, 20, 30].

2. Step 2: Concatenate slices

   Concatenating gives [40, 50, 10, 20, 30], which is right rotation by 2.

3. Final Answer:

   [40, 50, 10, 20, 30] -> Option B

4. Quick Check:

   Right rotate by 2 = last 2 front [OK]

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

Common Mistakes:

• Using slice with wrong indices
• Confusing left and right rotation
• Not concatenating slices in correct order

4. Find the error in this TypeScript function that rotates an array to the left by k positions:

function rotateLeft(arr: number[], k: number): number[] {
  for (let i = 0; i < k; i++) {
    arr.push(arr.shift());
  }
  return arr;
}

medium

A. arr.push() should be arr.unshift()

B. Loop should run from i = 1 to k

C. arr.shift() can return undefined, causing push(undefined)

D. Function should return void, not number[]

Solution

1. Step 1: Check arr.shift() return type

   arr.shift() returns element or undefined if array empty. Here, no check for undefined.

2. Step 2: Effect on arr.push()

   If arr.shift() returns undefined, arr.push(undefined) adds undefined to array, causing incorrect result or runtime issues.

3. Final Answer:

   arr.shift() can return undefined, causing push(undefined) -> Option C

4. Quick Check:

   shift may be undefined, must check [OK]

Hint: Check shift() return before push to avoid undefined [OK]

Common Mistakes:

• Ignoring undefined from shift()
• Wrong loop range assumptions
• Confusing push and unshift methods

5. Given an array arr of length n, how can you rotate it to the left by k positions efficiently without using extra space? Choose the correct approach.

hard

A. Use a temporary array to store first k elements, then shift rest left, then copy temp at end

B. Sort the array and then rotate by k positions

C. Rotate one by one k times using shift and push

D. Reverse first k elements, reverse last n-k elements, then reverse whole array

Solution

1. Step 1: Understand in-place rotation using reversal

   Reversing parts of array and then whole array rotates left by k without extra space.

2. Step 2: Apply reversal steps

   Reverse first k elements, reverse last n-k elements, then reverse entire array to get rotated array.

3. Final Answer:

   Reverse first k, reverse last n-k, reverse whole array -> Option D

4. Quick Check:

   Reversal method = in-place left rotate [OK]

Hint: Use triple reversal for in-place left rotation [OK]

Common Mistakes:

• Using extra array when not needed
• Rotating one by one causing O(n*k) time
• Sorting array unrelated to rotation