CODEWITHSUNDEEP
javaarraylistcircular-buffer
Mondin Francisco Alegrid
Mondin Francisco Alegrid

Reputation: 119

Left circular rotate an ArrayList then get index of max element

I need to left circular rotate an arraylist based on each element of a second arraylist and then return another list that has the max element index of the rotated arraylist. (each rotation should be performed on the original arraylist formation)

For example i have this two arraylist : rotatelist[1,2,3,4] , rotate[1,2,3]

The flow would be:

rotatelist[1,2,3,4],rotate[1] -> [2,3,4,1] : max element index= 2

rotatelist[1,2,3,4],rotate[2] -> [3,4,1,2] : max element index= 1

rotatelist[1,2,3,4],rotate[3] -> [4,3,2,1] : max element index= 0

The code below works fine, but when a test case, which has both arraylist element size reach about 100,000 a "Terminated due to timeout" error always shows, because I'm running this on HackerRank

List<Integer> indices = new ArrayList<>(rotate.size());

for(int i=0;i<rotate.size();i++){
//rotate arraylist to the left
Collections.rotate(rotatelist,-rotate.get(i));

//get and insert max element index to array 
indices.add(rotatelist.indexOf(Collections.max(rotatelist)));

//rotate back to previous positions
Collections.rotate(rotatelist,rotate.get(i));           
}
return indices;

So is there another way to optimize the performance of this code?

Is using a traditional for loop better than using Collections.rotate() performance wise?

Upvotes: 2

Views: 2153

Answers (5)

vivek awasthi
vivek awasthi

Reputation: 11

You can use default function of the collections below is the sample code for 1 left rotation, similarly you can change the number for multiple rotations.

import java.util.*;  
Collections.rotate(mylist,-(1));

Upvotes: 0

Trang Nguyen
Trang Nguyen

Reputation: 21

Maybe you can try this solution

public static List<Integer> rotateLeft(int d, List<Integer> arr) {
// Get head of the rotated array
int head = -99;
    for(int i = 0; d >=0; i++){
        head = arr.get(i);
        if(i == arr.size()-1){
            i = -1;
        }   
        d--;   
    }
    // get elements from head to the end of the original array
    List<Integer>sub = arr.subList(arr.lastIndexOf(head),arr.size());

    // get elements from begginning to head
    List<Integer>remainder = arr.subList(0,arr.lastIndexOf(head));

    // concat them 
    List<Integer>newl = new ArrayList<Integer>(sub);
    newl.addAll(remainder);

    return newl;
}

Upvotes: 1

Bohemian
Bohemian

Reputation: 425278

Firstly, forget about actually rotating anything, and instead think about what happens to just one of the elements in particular - the largest one.

I don’t want to spoon feed you code. Instead, consider these ideas:

Find the largest element’s index, call it iMax.

The position of the largest element after rotating n is (iMax - n + array.length) % array.length.

If n can be less than zero or greater than array.length, you will need to bring it within that range by using the fact that for positive n, rotations of n and n % array.length give the same result.

You should be able to build some code around these ideas.

Upvotes: 3

dariosicily
dariosicily

Reputation: 4582

I tried the snippet code you posted as you can check from the above code:

package stackoverflow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class Rotate {

    public static void main(String[] args) {

        int[] a = { 1, 2, 3, 4};  
        List<Integer> rotatelist = Arrays.stream(a).boxed().collect(Collectors.toList());
        int[] b = { 1, 2, 3};  
        List<Integer> rotate = Arrays.stream(b).boxed().collect(Collectors.toList());
        List<Integer> maxindexes = maxIndexes(rotate, rotatelist);
        System.out.println(maxindexes);
    }

    public static List<Integer> maxIndexes(List<Integer> rotate, List<Integer> rotatelist) {
        List<Integer> indices = new ArrayList<>(rotate.size());

        for(int i=0;i<rotate.size();i++){
        //rotate arraylist to the left
        Collections.rotate(rotatelist,-rotate.get(i));

        //added to print rotated arrays
        System.out.println(rotatelist);

        //get and insert max element index to array 
        indices.add(rotatelist.indexOf(Collections.max(rotatelist)));

        //rotate back to previous positions
        Collections.rotate(rotatelist,rotate.get(i));           
        }
        return indices;
    }

}

You can check I used the instruction System.out.println(rotatelist) inside the method to print the rotated arrays and I obtained the following results:

rotatelist[1,2,3,4],rotate[1] -> [2,3,4,1] : max element index= 2

rotatelist[1,2,3,4],rotate[2] -> [3,4,1,2] : max element index= 1

rotatelist[1,2,3,4],rotate[3] -> [4,1,2,3] : max element index= 0 So the third array is [4, 1, 2, 3] (original array rotated of three positions) and not [4, 3, 2, 1].

A possible solution to the timeout problem you mentioned is about duplicating the original array: [1, 2, 3, 4] will be now [1, 2, 3, 4, 1, 2, 3, 4]. Now you can obtain the rotations of array [1, 2, 3, 4] iterating over the new duplicate array:

for rotate[0] = 1 the rotated array starts from index 1 of duplicated array [1, 2, 3, 4, 1, 2, 3, 4] and index = 1 and length = 4 -> [2, 3, 4, 1]

for rotate[1] = 2 the rotated array starts from index 2 of duplicated array [1, 2, 3, 4, 1, 2, 3, 4] and index = 2 and length = 4 -> [3, 4, 1, 2]

for rotate[2] = 3 the rotated array starts from index 2 of duplicated array [1, 2, 3, 4, 1, 2, 3, 4] and index = 3 and length = 4 -> [4, 1, 2, 3]

Upvotes: 0

Ivan
Ivan

Reputation: 8758

If you need to return only indexes of max element after each rotation then you do not need to actually rotate list. You can calculate index of max element in initial list and then use some Maths to just calculate to which index that existing index will be converted after rotation.

Upvotes: 2

Related Questions