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 opeartionsint 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 codeint 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 approachfrom collections import defaultdict# Function for calculating # minimum operationsdef 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 codearr = [4, 1, 5, 3, 2]# Function callprint(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 opeartionsfunction 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 codelet 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)); }} |
Output
4
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!