Requirement : There's an input List and an input shift no. The first line contains two space-separated integers that denote :

• n, the number of integers, and
• d, the number of left rotations to perform.

The second line contains space-separated integers that describe arr[].

Constraints

• 1 <= n <= 10^5
• 1 <= d <= n
• 1 <= arr[i] <= 10^6

Sample Input

• 5 , 4
• 1 2 3 4 5

Sample Output

5 1 2 3 4

I have written this code which is working correctly but getting timeout while large operation. So I need to optimize my code to successfully run all the test cases. How to achieve that.

public static List<Integer> rotateLeft(int d, List<Integer> arr) {

    int size = arr.size();
    while(d>0) {
        int temp = arr.get(0);
        for(int i = 0; i<size; i  ){
            if(i != size-1){
                arr.set(i,arr.get(i 1));
            } else {
                arr.set(i,temp);
            }
        }
        d--;
    }
    
    return arr;

}

Failing for this input :

• n = 73642
• d = 60581
• And a huge Integer List of size 73642.

CodePudding user response：

Instead of using nested loops, this can be done in one loop. The final index of an element at index i after n shifts, can be calculated as (i n) % listLength, this index can be used to populate a shifted list. Like this:

import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(1,2,3,4,5);
        System.out.println(rotateLeft(4, arr));
    }
    
    public static List<Integer> rotateLeft(int d, List<Integer> arr) {
    List<Integer> rotatedList = new ArrayList<>(arr.size());
    int i=0;
    for(i=0; i< arr.size(); i  ) {
        int rotatedElementIndex = ((i d) % arr.size());
        rotatedList.add(arr.get(rotatedElementIndex));
    }
    return rotatedList;
  }
}

CodePudding user response：

Never liked hackerrank puzzles. What does "and a huge Integer array" mean? May we create a new list or we need to modify existing one? If we ought to modify existing one why our method is not void?

If we may create new list the optimal solution would be creating new Integer[] array and call System.arraycopy() twice.

In case of inline modifications the solution is:

    public static List<Integer> rotateLeft(int d, List<Integer> arr) {
        int i = 0, first = arr.get(0);
        int n = arr.size();
        while (true) {
            int source = (i   d) % n;
            if (source == 0) {
                arr.set(i, first);
                break;
            }
            arr.set(i, arr.get(source));
            i = source;
        }
        return arr;
    }

CodePudding user response：

For an in-place solution:

• reverse the subarrays arr[0, d) and arr[d, n) in-place. This is done by swapping the elements in symmetric pairs.

• reverse the whole array.

E.g., abcdefghijk, d=4

abcd|efghijk -> dcba|kjihgfe -> efghijk|abcd