Array Rotation in DSA with Free Explanation

Concept – Array Rotation in DSA

Array Rotation in DSA involves shifting the elements of an array either to the left or right by a specified number of positions.

Example:

Consider an array,

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

• Left Rotation by 2:
  • Result: [3, 4, 5, 1, 2]
• Right Rotation by 2:
  • Result: [4, 5, 1, 2, 3]

Approach:

1. Naive Approach (One by One Rotation):
   • For a left rotation, move the first element to the end and shift all others one position left.
   • Repeat this process d times for d rotations.
2. Efficient Approach (Reversal Algorithm):
   • Left Rotation:
     • Reverse the first d elements.
     • Reverse the remaining n-d elements.
     • Reverse the entire array.
   • Right Rotation:
     • Reverse the entire array.
     • Reverse the first d elements.
     • Reverse the remaining n-d elements.

Time Complexity:

• Naive Approach: O(n×d)
• Reversal Algorithm: O(n)

Visual Explanation

Example Array: A = [1, 2, 3, 4, 5]

Left Rotation by 2 using Reversal Algorithm:

• Step 1: Reverse the first d=2 elements.
  • Reverse [1, 2] → [2, 1]
  • Array becomes: [2, 1, 3, 4, 5]
• Step 2: Reverse the remaining n-d=3 elements.
  • Reverse [3, 4, 5] → [5, 4, 3]
  • Array becomes: [2, 1, 5, 4, 3]
• Step 3: Reverse the entire array.
  • Reverse [2, 1, 5, 4, 3] → [3, 4, 5, 1, 2]
  • Final rotated array: [3, 4, 5, 1, 2]

Right Rotation by 2 using Reversal Algorithm:

• Step 1: Reverse the entire array.
  • Reverse [1, 2, 3, 4, 5] → [5, 4, 3, 2, 1]
  • Array becomes: [5, 4, 3, 2, 1]
• Step 2: Reverse the first d=2 elements.
  • Reverse [5, 4] → [4, 5]
  • Array becomes: [4, 5, 3, 2, 1]
• Step 3: Reverse the remaining n-d=3 elements.
  • Reverse [3, 2, 1] → [1, 2, 3]
  • Final rotated array: [4, 5, 1, 2, 3]