Given a positive integer M and an array consisting of N distinct positive integers, the task is to remove the first M smallest elements from the array such that the relative order of the remaining element doesn’t alter.
Examples:
Input: M = 5, arr[] = {2, 81, 75, 98, 72, 63, 53, 5, 40, 92}
Output: 81 75 98 72 92
Explanation:
The first M(= 5) smallest element are {2, 5, 40, 53, 63}. After removing these elements the modified array is {81, 75, 98, 72, 92}.Input: M = 1, arr[] = {8, 3, 6, 10, 5}
Output: 8 6 10 5
Sorting-Based Approach: The given problem can be solved by pairing each array element with its index and then sort the array of pairs. Follow the steps below to solve the problem:
- Initialize a vector of pairs A and initialize A[i] as {arr[i], i}.
- Sort vector A[] by the first element of the pair.
- Sort the elements over the range [M, N – 1] by the second element of the pair.
- Now, iterate over the given range [M, N – 1] using the variable i and print the value of A[i].first as the resultant array element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the array after// removing the smallest M elementsvoid removeSmallestM(int arr[], int N, int M){ // Store pair of {element, index} vector<pair<int, int> > A; // Iterate over the range [0, N] for (int i = 0; i < N; i++) { A.emplace_back(arr[i], i); } // Sort with respect to the // first value sort(A.begin(), A.end()); // Sort from the index M to N - 1 // using comparator for sorting // by the second value sort(A.begin() + M, A.end(), [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; }); // Traverse from M to N - 1 for (int i = M; i < N; i++) { cout << A[i].first << " "; }}// Driver Codeint main(){ int M = 5; int arr[] = { 2, 81, 75, 98, 72, 63, 53, 5, 40, 92 }; int N = sizeof(arr) / sizeof(arr[0]); removeSmallestM(arr, N, M); return 0;} |
Python3
# Python3 program for the above approach# Function to print the array after# removing the smallest M elementsdef removeSmallestM(arr, N, M): # Store pair of {element, index} A = [] # Iterate over the range [0, N] for i in range(N): A.append([arr[i], i]) # Sort with respect to the # first value A = sorted(A) B = [] for i in range(M, N): B.append([A[i][1], A[i][0]]) B = sorted(B) # Traverse from M to N - 1 for i in range(len(B)): print(B[i][1], end = " ")# Driver Codeif __name__ == '__main__': M = 5 arr = [ 2, 81, 75, 98, 72, 63, 53, 5, 40, 92 ] N = len(arr) removeSmallestM(arr, N, M)# This code is contributed by mohit kumar 29 |
Javascript
<script>// JavaScript program for the above approach// Function to print the array after// removing the smallest M elementsfunction removeSmallestM(arr, N, M) { // Store pair of {element, index} let A = []; // Iterate over the range [0, N] for (let i = 0; i < N; i++) { A.push([arr[i], i]); } // Sort with respect to the // first value A.sort((a, b) => a[0] - b[0]); // Sort from the index M to N - 1 // using comparator for sorting // by the second value let B = []; for (let i = M; i < N; i++) { B.push([A[i][1], A[i][0]]) } B.sort((a, b) => a[0] - b[0]) for (let i = 0; i < B.length; i++) { document.write(B[i][1] + " ") }}// Driver Codelet M = 5;let arr = [2, 81, 75, 98, 72, 63, 53, 5, 40, 92];let N = arr.lengthremoveSmallestM(arr, N, M);</script> |
Java
import java.util.*; // class to represent the pair class Pair { public int first; public int second; public Pair(int first, int second) { this.first = first; this.second = second; } public int getKey() { return first; } public int getVal() { return second; }}class Main { // Function to print the array after // removing the smallest M elements public static void removeSmallestM(int[] arr, int N, int M) { // Store pair of {element, index} ArrayList<Pair> A = new ArrayList<>(); // Iterate over the range [0, N] for (int i = 0; i < N; i++) { A.add(new Pair(arr[i], i)); } // Sort with respect to the // first value Collections.sort(A, new Comparator<Pair>() { @Override public int compare(Pair a, Pair b) { return a.first - b.first; } }); // Sort from the index M to N - 1 // using comparator for sorting // by the second value Collections.sort(A.subList(M, N), new Comparator<Pair>() { @Override public int compare(Pair a, Pair b) { return a.second - b.second; } }); // Traverse from M to N - 1 for (int i = M; i < N; i++) { System.out.print(A.get(i).first + " "); } System.out.println(); } // Driver Code public static void main(String[] args) { int M = 5; int arr[] = { 2, 81, 75, 98, 72, 63, 53, 5, 40, 92 }; int N = arr.length; removeSmallestM(arr, N, M); }} |
C#
using System;using System.Linq;class Program { // Function to print the array after // removing the smallest M elements static void RemoveSmallestM(int[] arr, int N, int M) { // Store pair of {element, index} var A = new int[N][]; for (int i = 0; i < N; i++) { A[i] = new int[] { arr[i], i }; } // Sort with respect to the first value Array.Sort(A, (a, b) => a[0].CompareTo(b[0])); var B = new int[N - M][]; for (int i = M; i < N; i++) { B[i - M] = new int[] { A[i][1], A[i][0] }; } // Sort with respect to the first value Array.Sort(B, (a, b) => a[0].CompareTo(b[0])); // Traverse from M to N - 1 for (int i = 0; i < B.Length; i++) { Console.Write($"{B[i][1]} "); } } static void Main() { int M = 5; int[] arr = { 2, 81, 75, 98, 72, 63, 53, 5, 40, 92 }; int N = arr.Length; RemoveSmallestM(arr, N, M); }} |
Output:
81 75 98 72 92
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
HashMap-Based Approach: The given problem can also be solved using a HashMap to store the smallest M elements of the array. Follow the steps below to solve the problem:
- Initialize an auxiliary vector, say A, and store all the array element arr[] in it.
- Sort the vector A and initialize a HashMap, say mp.
- Iterate over the range [0, M – 1] using the variable i, and insert A[i] in the HashMap.
- Iterate over the range [0, N – 1] using the variable i, and if the value of arr[i] is not present in the HashMap then print the value of arr[i] as the resultant array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the array after// removing the smallest M elementsvoid removeSmallestM(int arr[], int N, int M){ // Stores the copy of arr vector<int> A(arr, arr + N); // Sort the vector in increasing // order sort(A.begin(), A.end()); // Stores the smallest M elements unordered_map<int, int> mp; for (int i = 0; i < M; i++) { // Insert A[i] in the map mp[A[i]] = 1; } for (int i = 0; i < N; i++) { // If current value is present // in the hashmap if (mp.find(arr[i]) == mp.end()) { // Print the value of // current element cout << arr[i] << " "; } }}// Driver Codeint main(){ int M = 5; int arr[] = { 2, 81, 75, 98, 72, 63, 53, 5, 40, 92 }; int N = sizeof(arr) / sizeof(arr[0]); removeSmallestM(arr, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static int[] reverse(int a[]) { int i, n = a.length, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a; } // Function to print the array after // removing the smallest M elements static void removeSmallestM(int arr[], int N, int M) { // Stores the copy of arr int[] A = new int[N]; for(int i = 0;i<N;i++) A[i] = arr[i]; // Sort the vector in increasing // order Arrays.sort(A); A = reverse(A); // Stores the smallest M elements Map<Integer,Integer> mp = new LinkedHashMap<Integer,Integer>(); for (int i = 0; i < M; i++) { // Insert A[i] in the map mp.put(A[i], 1); } for (int i = 0; i < N; i++) { // If current value is present // in the hashmap if (mp.containsKey(arr[i])) { // Print the value of // current element System.out.print(arr[i]+ " "); } } } // Driver Code public static void main(String[] args) { int M = 5; int arr[] = { 2, 81, 75, 98, 72, 63, 53, 5, 40, 92 }; int N = arr.length; removeSmallestM(arr, N, M); }}// This code is contributed by Rajput-Ji |
Python3
# Python Program for the above approach# Function to print the array after# removing the smallest M elementsdef removeSmallestM(arr, N, M) : # Stores the copy of arr A = arr.copy() # Sort the vector in increasing # order A.sort() # Stores the smallest M elements mp = {} for i in range(M) : # Insert A[i] in the map mp[A[i]] = 1 for i in range(N) : # If current value is present # in the hashmap if arr[i] not in mp : # Print the value of # current element print(arr[i], end = " ")# Driver CodeM = 5arr = [2, 81, 75, 98, 72, 63, 53, 5, 40, 92]N = len(arr)removeSmallestM(arr, N, M)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Linq;using System.Collections.Generic;class GFG { static void removeSmallestM(int[] arr, int N, int M) { // Stores the copy of arr int[] A = new int[N]; for(int i = 0; i < N ; i++){ A[i] = arr[i]; } // Sort the vector in increasing // order Array.Sort(A); // Stores the smallest M elements Dictionary<int,int> mp = new Dictionary<int, int>(); for (int i = 0; i < M; i++) { // Insert A[i] in the map mp[A[i]] = 1; } for (int i = 0; i < N; i++) { // If current value is not present // in the hashmap if (!mp.ContainsKey(arr[i])) { // Print the value of // current element Console.Write(arr[i] + " "); } } } // Driver Code public static void Main() { int M = 5; int[] arr = { 2, 81, 75, 98, 72, 63, 53, 5, 40, 92 }; int N = arr.Length; removeSmallestM(arr, N, M); }} |
Javascript
<script> // JavaScript Program for the above approach // Function to print the array after // removing the smallest M elements function removeSmallestM(arr, N, M) { // Stores the copy of arr let A = [...arr]; // Sort the vector in increasing // order A.sort(function (a, b) { return a - b; }) // Stores the smallest M elements let mp = new Map(); for (let i = 0; i < M; i++) { // Insert A[i] in the map mp.set(A[i], 1); } for (let i = 0; i < N; i++) { // If current value is present // in the hashmap if (mp.has(arr[i]) == false) { // Print the value of // current element document.write(arr[i] + " "); } } } // Driver Code let M = 5; let arr = [2, 81, 75, 98, 72, 63, 53, 5, 40, 92]; let N = arr.length; removeSmallestM(arr, N, M); // This code is contributed by Potta Lokesh</script> |
Output:
81 75 98 72 92
Time Complexity: O(N*log N), as we are sorting the array first so that required N*logN time
Auxiliary Space: O(M), as in solution we are using hashmap(unordered map) to store the first M element from the sorted array which means we store only M element in the hashmap(unordered map) so space complexity will be O(M).
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!
