Minimum Swaps 2

Sort by

recency

|

2464 Discussions

|

  • + 1 comment

    Python3 solution

    swaps = 0
    
    # track current positions separate from array
    current_positions = {value:position for position,value in enumerate(arr)}
    # +1 to indexes for intuitiveness
    for k in current_positions.keys():
        current_positions[k] += 1
    
    for p,v in enumerate(arr):
        if v != (p+1):
            # iterate from smallest to largest int
            # extract the position of the current int 
            # swap the positions in the dictionary
            # swap the numbers in the array to match -> ensures no missed swaps when iterating from smallest to largest
            current_position = current_positions[v] #returns index (plus 1)
            swapped_position = current_positions[(p+1)] #returns index (plus 1)
            current_positions[v], current_positions[(p+1)] = current_positions[(p+1)], current_positions[v]
            arr[(current_position-1)], arr[(swapped_position-1)] = arr[(swapped_position-1)], arr[(current_position-1)]
            swaps += 1
    
    return swaps
    
  • + 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