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

  • amezolma + 2 comments

    Did something similar in C#..

    using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    
    static string rotate(int rot, int[] arr)
    {
        string left = string.Join(
            " ", arr.Take(rot).ToArray()
        );
        string right = string.Join(
            " ", arr.Skip(rot).ToArray()
        );
        return right + ' ' + left;
    }

    static void Main(String[] args) {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(tokens_n[0]);
        int k = Convert.ToInt32(tokens_n[1]);
        string[] a_temp = Console.ReadLine().Split(' ');        
        int[] a = Array.ConvertAll(a_temp,Int32.Parse);

        // rotate and return as string
        string result = Solution.rotate(k, a);
        // print result        
        Console.WriteLine(result);
    }
}
    • merkman + 2 comments

      Or you can one line it with LINQ

      Console.Write(string.Join(" ", a.Skip(k).Concat(a.Take(k)).ToArray()));

      • rahulbhansali + 1 comment

        While it is definitely elegant looking with a single line of code, how many times will this iterate over the array when performing 'skip', 'take' and 'concating' them? In other words, what's the complexity of this algorithm?

        • mihir7759 + 0 comments

          O(n)

      • jordandamman + 0 comments

        Any resources that explain how this works? I definitely see that it works, but say k is 5 in the first example and the array is 12345, it looks like we're skipping the whole array, then concatenating that whole array back to it with Take(5). What am I missing? Thank you for your time.

    • 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?