Minimum Swaps 2

Sort by

recency

|

2463 Discussions

|

  • + 0 comments
        // Intialize the Minimum Swaps Counter
        int swaps = 0;
    
        // Push all values in the Array to a List for Monitoring purposes
        // This List will be updated as and when the array elements get processed
        List<int> arrList = new List<int> (arr);
    
        // Create a List of Dictionaries for the previous index mapping to the new index
        List<Dictionary<int,int>> dictList = new List<Dictionary<int, int>>{};
    
        // Loop over all the elements in the Array
        // The List of Array elements will be checked here till any Array elements exist
        while (arrList.Count != 0)
        {
            // Find the index of the first element of the List from the Array
            var i = Array.IndexOf(arr, arrList[0]);
    
            // Initiate the Dictionary object that will be added to the Tracker List
            Dictionary<int, int> dict = new Dictionary<int, int>{};
            dictList.Add(dict);
    
            // Check if the Element is at the correct place
            while (arr[i] != i+1 && !dict.ContainsKey(i))
            {
                // Element not at correct place
                // Find the correct place of the element
                int newIndex = arr[i]-1;
    
                // Add the previous index mapped to the new index to the dictionary
                dict[i] = newIndex;
    
                // Remove the traversed index from the Array List
                arrList.Remove(arr[i]);
    
                // Continue with the next Index
                i = newIndex;
            }
    
            // Remove the last traversed index from the Array List
            arrList.Remove(arr[i]);
    
            // Check the Dictionary Keys created so far
            foreach (var k in dict.Keys)
            {
                Console.WriteLine("{0} --> {1}", k, dict[k]);
            }
    
            // Update the Minimum Swaps needed so far
            if (dict.Keys.Count != 0) { swaps = swaps + dict.Keys.Count-1; };
    
            Console.WriteLine();           
    
        // Return the Minimum Swaps Counter
        return swaps;
    }
    
  • + 0 comments

    Kotlin solution

    fun minimumSwaps(arr: Array<Int>): Int {
        val list = arr.toMutableList()
        var swapCount = 0
        for (i in arr.lastIndex downTo 0){
            val value = list[i]
            val sortedValue = (i + 1)
            if(value == sortedValue){
                list.removeLast()
                continue
            }
            
            val swapTargetIndex = list.indexOf(sortedValue)
            list[swapTargetIndex] = value
            list.removeLast()
            swapCount++
        }
        return swapCount
    }
    
  • + 0 comments

    Python solution with all the base conditions :

    def minimumSwaps(arr):
        
        arr_sorted = False
        current_pointer = 0
        swaps = 0
        
        while not arr_sorted :
            if (current_pointer == len(arr)) :
                arr_sorted = True
                break
            
            if (current_pointer+1 == arr[current_pointer]) :
                current_pointer += 1
            else :
                ind = arr[current_pointer] - 1
                arr[current_pointer], arr[ind] = arr[ind], arr[current_pointer]
                swaps += 1
            
        return swaps
    
  • + 1 comment
    def minimumSwaps(arr):
        i = 0
        swap = 0
        while i < len(arr):
            if arr[i] == i+1:
                i +=1
            else:
                index = arr[i] -1
                arr[i], arr[index] = arr[index], arr[i]
                swap += 1
        return swap
    
  • + 0 comments

    Java 7: Uses Selection sort which guarantees minimum number of swaps.

        static int minimumSwaps(int[] arr) {
            int swaps = 0;
            for(int i = 0; i < arr.length; i++) {
                int minimum = Integer.MAX_VALUE;
                int minimumIndex = -1;
                for(int j = i; j < arr.length; j++) {
                    if (arr[j] < minimum) { 
                        minimum = arr[j];
                        minimumIndex = j; 
                    }
                }
                if (arr[i] != minimum) {
                    int temp = arr[i];
                    arr[i] = arr[minimumIndex];
                    arr[minimumIndex] = temp;
                    swaps += 1;
                }
            }
            return swaps;
        }