Rotate Array

PROBLEM

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

Example 1

*Input*: nums = [1,2,3,4,5,6,7], k = 3
*Output*: [5,6,7,1,2,3,4]
*Explanation*:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2

*Input*: nums = [-1,-100,3,99], k = 2
*Output*: [3,99,-1,-100]
*Explanation*:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

SOLVING

We’ll use the Two Pointers method

TimeComplexity - O(N)
SpaceComplexity - O(1)

k must be equal k modulo array length, otherwise ERROR !!

Steps

Place Your Pointers

k equal to k % size | 3 % 7 = 3
Left Pointer to size - k | 7 - 3 = 4
Right Pointer to the last element nums.size() - 1 = 6

	     L     R
	     ↓     ↓
[1, 2, 3, 4, 5, 6, 7]

Reverse Right Part

	     L     R
	     ↓     ↓
[1, 2, 3, 4, 7, 6, 5]
		L
		R
		↓
[1, 2, 3, 4, 7, 6, 5]

Reverse Left Part

Left Pointer equal 0
Right Pointer equal to size - k - 1 = 3

 L        R
 ↓        ↓
[1, 2, 3, 4, 7, 6, 5]
 L        R
 ↓        ↓
[4, 2, 3, 1, 7, 6, 5]
    L  R
    ↓  ↓
[4, 2, 3, 1, 7, 6, 5]

[4, 3, 2, 1, 7, 6, 5]

Reverse The List

Left Pointer equal to 0
Right Pointer equal to last element

 L                 R
 ↓                 ↓
[4, 3, 2, 1, 7, 6, 5]
    L           R
    ↓           ↓
[5, 3, 2, 1, 7, 6, 4]
       L     R
       ↓     ↓
[5, 6, 2, 1, 7, 3, 4]
	  R
	  L
	  ↓
[5, 6, 7, 1, 2, 3, 4]

Code

class Solution {
public:
  void rotate(vector<int> &nums, int k) {
    int size = nums.size();

    if (size == 1)
      return;

    // Very Important
    k = k % size;
    int last = size - k;
    int leftPtr = last, rightPtr = size - 1;

    // First, Reverse Right Part
    for (; leftPtr <= rightPtr; leftPtr++) {
      swap(nums[leftPtr], nums[rightPtr]);
      rightPtr--;
    }

    // Second, Reverse Left Part
    rightPtr = last - 1;
    for (leftPtr = 0; leftPtr <= rightPtr; leftPtr++) {
      swap(nums[leftPtr], nums[rightPtr]);
      rightPtr--;
    }

    // Reverse Array
    rightPtr = size - 1;
    for (leftPtr = 0; leftPtr <= rightPtr; leftPtr++) {
      swap(nums[leftPtr], nums[rightPtr]);
      rightPtr--;
    }
  }
};