Minimize operations to sort given array by swapping K and arr[i] if K is greater

0 0 6 minutes read

Given an array arr[] of N integers and an integer K, the task is to find the minimum number of operations required to sort the array in non-decreasing order such that in each operation any array element arr[i] can be swapped with K if the value of (arr[i] > K).

Examples:

Input: arr[] = {0, 2, 3, 5, 4}, K = 1
Output: 3
Explanation:
The given array can be sorted using the following steps:

For i = 1, since arr[1] > K, swapping the values of arr[1] and K. Hence, the array becomes {0, 1, 3, 5, 4} and value of K = 2.

For i = 2, since arr[2] > K, swapping the values of arr[2] and K. Hence, the array becomes {0, 1, 2, 5, 4} and value of K = 3.

For i = 3, since arr[3] > K, swapping the values of arr[3] and K. Hence, the array becomes {0, 1, 2, 3, 4} and value of K = 5.

After the above operations, the given array has been sorted.

Input: arr[] = {1, 3, 5, 9, 7}, K = 10
Output: -1

Approach: The given problem can be solved using a Greedy Approach, the idea is to minimize the value of arr[i] at each step for all i in the range [0, N – 1] which is the most optimal choice for the further array to be sorted. Therefore, if the value of arr[i] > K, swapping the values of arr[i] and K is the most optimal choice. Follow the steps below to solve the given problem:

Create a variable cnt, which stores the count of the operations performed. Initially cnt = 0.
Traverse the array arr[] using a variable i in the range [0, N-1] in increasing order of i.
For each index, if arr[i] > K, swap the value of K and arr[i] and increment the value of cnt by 1.
After every operation, check whether the array arr[] is sorted or not using the approach discussed in this article. If the array arr[] is sorted, return the value of cnt as the required answer.
If the array is not sorted after performing the above steps, the print -1.

Below is the implementation of the above approach:

C++

// C++ program of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of given operations in order to sort
// the array arr[] in non-decreasing order
int minimumswaps(int arr[], int N, int K)
{
    // If arr[] is already sorted, return 0
    if (is_sorted(arr, arr + N)) {
        return 0;
    }
 
    // Stores the count of operations
    int cnt = 0;
 
    // Loop to iterate over the array
    for (int i = 0; i < N; i++) {
 
        // If arr[i] is greater than K,
        // minimize the value of arr[i]
        if (arr[i] > K) {
            swap(arr[i], K);
 
            // Increment the count by 1
            cnt++;
 
            // Check if the array is sorted
            // after the last operation
            if (is_sorted(arr, arr + N)) {
 
                // Return answer
                return cnt;
            }
        }
    }
 
    // Not Possible to sort the array using
    // given operation, hence return -1
    return -1;
}
 
// Driver Code
int main()
{
    int arr[] = { 0, 2, 3, 5, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 1;
 
    cout << minimumswaps(arr, N, K);
 
    return 0;
}

Java

// Java program of the above approach
import java.io.*;
class GFG
{
    static boolean is_sorted(int arr[], int N)
    {
        for (int i = 0; i < N - 1; i++)
        {
 
            if (arr[i] > arr[i + 1])
                return false;
        }
 
        return true;
    }
 
    // Function to find the minimum number
    // of given operations in order to sort
    // the array arr[] in non-decreasing order
    static int minimumswaps(int arr[], int N, int K)
    {
       
        // If arr[] is already sorted, return 0
        if (is_sorted(arr, N)) {
            return 0;
        }
 
        // Stores the count of operations
        int cnt = 0;
 
        // Loop to iterate over the array
        for (int i = 0; i < N; i++) {
 
            // If arr[i] is greater than K,
            // minimize the value of arr[i]
            if (arr[i] > K) {
                int temp = arr[i];
                  arr[i] = K;
                  K = temp;
 
                // Increment the count by 1
                cnt++;
 
                // Check if the array is sorted
                // after the last operation
                if (is_sorted(arr, N)) {
 
                    // Return answer
                    return cnt;
                }
            }
        }
 
        // Not Possible to sort the array using
        // given operation, hence return -1
        return -1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 0, 2, 3, 5, 4 };
        int N = arr.length;
           int K = 1;
 
        System.out.println(minimumswaps(arr, N, K));
    }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python 3 program of the above approach
def is_sort(arr):
    for i in range(len(arr)-1):
        if arr[i]>arr[i+1]:
            return False
    return True
   
# Function to find the minimum number
# of given operations in order to sort
# the array arr[] in non-decreasing order
def minimumswaps(arr, N, K):
   
    # If arr[] is already sorted, return 0
    if is_sort(arr):
        return 0
 
    # Stores the count of operations
    cnt = 0
 
    # Loop to iterate over the array
    for i in range(N):
        # If arr[i] is greater than K,
        # minimize the value of arr[i]
        if(arr[i] > K):
            temp = arr[i]
            arr[i] = K
            K = temp
             
            # Increment the count by 1
            cnt += 1
 
            # Check if the array is sorted
            # after the last operation
            if is_sort(arr):
                # Return answer
                return cnt
 
    # Not Possible to sort the array using
    # given operation, hence return -1
    return -1
 
# Driver Code
if __name__ == '__main__':
    arr = [0, 2, 3, 5, 4]
    N = len(arr)
    K = 1
    print(minimumswaps(arr, N, K))
     
    # This code is contributed by bgangwar59.

C#

// C# program of the above approach
using System;
class GFG {
    static bool is_sorted(int[] arr, int N)
    {
        for (int i = 0; i < N - 1; i++) {
 
            if (arr[i] > arr[i + 1])
                return false;
        }
 
        return true;
    }
 
    // Function to find the minimum number
    // of given operations in order to sort
    // the array arr[] in non-decreasing order
    static int minimumswaps(int[] arr, int N, int K)
    {
 
        // If arr[] is already sorted, return 0
        if (is_sorted(arr, N)) {
            return 0;
        }
 
        // Stores the count of operations
        int cnt = 0;
 
        // Loop to iterate over the array
        for (int i = 0; i < N; i++) {
 
            // If arr[i] is greater than K,
            // minimize the value of arr[i]
            if (arr[i] > K) {
                int temp = arr[i];
                arr[i] = K;
                K = temp;
 
                // Increment the count by 1
                cnt++;
 
                // Check if the array is sorted
                // after the last operation
                if (is_sorted(arr, N)) {
 
                    // Return answer
                    return cnt;
                }
            }
        }
 
        // Not Possible to sort the array using
        // given operation, hence return -1
        return -1;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { 0, 2, 3, 5, 4 };
        int N = arr.Length;
        int K = 1;
 
        Console.WriteLine(minimumswaps(arr, N, K));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
        function is_sorted(arr, N) {
            for (let i = 0; i < N - 1; i++) {
 
                if (arr[i] > arr[i + 1])
                    return false;
            }
 
            return true;
        }
 
        // Function to find the minimum number
        // of given operations in order to sort
        // the array arr[] in non-decreasing order
        function minimumswaps(arr, N, K)
        {
         
            // If arr[] is already sorted, return 0
            if (is_sorted(arr, N)) {
                return 0;
            }
 
            // Stores the count of operations
            let cnt = 0;
 
            // Loop to iterate over the array
            for (let i = 0; i < N; i++) {
 
                // If arr[i] is greater than K,
                // minimize the value of arr[i]
                if (arr[i] > K) {
                    let temp = arr[i];
                    arr[i] = K;
                    K = temp;
 
                    // Increment the count by 1
                    cnt++;
 
                    // Check if the array is sorted
                    // after the last operation
                    if (is_sorted(arr, N)) {
 
                        // Return answer
                        return cnt;
                    }
                }
            }
 
            // Not Possible to sort the array using
            // given operation, hence return -1
            return -1;
        }
 
        // Driver Code
        let arr = [0, 2, 3, 5, 4];
        let N = arr.length;
        let K = 1;
 
        document.write(minimumswaps(arr, N, K));
 
     // This code is contributed by Potta Lokesh
 
    </script>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!