Avoiding Time Limit Exceeded(TLE) is one of the most important aspects that we need to take care of while doing competitive coding as well as while answering questions on DSA during a technical PI. In this context, one commonly asked question across all coding platforms is sorting or problems that involve sorting. The following code is something I have devised while practicing Data Structures, and it linearly sorts a list of consecutive numbers starting from 1 in a minimum number of swaps and returns the value of the number of swaps done.
The concept behind the following code is that the correct position of a number in a sorted array is one less than the number itself, considering that the array index starts from 0. This is because the array only consists of consecutive numbers starting from one.
Illustration: Consider the following example: The given unsorted array is: 4 3 1 2 5.
Input: Below is a table of the array elements with their current position in the array (indicated by the indices in the first row).
|
0 |
1 |
2 |
3 |
4 |
|
4 |
3 |
1 |
2 |
5 |
Output: After sorting, the array is going to look as shown below. Thus, the correct position of the elements is nothing but an index of value one less than the number itself and hence all we need to do is put the respective elements at their correct indices which can be determined from the element value.
|
0 |
1 |
2 |
3 |
4 |
|
1 |
2 |
3 |
4 |
5 |
Approach:
- We start by inserting the given array elements into a HashMap where the key is the element and the value is the index indicating the current position.
- Then we run a for loop starting from the initial index value of the input array (i.e, 0) up-to a value one less than the size of the array.
- In every iteration, we check if the value at arr[i] is one more than ‘i’ or not.
- If so, it means that the element is at its right position, or else its position needs to be swapped with that of the element whose position it actually is (that element is nothing but (i+1)). Every time a swapping happens the variable meant for keeping count of the number of swaps is incremented by one.
- Then corresponding changes in the array due to swapping are updated in the HashMap as well.
Pictorial representation: Initially, the HashMap is as follows
| Element(Key) | Current Index(Value) |
|---|---|
|
4 |
0 |
|
3 |
1 |
|
1 |
2 |
|
2 |
3 |
|
5 |
4 |
After the first iteration, the HashMap will look like this
| Element(Key) | Current Index(Value) |
|
4 |
2 |
|
3 |
1 |
|
1 |
0 |
|
2 |
3 |
|
5 |
4 |
While the array becomes
|
0 |
1 |
2 |
3 |
4 |
|
1 |
3 |
4 |
2 |
5 |
Conclusion: Thus, after every swap one element gets placed at its correct position, and corresponding changes made to the hashmap ensure that the number of swaps is minimum.
Implementation:
Java
// Java Program to illustrate a Hack to Avoid TLE while// coding// Importing required librariesimport java.io.*;import java.math.*;import java.security.*;import java.text.*;import java.util.*;import java.util.concurrent.*;import java.util.regex.*;// Main Classclass GFG { // Method 1 // To find the minimum number of swaps required static int minimumSwaps(int[] arr) { // Declaring and initializing variables to 0 // Swap and Index variable int swap = 0, index = 0; // Creating object of HashMap class for storing // array elements along with corresponding current // position in the input array // Declaring both the objects if Integer type HashMap<Integer, Integer> index_table = new HashMap<>(); for (int i = 0; i < arr.length; i++) { index_table.put(arr[i], i); } // Loop variable beginning from 0 so the element // that should be present at index i after sorting // is, i+1 Hence we check if arr[i] is equal to i+1 // or not for (int i = 0; i < arr.length; i++) { // Condition check for figuring out correct // element if (arr[i] != (i + 1)) { // If the above condition is not fulfilled // i.e, if arr[i]!=i+1 that means the // correct element needs to be swapped with // the current one. // Find the index of the element i+1 from // the hashmap index = index_table.get(i + 1); // Swapping the element arr[index] = arr[i]; arr[i] = i + 1; // Variable keeping a count of the number of // swaps swap++; // Updating the hashmap index_table.put(arr[i], i); index_table.put(arr[index], index); } } // Returning the swap counts return swap; } // Scanner Class object to take input from user private static final Scanner scanner = new Scanner(System.in); // Method 2 // Main driver method public static void main(String[] args) throws IOException { // Creating an object of BufferedWriter to read // input for the use BufferedWriter bufferedWriter = new BufferedWriter( new FileWriter(System.getenv("OUTPUT_PATH"))); // Storing the non-primitive datatype // Here, Integer value int n = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); // Creating arrays // Array 1 // Creating an Integer array o size N int[] arr = new int[n]; // Array 2 // Creating an String array String[] arrItems = scanner.nextLine().split(" "); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int i = 0; i < n; i++) { int arrItem = Integer.parseInt(arrItems[i]); arr[i] = arrItem; } int res = minimumSwaps(arr); bufferedWriter.write(String.valueOf(res)); // Getting to new line bufferedWriter.newLine(); // No further input will be accepted // using the close() method bufferedWriter.close(); // Closing the inputs scanner.close(); }} |
Output:
Input:
4 3 1 2 5
Output:
3
