Whenever George asks Lily to hang out, she’s busy doing homework. George wants to help her finish it faster, but he’s in over his head! Can you help George understand Lily’s homework so she can hang out with him?
Consider an array of n distinct integers. George can swap any two elements of the array any number of times.
An array is beautiful if the sum of |arr[i] - arr[i-1]| among 0 < i < n is minimal.
Given the array arr, determine and return the minimum number of swaps that should be performed in order to make the array beautiful.
Input Format
The first line contains a single integer, n, the number of elements in arr. The second line contains n space-separated integers, arr[i].
Constraints
- 1<= n <= 100000
- 1 <= arr[i] <= 2 x pow(10, 9)
Explanation
So, basically what we need to do is to sort the array arr by swapping it’s element’s least number of times.
Link to the problem on hackerrank
Solution in java
import java.util.*;
class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] values = new long[n];
long[] reverse_values = new long[n];
for (int i = 0; i < n; i++) {
values[i] = sc.nextLong();
}
for (int i = n - 1, j = 0; i >= 0; i--, j++) {
reverse_values[j] = values[i];
}
System.out.println(Math.min(swaps(values), swaps(reverse_values)));
sc.close();
}
public static void swap(long[] array, int index1, int index2) {
long temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static int swaps(long[] unsorted_values) {
int num_of_swaps = 0;
Map<Long, Integer> locations = new HashMap<>();
for (int i = 0; i < unsorted_values.length; i++) {
locations.put(unsorted_values[i], i);
}
long[] sortedValue = unsorted_values.clone();
Arrays.sort(sortedValue);
for (int i = 0; i < sortedValue.length; i++) {
if (sortedValue[i] != unsorted_values[i]) {
num_of_swaps++;
int swapIndex = locations.get(sortedValue[i]);
locations.put(unsorted_values[i], swapIndex);
swap(unsorted_values, i, swapIndex);
}
}
return num_of_swaps;
}
}