In this post we will be solving the HackerRank Largest Permutation problem using the Java programming language, the VSCode IDE and a Windows computer.
You are given an unordered array of `unique integers` incrementing from 1. You can swap any two elements a limited number of times. Determine the largest lexicographical value array that can be created by executing `no more` than the limited number of swaps. Constraints o 1 <= n <= 10^5 o 1 <= k <= 10^9
We are given a list of unique integers incrementing from 1. We can swap two values at a time up to a number `k`. We need to return the largest possible permutation in the list.
Please take a few moments to read the requirements and make sure you understand them and what data is being provided.
public static List<Integer> largestPermutation(int k, List<Integer> arr) {
}
The signature for the function of interest indicates that we are provided a list of integers `arr` (should have been named `lst` or something along those lines), and an int `k`. Our function needs to return a list as indicated in the requirements.
Since I am going to develop the code on my computer, I will need to generate a simple test scaffold which will read the input arguments, populate the necessary variables, call the function of interest, and display the result. Please note that the test scaffold IS NOT PART OF THE SOLUTION. The simplest approach is to use the online IDE provided by HackerRank.
5 1 4 2 3 5 1 main <<< n: 5 main <<< k: 1 main <<< arr: [4, 2, 3, 5, 1] main <<< largestPermutation0: [5, 2, 3, 4, 1] main <<< largestPermutation: [5, 2, 3, 4, 1] 3 1 2 1 3 main <<< n: 3 main <<< k: 1 main <<< arr: [2, 1, 3] main <<< largestPermutation0: [3, 1, 2] main <<< largestPermutation: [3, 1, 2] 2 1 2 1 main <<< n: 2 main <<< k: 1 main <<< arr: [2, 1] main <<< largestPermutation0: [2, 1] main <<< largestPermutation: [2, 1]
Each test case is separated by two blank lines from others.
The first two lines of each test case are input lines.
Our test code reads the lines, populates some variables and displays their contents. This is done to make sure all is well before the function of interest is called.
There are two implementations of the function of interest. The first missed to pass test case 15. The second implementation passed all test cases.
/**
* Test scaffold
*
* !!! NOT PART OF THE SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read n and k ****
int[] nk = Arrays.stream(br.readLine().trim().split(" "))
.map(s -> s.trim())
.mapToInt(Integer::parseInt)
.toArray();
// **** for ease of use ****
var n = nk[0];
var k = nk[1];
// **** read list<Integer> arr ****
List<Integer> arr = Arrays.stream(br.readLine().trim().split(" "))
.map(Integer::parseInt)
.collect(Collectors.toList());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
System.out.println("main <<< k: " + k);
System.out.println("main <<< arr: " + arr.toString());
// **** copy (deep) arr list ****
List<Integer> cal = arr.stream()
.collect(Collectors.toList());
// **** call function of interest and display result ****
System.out.println("main <<< largestPermutation0: " + largestPermutation0(k, arr));
// **** restore arr list ****
arr = cal.stream()
.collect(Collectors.toList());
// **** call function of interest and display result ****
System.out.println("main <<< largestPermutation: " + largestPermutation(k, arr));
}
The test scaffold seems to follow closely the description of the test cases. AT this time I have nothing else to add. That said; if you have comments or questions please do not hesitate and leave me a message below.
/**
* Determine the largest lexicographical value array that can be created
* by executing `no more` than the limited number of swaps.
*
* Timed out on test case 15 :o(
*/
public static List<Integer> largestPermutation0(int k, List<Integer> arr) {
// **** initialization ****
var n = arr.size();
// **** sanity checks ****
if (n == 1) return arr;
if (k >= n) {
Collections.sort(arr, Collections.reverseOrder());
return arr;
}
// **** remaining largest value ****
var largest = n;
// **** loop swapping elements ****
for (var c = 0; k > 0 && c < n - 1; c++) {
// **** get index of largest element ****
var l = arr.indexOf(largest--);
// **** skip this swap ****
if (c == l) continue;
// ???? ????
// System.out.println("<<< swap c: " + c + " l: " + l);
// **** swap elements ****
Collections.swap(arr, l, c);
// ???? ????
// System.out.println("<<< arr: " + arr.toString());
// **** count this permutation ****
k--;
}
// **** return updated list ****
return arr;
}
This implementation passed all test cases except test case #15. It timed out.
The approach is relatively simple.
The main loop swaps elements counting the number of swaps by decrementing `k`.
Have not much to add at this time.
/**
* Determine the largest lexicographical value array that can be created
* by executing `no more` than the limited number of swaps.
*
* Passed all test cases :o)
*/
public static List<Integer> largestPermutation(int k, List<Integer> arr) {
// **** initialization ****
var n = arr.size();
// **** sanity checks ****
if (n == 1) return arr;
if (k >= n) {
Collections.sort(arr, Collections.reverseOrder());
return arr;
}
// **** position of numbers in list ****
int[] position = new int[n + 1];
for (var i = 0; i < arr.size(); i++)
position[arr.get(i)] = i;
// ???? ????
// System.out.println("<<< position: " + Arrays.toString(position));
// **** loop swapping list entries (as needed) ****
for (int i = n; k > 0 && i > 0; --i) {
// **** actual position of `i` ****
var actualPos = position[i];
// **** expected position for `i` ****
var expectedPos = n - i;
// ???? ????
// System.out.println("<<< i: " + i + " in actualPos: " + actualPos + " expectedPos: " + expectedPos);
// **** check if i'th value is in the expected place ****
if (actualPos != expectedPos) {
// **** swap list elements ****
Collections.swap(arr, actualPos, expectedPos);
// ???? ????
// System.out.println("<<< arr: " + arr.toString());
// **** update positions ****
position[arr.get(actualPos)] = actualPos;
position[arr.get(expectedPos)] = expectedPos;
// ???? ????
// System.out.println("<<< position: " + Arrays.toString(position));
// **** account for this swap ****
k--;
}
}
// **** return modified list ****
return arr;
}
This implementation passed all test cases.
It starts by performing some sanity checks.
It then populates an int[] array `position` (perhaps I should have named it `positions`) which is used to track the positions of the integer values. We could have set the count to `n` but decided to use `n + 1` to eliminate the need to index values having to subtract 1.
The main loop starts with the integer with the highest value which in this case should be `n` given that the requirements call for values in the [1:n] range.
We then compute the actual and the expected positions of the value `i` in the list noting that the largest values should be on the left (or start) of the list `arr`.
If the positions do not match, we need to swap them to make them match our expectation.
We swap the values and then update the associated values in the `position` array.
Finally the variable `k` is decremented to account for the swap just completed.
When all is said and done the function of interest returns the `arr` list.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named LargestPermutation.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John