Saturday, March 11, 2023

Given an unsorted array arr[] of size N. Rotate the array to the left (counter-clockwise direction) by D steps, where D is a positive integer.

 Rotate the array to the left (counter-clockwise direction) by D steps in O(n) time

  1. Time complexity : O(n)
  2. Space Complexity : O(1)
If D is the number of steps and N is the number of element in the array. First find the D%N to reduce the number of steps. If D>N ,then we have to same steps D/N times. 

Now partition the array taking d as pivot. Reverse the array from arr[0] to arr[d-1] and arr[d] to arr[n-1]. 

Eg : If the array is 

1 2 3 4 5, where d=2 and n=5
after taking d as pivot the new array will be  2 1 5 4 3

Now reverse the whole array . Over all time complexity will be O(n)

_____________________
 static void rotateArr(int arr[], int d, int n)
    {
       
        d = d%n;
        
        int temp;
        
        for(int i=0;i<d/2;i++){
            temp = arr[i];
            arr[i] = arr[d-1-i];
            arr[d-1-i] = temp;
        }
        
        for(int i=d;i<(n+d)/2;i++){
            temp = arr[i];
            arr[i] = arr[n+d-1-i];
            arr[n+d-1-i] = temp;
        }
        
        for(int i=0;i<n/2;i++){
            temp = arr[i];
            arr[i] = arr[n-1-i];
            arr[n-1-i] = temp;
        }
        
        
    }
Rotate the array to the left (counter-clockwise direction) by D steps in O(n) time

 

No comments:

Post a Comment

Quick Sort in Java

 Quick Sort in Java Time complexity : O(n*n) - Worst case , O(nlogn) - Best Case Space complexity : O(logn) - height of recursion tree Best ...