Minimum operations required to Sort the Array using following operations - Coding

Given an array arr[] of size N. Make the array arr[] sorted in non-decreasing order in the minimum number of operations where you can choose any integer x and replace elements arr[i] == x equal to 0 for,
0 ? i ? N – 1.

Examples:

Input: n = 3, arr[] = {3, 3, 2}
Output: 1
Explanation: If you choose x = 3 then after one operation array will become {0, 0, 2} which is sorted in non-decreasing order.

Input: n = 4, arr[] = {2, 4, 1, 2}
Output: 3
Explanation: First you can choose x = 2 then after one operation array will become {0, 4, 1, 0} and in the second operation you can choose x = 1 then after the operation array will become {0, 4, 0, 0} and at last you can choose x = 4 and the array will become {0, 0, 0, 0} which is sorted in non-decreasing order.

Approach: The problem can be solved based on the following idea:

This problem can be solved using a greedy approach. We know that an array is sorted in non-decreasing order if arr[i] <= arr[i+1] for all i. So as we get arr[i] > arr[i+1] then we have to set x = arr[i]. So, the optimal idea is to traverse the array from the end and mark the index for which arr[i] > arr[i+1] and then count the different elements till that index.

Follow the below steps to implement the idea:

Find the last index from the end such that arr[i] > arr[i + 1].
If the array is already sorted then return 0.
Else make a visit[] of size n+1 which will be true only for those elements which should be zero to make the array sorted.
To fill the visit[] we will run a loop from the end of the arr array and mark all the indexes till the last index as true and then from the last index+1 to n-index iterate the arr array and mark the vis index as true for which the element already exists.
Now count the all true elements of the vis vector and return the answer.

Below is the implementation for the above approach:

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum operations
// to sort the array
int minMoves(int n, int arr[])
{
 
    // Variable to store the idx for which
    // arr[i] > arr[i + 1]
    int last = -1;
    for (int i = n - 2; i >= 0; i--) {
 
        if (arr[i] > arr[i + 1]) {
            last = i;
            break;
        }
    }
 
    // If no such element found then return 0
    if (last == -1) {
        return 0;
    }
 
    // Make a visit vector to store which
    // elements we need to make zero
    bool visit[n + 1];
 
    // Initially make all the elements as false
    for (int i = 1; i < n + 1; i++) {
 
        visit[i] = false;
    }
 
    // Mark the elements till the last index
    // as true
    for (int i = 0; i <= last; i++) {
 
        visit[arr[i]] = true;
    }
 
    // After the last index mark the index
    // last for which elements are repeating
    for (int i = last + 1; i < n; i++) {
 
        if (visit[arr[i]] == true) {
            last = i;
        }
    }
 
    // Again mark all the elements before
    // last index as true
    for (int i = last; i >= 0; i--) {
 
        visit[arr[i]] = true;
    }
 
    int ans = 0;
 
    // Count the number of elements which
    // are true in visit vector
    for (int i = 1; i <= n; i++) {
 
        if (visit[i] == true) {
            ans++;
        }
    }
 
    // Return the count
    return ans;
}
 
// Driver Code
int main()
{
 
    // Test Case 1
    int n = 3;
    int arr[] = { 3, 3, 2 };
 
    // Function call
    cout << minMoves(n, arr) << endl;
 
    // Test Case 2
    n = 4;
    int arr1[] = { 2, 4, 1, 2 };
 
    // Function call
    cout << minMoves(n, arr1) << endl;
    return 0;
}

Java

// Java code for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  // Function to find the minimum operations
  // to sort the array
  public static int minMoves(int n, int[] arr)
  {
    // Variable to store the idx for which
    // arr[i] > arr[i + 1]
    int last = -1;
    for (int i = n - 2; i >= 0; i--) {
      if (arr[i] > arr[i + 1]) {
        last = i;
        break;
      }
    }
 
    // If no such element found then return 0
    if (last == -1) {
      return 0;
    }
 
    // Make a visit vector to store which
    // elements we need to make zero
    boolean[] visit = new boolean[n + 1];
 
    // Initially make all the elements as false
    Arrays.fill(visit, false);
 
    // Mark the elements till the last index
    // as true
    for (int i = 0; i <= last; i++) {
      visit[arr[i]] = true;
    }
 
    // After the last index mark the index
    // last for which elements are repeating
    for (int i = last + 1; i < n; i++) {
      if (visit[arr[i]] == true) {
        last = i;
      }
    }
 
    // Again mark all the elements before
    // last index as true
    for (int i = last; i >= 0; i--) {
      visit[arr[i]] = true;
    }
 
    int ans = 0;
 
    // Count the number of elements which
    // are true in visit vector
    for (int i = 1; i <= n; i++) {
      if (visit[i] == true) {
        ans++;
      }
    }
 
    // Return the count
    return ans;
  }
 
  public static void main(String[] args)
  {
    // Test Case 1
    int n = 3;
    int[] arr = { 3, 3, 2 };
 
    // Function call
    System.out.println(minMoves(n, arr));
 
    // Test Case 2
    n = 4;
    int[] arr1 = { 2, 4, 1, 2 };
 
    // Function call
    System.out.println(minMoves(n, arr1));
  }
}
 
// This code is contributed by lokesh.

Python3

# Python code for the above approach
 
# Function to find the minimum operations
# to sort the array
def minMoves(n,arr):
    # Variable to store the idx for which
    # arr[i] > arr[i + 1]
    last=-1
    for i in range(n-2,-1,-1):
        if(arr[i]>arr[i+1]):
            last=i
            break
     
    # If no such element found then return 0
    if(last==-1):
        return 0
     
    # Make a visit vector to store which
    # elements we need to make zero
    visit=[True]*(n+1)
     
    # Initially make all the elements as false
    for i in range(1,n+1):
        visit[i]=False
     
    # Mark the elements till the last index
    # as true
    for i in range(0,last+1):
        visit[arr[i]]=True
     
    # After the last index mark the index
    # last for which elements are repeating
    for i in range(last+1,n):
        if(visit[arr[i]]==True):
            last=i
     
    # Again mark all the elements before
    # last index as true
    for i in range(last,-1,-1):
        visit[arr[i]]=True
     
    ans=0
     
    # Count the number of elements which
    # are true in visit vector
    for i in range(1,n+1):
        if(visit[i]==True):
            ans+=1
             
    # Return the count
    return ans
     
# Driver code
 
# Test Case 1
n=3
arr=[3,3,2]
 
# Function call
print(minMoves(n,arr))
 
# Test Case 2
n=4
arr=[2,4,1,2]
 
# Function call
print(minMoves(n,arr))
 
# This code is contributed by Pushpesh Raj.

C#

// C# code for the above approach
using System;
using System.Linq;
 
public class GFG {
 
  // Function to find the minimum operations
  // to sort the array
  public static int minMoves(int n, int[] arr)
  {
     
    // Variable to store the idx for which
    // arr[i] > arr[i + 1]
    int last = -1;
    for (int i = n - 2; i >= 0; i--) {
      if (arr[i] > arr[i + 1]) {
        last = i;
        break;
      }
    }
 
    // If no such element found then return 0
    if (last == -1) {
      return 0;
    }
 
    // Make a visit vector to store which
    // elements we need to make zero
    bool[] visit = new bool[n + 1];
 
    // Initially make all the elements as false
    for (int i = 0; i <= n; i++) {
      visit[i] = false;
    }
 
    // Mark the elements till the last index
    // as true
    for (int i = 0; i <= last; i++) {
      visit[arr[i]] = true;
    }
 
    // After the last index mark the index
    // last for which elements are repeating
    for (int i = last + 1; i < n; i++) {
      if (visit[arr[i]] == true) {
        last = i;
      }
    }
 
    // Again mark all the elements before
    // last index as true
    for (int i = last; i >= 0; i--) {
      visit[arr[i]] = true;
    }
 
    int ans = 0;
 
    // Count the number of elements which
    // are true in visit vector
    for (int i = 1; i <= n; i++) {
      if (visit[i] == true) {
        ans++;
      }
    }
 
    // Return the count
    return ans;
  }
 
  static public void Main()
  {
 
    // Code
    // Test Case 1
    int n = 3;
    int[] arr = { 3, 3, 2 };
 
    // Function call
    Console.WriteLine(minMoves(n, arr));
 
    // Test Case 2
    n = 4;
    int[] arr1 = { 2, 4, 1, 2 };
 
    // Function call
    Console.WriteLine(minMoves(n, arr1));
  }
}
 
// This code is contributed by lokeshmvs21.

Javascript

  // JS code to implement the approach
 
  // Function to find the minimum operations
  // to sort the array
  function minMoves(n, arr) {
 
    // Variable to store the idx for which
    // arr[i] > arr[i + 1]
    let last = -1;
    for (let i = n - 2; i >= 0; i--) {
 
      if (arr[i] > arr[i + 1]) {
        last = i;
        break;
      }
    }
 
    // If no such element found then return 0
    if (last == -1) {
      return 0;
    }
 
    // Make a visit vector to store which
    // elements we need to make zero
    let visit = new Array(n + 1).fill(0);
 
    // Initially make all the elements as false
    for (let i = 1; i < n + 1; i++) {
 
      visit[i] = false;
    }
 
    // Mark the elements till the last index
    // as true
    for (let i = 0; i <= last; i++) {
 
      visit[arr[i]] = true;
    }
 
    // After the last index mark the index
    // last for which elements are repeating
    for (let i = last + 1; i < n; i++) {
 
      if (visit[arr[i]] == true) {
        last = i;
      }
    }
 
    // Again mark all the elements before
    // last index as true
    for (let i = last; i >= 0; i--) {
 
      visit[arr[i]] = true;
    }
 
    let ans = 0;
 
    // Count the number of elements which
    // are true in visit vector
    for (let i = 1; i <= n; i++) {
 
      if (visit[i] == true) {
        ans++;
      }
    }
 
    // Return the count
    return ans;
  }
 
  // Driver Code
 
 
  // Test Case 1
  let n = 3;
  let arr = [3, 3, 2];
 
  // Function call
  console.log(minMoves(n, arr) + "<br>");
 
  // Test Case 2
  n = 4;
  let arr1 = [2, 4, 1, 2];
 
  // Function call
  console.log(minMoves(n, arr1) + "<br>");
 
// This code is contributed by Potta Lokesh

Output

1
3

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

Related articles:

Reffered: https://www.geeksforgeeks.org

DSA

Related
Implementation of Wu Manber Algorithm?
Maximum non overlapping Subset with sum greater than K
Check if given Array can be formed by increasing or decreasing element
Check if max sum of visible faces of N dice is at least X or not
Create Y[] by given Array X[] following given condition

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12