Modify array by removing M smallest elements maintaining the order of remaining elements

0 0 9 minutes read

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 elements
void 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 Code
int 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 elements
def 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 Code
if __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 elements
function 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 Code
 
let M = 5;
let arr = [2, 81, 75, 98, 72,
    63, 53, 5, 40, 92];
let N = arr.length
removeSmallestM(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 elements
void 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 Code
int 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 approach
import 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 elements
def 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 Code
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 gfgking

C#

// C# program for the above approach
 
using 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 zambiatek!