Optimizing arrayRotateLeft method

Question

My method works but apparently for Hackerrank it's not fast enough when dealing with big numbers. How do I optimize it? n is the array size, k is the number of times the array's elements should be rotated left.

 public static int[] arrayLeftRotation(int[] a, int n, int k) {
        int[] holder = new int[n];
        for(int m=0; m<k; m++)
            {
      for(int b = 0; b<n; b++)
          {
          if(b==0) holder[n-1]=a[b];
          else holder[b-1]=a[b];
          }
          a = holder;
          holder = new int[n];
        }
        return a;
    }

Do you have to use an array? You could use a Deque and remove elements from the head and add it to the tail. If you require an array, then you should probably treat it as circular and have a pointer to the "first" element, and shift the pointer when rotating the array. — Jacob G.
– Jacob G., Commented Apr 7, 2017 at 3:53
Well the parameters need to stay the same and I need to return an array. — Bloodluster
– Bloodluster, Commented Apr 7, 2017 at 3:55
If you require to use array, I don't think your code need to optimize — Fady Saad
– Fady Saad, Commented Apr 7, 2017 at 3:56
Maybe something along the lines of System#arrayCopy or Arrays#copyOfRange could optimize your method if any of those methods are intrinsic. Otherwise I'd stick with StinePike's answer, as it's only O(n) instead of O(nk). — Jacob G.
– Jacob G., Commented Apr 7, 2017 at 3:59
Yea StinePike's answer was the best. I started it off with a while loop lol which was like O(n^2). Didn't think there'd be a O(n) solution. — Bloodluster
– Bloodluster, Commented Apr 7, 2017 at 4:07

stinepike · Accepted Answer · 2017-04-07 03:56:12Z

1

You can do something like following

public static int[] arrayLeftRotation(int[] a, int n, int k) {
    int[] b = new int[n]
    for(int i = 0; i<n; i++)
        b[i] = a[(i+k)%n]
    return b;
}

answered Apr 7, 2017 at 3:56

stinepike

54.9k14 gold badges95 silver badges116 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Bloodluster Over a year ago

dam so much shorter

stinepike Over a year ago

@Bloodluster.. it has to be faster for optimization not shorter . welcome to the SO. if you find any answer helpful you can upvote/accet it.

Community · Accepted Answer · 2017-05-23 12:02:11Z

1

I would prefer to implement this with System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length), and you can replace n with src.length. Something like,

public static int[] arrayLeftRotation(int[] src, int k) {
    int[] dest = new int[src.length];
    System.arraycopy(src, k, dest, 0, src.length - k);
    System.arraycopy(src, 0, dest, src.length - k, k);
    return dest;
}

You might also implement @StinePike's proposed solution in one line with an IntStream like

public static int[] arrayLeftRotation(int[] a, int k) {
    return IntStream.range(0, a.length).map(i -> a[(i + k) % a.length]).toArray();
}

edited May 23, 2017 at 12:02

CommunityBot

11 silver badge

answered Apr 7, 2017 at 4:04

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

1 Comment

Jacob G. Over a year ago

Would you be able to benchmark this against StinePike's answer? I'm curious to see if there's any difference.

Collectives™ on Stack Overflow

Optimizing arrayRotateLeft method

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related