Trusted answers to developer questions

Taimur Hassan

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

This problem requires us to shift/rotate a fixed-size array to the left by k positions, where k is a user-determined variable. For example, given an `array [1,2,3,4,5]`

, a shift of 3 positions should result in the final state of the array being `[4,5,1,2,3]`

. There are several different ways to achieve this.

One simple solution is to write an algorithm to shift/rotate the array once and then repeat this a total of k times.

Let's look at the code below:

#include <iostream> using namespace std; void shiftArr(int* arr , int n) { // Initially: [1 2 3 4 5] // swapping the first element with the last element int temp = arr[0]; arr[0] = arr[n-1]; arr[n-1] = temp; // Now: [5 2 3 4 1] // swapping the first element with the (N-i)th element for the entire length of the array (where i starts from 1) for(int i=n-2 ; i>=0 ; i--) { int temp2 = arr[0]; arr[0] = arr[i]; arr[i] = temp2; // Array in each iteration: // [4 2 3 5 1] // [3 2 4 5 1] // [2 3 4 5 1] } } void shiftArrByK(int* arr , int n , int k) { for(int i=0 ; i<k%n ; i++) // we take a modulus in case the value of k is >= N { shiftArr(arr , n) ; } } int main() { int arr[] = {1,2,3,4,5}; int size_of_array = 5 ; int k = 2 ; cout << "Before shifting: " ; for(int i=0 ; i<size_of_array ; i++) { cout << arr[i] << " " ; } cout << endl ; shiftArrByK(arr , size_of_array , k); cout << "After shifting: " ; for(int i=0 ; i<size_of_array ; i++) { cout << arr[i] << " " ; } cout << endl ; }

However, this is a very inefficient way to perform this task. In the worst case, it will take

A better approach would be one in which the number of times the elements need to be shifted is minimized. The diagram below depicts the algorithm implementing this approach with an example:

An algorithm to shift an array to the left k times (k=2 in this example)

Note:In this method, the maximum number of times that a single element is shifted is$2$ , whereas in the previous method, it was$N$ .

Let's implement this algorithm below:

#include <iostream> using namespace std; void reverseArray(int* arr , int low , int high) { while(low<high) { swap(arr[low] , arr[high]); low++; high--; } } void shiftLeftByN(int* arr , int n , int k) { k = k%n ; // we take a modulus in case the value of k is >= N reverseArray(arr , 0 , k-1); reverseArray(arr , k , n-1); reverseArray(arr , 0 , n-1); } int main() { int arr[5] = {1,2,3,4,5} ; int size_of_array=5 ; int k=2 ; cout << "Before rotation: " ; for(int i=0 ; i<size_of_array ; i++) { cout << arr[i] << " " ; } cout << endl ; shiftLeftByN(arr , size_of_array , k) ; cout << "After rotation: " ; for(int i=0 ; i<size_of_array ; i++) { cout << arr[i] << " " ; } cout << endl ; }

This method takes

RELATED TAGS

c++

python

CONTRIBUTOR

Taimur Hassan

Copyright Â©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring

Related Courses