We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Tutorials
  3. Cracking the Coding Interview
  4. Arrays: Left Rotation
  5. Discussions

Arrays: Left Rotation

  • avi_roychow + 4 comments

    Can any one please tell me why the below code is timing out for large data set:

    for(int j=0;j<k;j++)
        {
        for(int current=n-1;current>=0;current--)
        {
           if(current!=0)
           {
               if(temp!=0)
               {
                 
            a[current-1]= a[current-1]+temp;
                   temp= a[current-1]-temp;
                   a[current-1]=a[current-1]-temp;
               }
               else
               {
                   temp=a[current-1];
                   a[current-1]=a[current];//for the first time
                  
               }
            
           
           }
            else//when current reaches the first element
            {
                a[n-1]=temp;
                
            }  
        }
            
        }
        Console.WriteLine(string.Join(" ",a));
    • rishabh10 + 2 comments

      mine is also a brute force approach but it worked check it out if it helps you

      import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static int[] arrayLeftRotation(int[] a, int n, int k) {
       int temp,i,j;
        for(i=0;i<k;i++){
            temp=a[0];
            for(j=1;j<n;j++){
               a[j-1]=a[j]; 
            }
            a[n-1]=temp;
        }
      
        return a;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a[] = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
      
        int[] output = new int[n];
        output = arrayLeftRotation(a, n, k);
        for(int i = 0; i < n; i++)
            System.out.print(output[i] + " ");
      
        System.out.println();
      
    }
}
      • pateldeep18 + 0 comments
        int main(){
    int n; 
    int k; 
    int temp1, temp2;
    scanf("%d %d",&n,&k);
    
    int *a = malloc(sizeof(int) * n);
    for(int a_i = 0; a_i < n; a_i++){
       scanf("%d",&a[a_i]);
    }
    k = k %n;
    for(int a_i = 0; a_i < k; a_i++){
        temp1 = a[0];
        for(int i = 1; i < n; i++){
            a[i-1] = a[i];
        }
        a[n-1] = temp1;
    }

    for(int a_i = 0; a_i < n; a_i++){
       printf("%d ", a[a_i]);
    }
    
    return 0;
}

        my code is the same as yours but i still time in test case 8, why is that?

      • not_nigel + 0 comments

        You're not wrong but this solution is inefficient. You're solving it in O(((n-1) * k) + 2n). The solution below is in O(2n).

        private static void solution(int size, int shift, int[] arr) {

		int count = 0;

		for (int i = shift; i < size; i++) {
			System.out.print(arr[i]);
			System.out.print(" ");
			count++;
		}

		count = 0;

		for (int i = size - shift; i < size; i++) {
			System.out.print(arr[count]);
			if (i != size - 1)
				System.out.print(" ");
			count++;
		}
	}
    • ash_jo4444 + 2 comments

      I got a timeout error for TC#8 and #9 for the same logic in Python :(

      • Muthukumar_T + 1 comment

        i got time out for tc#8 in c why??????

        • val3rian + 0 comments

          Iterate over array only once

      • russelljuma + 0 comments

        No loops. Just split and reconnect. def rotLeft(a, d): b = [] b = a[d:len(a)] + a[0:d] return b

    • gdahis + 1 comment

      Because it is O(n*k), if you have a big n and a big k, it could timeout. See if you can think of an algorithm that would visit each array element only once and make it o(n). Also, is there any optimization you can make? For example: if k is bigger than n, then you don't need to do k rotations you just need to do k % n rotations and k will be much smaller, smaller than n. Example:

      [ 1, 2, 3, 4, 5 ]

      K=2, K=7=(1*5)+2, K=12=(2*5)+2, they are all equivant, leading the array to be:

      [3, 4, 5, 1, 2]

    • Nitin304 + 1 comment

      My Solution :

      public static int[] arrayLeftRotation(int[] a, int n, int k) {
      int[] b = new int[n];
        for(int i=0;i<n-k;i++){
            b[i] = a[k+i];
        }
       int l = 0;
        for(int i=n-k;i<n;i++){
            b[i] = a[l++];
        }
       return b; 
        
        
    }
      • hatem_ali64 + 1 comment
        [deleted]
        • amit_feb06 + 1 comment

          with one for loop i have subitted the code

          • eddiecrochet1994 + 0 comments

            Can I ask how you managed that?