Problem statement

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

Solution

With extra space

The solution is quite simple. We can use a temporary array to store the elements that will be rotated. Then we can copy the elements from the temporary array to the original array.

Without extra space

The solution is quite simple. We can reverse the array. Then we can reverse the first k elements and the last n - k elements.

Code

With extra space

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

// rotate right
vector<int> rotate_arr_right(int k, vector<int> arr) {
  int len = arr.size();
  int finalShift = k % len;
  if (finalShift == 0)
    return arr;
  vector<int> newArr(len, 0);

  for (int i = 0, j = k; i < len; j = (j + 1) % len, i++) {
    newArr[j] = arr[i];
  }
  return newArr;
}

int main() {
  vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  vector<int> newArr = rotate_arr_right(3, arr);
  for (int i = 0; i < newArr.size(); i++) {
    printf("%d ", newArr[i]);
  }
  printf("\n");
  return 0;
}

Without extra space

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

void x_reverse(vector<int> &arr, int startIdx, int endIdx) {
  if (startIdx > endIdx || startIdx >= arr.size() || endIdx >= arr.size())
    throw invalid_argument("invalid index");
  if (endIdx - startIdx <= 1)
    return;
  while (startIdx <= endIdx) {
    int temp = arr[startIdx];
    arr[startIdx] = arr[endIdx];
    arr[endIdx] = temp;
    startIdx += 1;
    endIdx -= 1;
  }
}

void print_arr(vector<int> &arr) {

  for (int i = 0; i < arr.size(); i++) {
    printf("%d ", arr[i]);
  }
}

// rotate right without extra space
void rotate_arr(int k, vector<int> &arr) {
  int len = arr.size();
  int finalShift = k % len;
  printf("finalShift: %d\n", finalShift);
  if (finalShift == 0)
    return;
  // reverse full arr
  x_reverse(arr, 0, len - 1);
  //  print_arr(arr);
  // reverse again from 0 -> finalShift
  x_reverse(arr, 0, finalShift - 1);
  //  print_arr(arr);
  // reverse again from finalShift -> len
  x_reverse(arr, finalShift, len - 1);
  //  print_arr(arr);
}


int main() {
  vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  rotate_arr(3, arr);
  for (int i = 0; i < arr.size(); i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
  return 0;
}