Given a list of integers, the task is to generate another list with N minimum elements.
Examples:
Input: {23, 1, 6, 2, 90}
Output: {1, 2}
Input: {34, 21, 56, 42, 89, 90, -1}
Output: {-1, 21}
Approach: The idea is to use the concept used in Find the smallest and second smallest elements in an array.
- First, find the smallest number in the given list.
- Then add that current minimum element to another list that will contain the N minimum elements.
- Remove the current minimum element from the given list.
- Continue with the same process until the N minimum elements are found.
Below is the implementation of the above approach:
C++
// C++ program to find N // minimum elements#include <bits/stdc++.h>using namespace std;void Nminelements(vector<int>list1, int N){ vector<int> final_list; int n = list1.size(); for (int i = 0; i < N; i++) { int min1 = 9999999; for (int j = 0; j < n; j++) { if (list1[j] < min1) min1 = list1[j]; } // remove minimum element // from list so that it do // not come in calculation again list1.erase(remove(list1.begin(), list1.end(), min1), list1.end()); final_list.push_back(min1); } for(int i = 0; i < final_list.size(); i++) cout << final_list[i] << " ";} // Driver codeint main(){ vector<int> list1 = {4, 78, 34, 10, 8, 21, 11, 231}; int N = 2; Nminelements(list1, N);}// This code is contributed by Subhadeep |
Java
// Java program to find N// minimum elementsimport java.io.*;import java.util.*;class GFG{ static void Nminelements(ArrayList<Integer> list1, int N){ ArrayList<Integer> final_list = new ArrayList<Integer>(); for(int i = 0; i < N; i++) { int min1 = 9999999; int index = 0; for(int j = 0; j < list1.size(); j++) { if ((int)list1.get(j) < min1) { min1 = (int)list1.get(j); index = j; } } // Remove minimum element // from list so that it do // not come in calculation again list1.remove(index); final_list.add(min1); } for(int i = 0; i < final_list.size(); i++) System.out.print(final_list.get(i) + " ");} // Driver codepublic static void main (String[] args){ ArrayList<Integer> list1 = new ArrayList<Integer>( Arrays.asList(4, 78, 34, 10, 8, 21, 11, 231 )); int N = 2; Nminelements(list1, N);}}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program to find N minimum elementsdef Nminelements(list1, N): final_list =[]; for i in range(0, N): min1 = 9999999; for j in range(len(list1)): if list1[j]<min1: min1 = list1[j]; # remove minimum element from list so # that it do not come in calculation again list1.remove(min1); final_list.append(min1) print(final_list) # Driver codelist1 = [4, 78, 34, 10, 8, 21, 11, 231];N = 2;Nminelements(list1, N) |
C#
// C# program to find N// minimum elementsusing System;using System.Collections;class GFG{static void Nminelements(ArrayList list1, int N){ ArrayList final_list = new ArrayList(); for(int i = 0; i < N; i++) { int min1 = 9999999; for(int j = 0; j < list1.Count; j++) { if ((int)list1[j] < min1) min1 = (int)list1[j]; } // Remove minimum element // from list so that it do // not come in calculation again list1.Remove(min1); final_list.Add(min1); } for(int i = 0; i < final_list.Count; i++) Console.Write(final_list[i] + " ");}// Driver codepublic static void Main(){ ArrayList list1 = new ArrayList(){ 4, 78, 34, 10, 8, 21, 11, 231 }; int N = 2; Nminelements(list1, N);}}// This code is contributed by chitranayal |
Javascript
<script>// Javascript program to find N// minimum elementsfunction Nminelements(list1,N){ let final_list = []; for(let i = 0; i < N; i++) { let min1 = 9999999; let index = 0; for(let j = 0; j < list1.length; j++) { if (list1[j] < min1) { min1 = list1[j]; index = j; } } // Remove minimum element // from list so that it do // not come in calculation again list1.splice(index, 1); final_list.push(min1); } for(let i = 0; i < final_list.length; i++) document.write(final_list[i] + " ");}// Driver codelet list1=[4, 78, 34, 10, 8, 21, 11, 231 ];let N = 2;Nminelements(list1, N);// This code is contributed by rag2127</script> |
Output
4 8
Complexity Analysis:
- Time Complexity: O(n*n)
- Auxiliary Space: O(n)
Another approach we can use is heapq module in Python’s standard library to efficiently find the N minimum elements in the list.
The heapq module provides functions for implementing heap sort algorithms. A heap is a complete binary tree where the root node is the smallest element in the tree. By maintaining the list as a heap, we can repeatedly extract the smallest element from the heap and add it to the list of N minimum elements until we have found the desired number of minimum elements.
Here is an example of how this can be implemented:
C++
#include <iostream>#include <queue>#include <vector>std::vector<int> find_n_minimum(std::vector<int> lst, int n){ std::priority_queue<int, std::vector<int>, std::greater<int> > pq; for (int i = 0; i < lst.size(); i++) { pq.push(lst[i]); } std::vector<int> n_minimum; for (int i = 0; i < n; i++) { n_minimum.push_back(pq.top()); pq.pop(); } return n_minimum;}int main(){ std::vector<int> lst1 = { 23, 1, 6, 2, 90 }; std::vector<int> lst2 = { 34, 21, 56, 42, 89, 90, -1 }; std::vector<int> n_minimum1 = find_n_minimum(lst1, 2); std::vector<int> n_minimum2 = find_n_minimum(lst2, 2); for (int i = 0; i < n_minimum1.size(); i++) { std::cout << n_minimum1[i] << " "; } std::cout << std::endl; for (int i = 0; i < n_minimum2.size(); i++) { std::cout << n_minimum2[i] << " "; } std::cout << std::endl; return 0;}//Code contributed by dhanshriborse |
Java
// Java Code for the approachimport java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;public class GFG { public static List<Integer> findNMinimum(List<Integer> lst, int n) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int i = 0; i < lst.size(); i++) { pq.offer(lst.get(i)); } List<Integer> nMinimum = new ArrayList<>(); for (int i = 0; i < n; i++) { nMinimum.add(pq.poll()); } return nMinimum; } public static void main(String[] args) { List<Integer> lst1 = List.of(23, 1, 6, 2, 90); List<Integer> lst2 = List.of(34, 21, 56, 42, 89, 90, -1); List<Integer> nMinimum1 = findNMinimum(lst1, 2); List<Integer> nMinimum2 = findNMinimum(lst2, 2); for (int i = 0; i < nMinimum1.size(); i++) { System.out.print(nMinimum1.get(i) + " "); } System.out.println(); for (int i = 0; i < nMinimum2.size(); i++) { System.out.print(nMinimum2.get(i) + " "); } System.out.println(); }} |
Python3
import heapqdef find_n_minimum(lst, n): heapq.heapify(lst) # convert the list to a heap n_minimum = [] for i in range(n): n_minimum.append(heapq.heappop(lst)) # extract the smallest element from the heap return n_minimumprint(find_n_minimum([23, 1, 6, 2, 90], 2)) # [1, 2]print(find_n_minimum([34, 21, 56, 42, 89, 90, -1], 2)) # [-1, 21]#This code is contributed by Edula Vinay Kumar Reddy |
Javascript
function findNMinimum(lst, n) { lst.sort((a, b) => a - b); // sort the list in ascending order const nMinimum = []; for (let i = 0; i < n; i++) { nMinimum.push(lst[i]); // add the first n elements to the nMinimum array } return nMinimum;}console.log(findNMinimum([23, 1, 6, 2, 90], 2)); // [1, 2]console.log(findNMinimum([34, 21, 56, 42, 89, 90, -1], 2)); // [-1, 21] |
C#
using System;using System.Collections.Generic;class Program { // Function to find the n smallest elements in a vector static List<int> FindNMinimum(List<int> lst, int n) { // Create a priority queue with the smallest element // at the top PriorityQueue<int> pq = new PriorityQueue<int>(); // Add all elements of the vector to the priority // queue foreach(int num in lst) { pq.Enqueue(num); } // Create a new vector to store the n smallest // elements List<int> nMinimum = new List<int>(); // Pop the top n elements from the priority queue // and add them to the new vector for (int i = 0; i < n; i++) { nMinimum.Add(pq.Dequeue()); } return nMinimum; } static void Main(string[] args) { List<int> lst1 = new List<int>() { 23, 1, 6, 2, 90 }; List<int> lst2 = new List<int>() { 34, 21, 56, 42, 89, 90, -1 }; // Find the 2 smallest elements in each vector List<int> nMinimum1 = FindNMinimum(lst1, 2); List<int> nMinimum2 = FindNMinimum(lst2, 2); // Print the results foreach(int num in nMinimum1) { Console.Write(num + " "); } Console.WriteLine(); foreach(int num in nMinimum2) { Console.Write(num + " "); } Console.WriteLine(); }}// Priority Queue class with the smallest element at the topclass PriorityQueue<T> where T : IComparable<T> { private List<T> data; public PriorityQueue() { this.data = new List<T>(); } public void Enqueue(T item) { data.Add(item); int ci = data.Count - 1; while (ci > 0) { int pi = (ci - 1) / 2; if (data[ci].CompareTo(data[pi]) >= 0) break; T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp; ci = pi; } } public T Dequeue() { int li = data.Count - 1; T frontItem = data[0]; data[0] = data[li]; data.RemoveAt(li); --li; int ci = 0; while (true) { int rc = ci * 2 + 1; if (rc > li) break; int lc = rc + 1; if (lc <= li && data[lc].CompareTo(data[rc]) < 0) rc = lc; if (data[ci].CompareTo(data[rc]) <= 0) break; T tmp = data[ci]; data[ci] = data[rc]; data[rc] = tmp; ci = rc; } return frontItem; } public T Peek() { T frontItem = data[0]; return frontItem; } public int Count() { return data.Count; }}// This code is contributed by sarojmcy2e |
Output
[1, 2] [-1, 21]
This approach has a time complexity of O(n log n) and a space complexity of O(n), making it more efficient than the approach in the provided article.
Approach#3:Using sorted()
This approach sorts the input list and returns the first n elements.
Algorithm
1. Sort the input list in ascending order
2. Return the first N elements of the sorted list
Python3
def n_smallest_elements(input_list, n): sorted_list = sorted(input_list) return sorted_list[:n]print(n_smallest_elements([23, 1, 6, 2, 90], 2)) print(n_smallest_elements([34, 21, 56, 42, 89, 90, -1], 2)) |
Output
[1, 2] [-1, 21]
Time complexity: O(nlogn) where n is the length of the input list due to the sorting operation
Space complexity: O(n) for the sorted list
METHOD: Using sorted list
APPROACH:
This approach takes a list of integers as input and a value n, which represents the number of minimum elements to be returned from the list. It uses the sorting algorithm to sort the input list in ascending order. It then returns the first n elements of the sorted list.
ALGORITHM:
- Sort the input list in ascending order.
- Return the first n elements of the sorted list.
Python3
def n_minimum_elements(input_list, n): sorted_list = sorted(input_list) return sorted_list[:n]# Input 1input_list = [23, 1, 6, 2, 90]n = 4output = n_minimum_elements(input_list, n)print(output) # [1, 2, 6, 23]# Input 2input_list = [34, 21, 56, 42, 89, 90, -1]n = 8output = n_minimum_elements(input_list, n)print(output) # [34, 21, 56, 42, 89, 90, -1] |
Output
[1, 2, 6, 23] [-1, 21, 34, 42, 56, 89, 90]
Time Complexity:
The time complexity of sorting the list is O(n log n) in the average case, and O(n^2) in the worst case. However, since we are only sorting once, the overall time complexity of the function is O(n log n) in the average case, and O(n^2) in the worst case.
Auxiliary Space:
The space complexity of the function is O(n), since we need to create a new sorted list that has the same length as the input list.
