Minimum number of Groups needed to convert the given Array to another Array-CodePudding

I have a given array with unique values say [1,4,3,2] and another desired array [1,2,4,3]

I want to cut this input array into a minimum number of pieces so I can convert that to the desired array by just re-arranging the cut pieces.

So for the input array [1,4,3,2] I can cut into pieces (1), (4,3), (2) and re-arrange like (1),(2),(4,3) to get the desired array [1,2,4,3]

Constraints:

Array values are unique. 
The size of both arrays is the same and can be up to 1000. 
Values in arrays are integers

So the answer is 3 pieces for this example.

Here is what I have tried:

public int process(int[] inp, int[] desired) {
   int ans = 0;
   for (int i = 0; i < inp.length; i  ) {
      if (inp[i] != desired[i]) ans  ;
   }
   return ans;
}

My approach is not a correct one, as I am finding elements at each index to count the mismatches. What is the correct approach for solving this problem?

CodePudding user response：

Since all elements in the given arrays are unique, we can store index the positions of elements in one of these arrays by generating a map of type Map<Integer,Integer> associating an array element (Key) with its index (Value).

Then iterate over the second array, searching for identical chunks.

For that, we need to maintain a variable prevIndex that would store the index occupied by the previous element in the first array. While iterating, we would need to check each next index in the first array (corresponding to the next element in the first array). If the next index differs from the previous only by one - the next element is proved to be a part of a chunk with identical order, and we're just incrementing prevIndex. Otherwise, increment the count of chunks.

public static int process(int[] arr1, int[] arr2) {
    Map<Integer, Integer> indexByValue = mapIndices(arr2);
    
    int count = 1;
    
    int prevIndex = indexByValue.get(arr1[0]);
    
    for (int i = 1; i < arr1.length; i  ) {
        int nextIndex = indexByValue.get(arr1[i]);
        if (nextIndex == prevIndex   1) {
            prevIndex  ;
        } else {
            prevIndex = nextIndex;
            count  ;
        }
    }
    
    return count;
}

public static Map<Integer, Integer> mapIndices(int[] arr) {
    
    return IntStream.range(0, arr.length)
        .boxed()
        .collect(Collectors.toMap(
            i -> arr[i],
            Function.identity()
        ));
}

main()

public static void main(String[] args) {
    System.out.println(process(new int[]{1, 4, 3, 2}, new int[]{1, 2, 4, 3}));
}

Output: