Minimum operations required to sort the array
Given an array arr[], the task is to find the minimum operations required to sort the array in increasing order. In one operation, you can set each occurrence of one element to 0.
Examples:
Input: item[] = [4, 1, 5, 3, 2]
Output: 4
Explanation: Set arr[0], arr[1], arr[2], arr[3] = 0. Hence, the minimum operations required is 4.Input: item[] = [1, 3, 1, 3]
Output: 2
Explanation: Set arr[0] and arr[1] to 0. Array becomes = {0, 0, 0, 0}. Hence the minimum operations required is 2.
Approach: The problem can be solved based on the following idea:
In order to sort the array in increasing order, the condition a[i] ≤ a[i+1] must be followed at each and every instance. We iterate over the array and if we found the condition to be violating i.e. a[i] > a[i+1], So, in order to make a[i+1] greater, We will set all its previous non-zero elements to 0.
The previous element which has been assigned to zero will also set all its occurrences to zero.
Follow the steps mentioned below to implement the idea:
- Declare a map of int and vector which stores the index of each element.
- Declare queue which stores the count of previously non-zero elements for each index.
- Start iterating over the array and if a[i] > a[i+1], increase the count by the size of the queue (which is the count of non-zero elements appearing before it)
- Iterate over the queue till it becomes empty and set the occurrence of each element to zero which has previously set to zero.
- Return the count.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function for calculating // minimum opeartions int minimum_operations(vector< int >& arr, int n) { // Declare map for storing the index // of each element. map< int , vector< int > > mpp; for ( int i = 0; i < arr.size(); i++) { mpp[arr[i]].push_back(i); } // Declare queue which store the count // of previously non zero element. queue< int > q; set< int > st; // Count the total opeartions int count = 0; for ( int i = 0; i < n - 1; i++) { if (st.find(arr[i]) == st.end() && arr[i] != 0) { q.push(arr[i]); st.insert(arr[i]); } // If found the violating condition if (arr[i] > arr[i + 1]) { // Increase the count by the // previously non zero elements count += q.size(); while (!q.empty()) { int top = q.front(); q.pop(); if (mpp.find(top) != mpp.end()) { // Set all occurences of // previously assigned zero // elements to zero vector< int > idx = mpp[top]; for ( int i = 0; i < idx.size(); i++) { arr[idx[i]] = 0; } } } } } // Returning the count return count; } // Driver code int main() { vector< int > arr = { 4, 1, 5, 3, 2 }; int n = arr.size(); // Function call cout << minimum_operations(arr, n); return 0; } |
Python3
# Python implementation of above approach from collections import defaultdict # Function for calculating # minimum operations def minimum_operations(arr): # Declare defaultdict for storing the # index of each element mpp = defaultdict( list ) for i, x in enumerate (arr): mpp[x].append(i) # Declare a queue which stores the count # of previously non-zero elements q = [] st = set () # Count the total operations count = 0 for i in range ( len (arr) - 1 ): if arr[i] not in st and arr[i] ! = 0 : q.append(arr[i]) st.add(arr[i]) # If found the violating condition if arr[i] > arr[i + 1 ]: # Increase the count by the # previously non-zero elements count + = len (q) while q: top = q.pop( 0 ) if top in mpp: # Set all occurrences of previously # assigned zero elements to zero for idx in mpp[top]: arr[idx] = 0 # Returning the count return count # Driver code arr = [ 4 , 1 , 5 , 3 , 2 ] # Function call print (minimum_operations(arr)) # This Code is Contributed by Prasad Kandekar(prasad264) |
Java
import java.util.*; public class Main { // Function for calculating minimum operations public static int minimum_operations(List<Integer> arr, int n) { // Declare map for storing the index of each // element. Map<Integer, List<Integer> > mpp = new HashMap<>(); for ( int i = 0 ; i < arr.size(); i++) { int num = arr.get(i); if (!mpp.containsKey(num)) { mpp.put(num, new ArrayList<Integer>()); } mpp.get(num).add(i); } // Declare queue which store the count of previously // non zero element. Queue<Integer> q = new LinkedList<>(); Set<Integer> st = new HashSet<>(); // Count the total operations int count = 0 ; for ( int i = 0 ; i < n - 1 ; i++) { if (!st.contains(arr.get(i)) && arr.get(i) != 0 ) { q.offer(arr.get(i)); st.add(arr.get(i)); } // If found the violating condition if (arr.get(i) > arr.get(i + 1 )) { // Increase the count by the previously non // zero elements count += q.size(); while (!q.isEmpty()) { int top = q.poll(); if (mpp.containsKey(top)) { // Set all occurrences of previously // assigned zero elements to zero List<Integer> idx = mpp.get(top); for ( int j = 0 ; j < idx.size(); j++) { arr.set(idx.get(j), 0 ); } } } } } // Returning the count return count; } // Driver code public static void main(String[] args) { List<Integer> arr = new ArrayList<>(Arrays.asList( 4 , 1 , 5 , 3 , 2 )); int n = arr.size(); // Function call System.out.println(minimum_operations(arr, n)); } } |
Javascript
// Javascript implementation of above approach // Function for calculating // minimum opeartions function minimum_operations(arr) { // Declare map for storing the index // of each element. let mpp = new Map(); for (let i = 0; i < arr.length; i++) { let val = arr[i]; if (mpp.has(val)) { mpp.get(val).push(i); } else { mpp.set(val, [i]); } } // Declare queue which store the count // of previously non zero element. let q = []; let st = new Set(); // Count the total opeartions let count = 0; for (let i = 0; i < arr.length - 1; i++) { if (!st.has(arr[i]) && arr[i] !== 0) { q.push(arr[i]); st.add(arr[i]); } // If found the violating condition if (arr[i] > arr[i + 1]) { // Increase the count by the // previously non zero elements count += q.length; while (q.length > 0) { let top = q.shift(); if (mpp.has(top)) { // Set all occurences of // previously assigned zero // elements to zero let idx = mpp.get(top); for (let i = 0; i < idx.length; i++) { arr[idx[i]] = 0; } } } } } // Returning the count return count; } // Driver code let arr = [4, 1, 5, 3, 2]; console.log(minimum_operations(arr)); // This code is contributed by prasad264 |
C#
using System; using System.Collections.Generic; class Program { // Function for calculating minimum opeartions static int minimum_operations(List< int > arr, int n) { // Declare map for storing the index of each element Dictionary< int , List< int > > mpp = new Dictionary< int , List< int > >(); for ( int i = 0; i < arr.Count; i++) { if (!mpp.ContainsKey(arr[i])) { mpp[arr[i]] = new List< int >(); } mpp[arr[i]].Add(i); } // Declare queue which store the count of previously // non zero element Queue< int > q = new Queue< int >(); HashSet< int > st = new HashSet< int >(); // Count the total opeartions int count = 0; for ( int i = 0; i < n - 1; i++) { if (!st.Contains(arr[i]) && arr[i] != 0) { q.Enqueue(arr[i]); st.Add(arr[i]); } // If found the violating condition if (arr[i] > arr[i + 1]) { // Increase the count by the previously non // zero elements count += q.Count; while (q.Count > 0) { int top = q.Dequeue(); if (mpp.ContainsKey(top)) { // Set all occurences of previously // assigned zero elements to zero List< int > idx = mpp[top]; for ( int j = 0; j < idx.Count; j++) { arr[idx[j]] = 0; } } } } } // Returning the count return count; } // Driver code static void Main( string [] args) { List< int > arr = new List< int >{ 4, 1, 5, 3, 2 }; int n = arr.Count; // Function call Console.WriteLine(minimum_operations(arr, n)); } } |
4
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Contact Us