Program to print N minimum elements from list of integers
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 code int 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 elements import 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 code public 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 elements def 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 code list1 = [ 4 , 78 , 34 , 10 , 8 , 21 , 11 , 231 ]; N = 2 ; Nminelements(list1, N) |
C#
// C# program to find N // minimum elements using 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 code public 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 elements function 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 code let list1=[4, 78, 34, 10, 8, 21, 11, 231 ]; let N = 2; Nminelements(list1, N); // This code is contributed by rag2127 </script> |
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 approach import 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 heapq def 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_minimum print (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 |
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 top class 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 |
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] |
[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
C++
#include <algorithm> #include <iostream> #include <vector> using namespace std; vector< int > nSmallestElements(vector< int > inputList, int n) { // Sort the input list in ascending order. sort(inputList.begin(), inputList.end()); // Return the first `n` elements of the sorted list. vector< int > smallestElements; for ( int i = 0; i < n; i++) { smallestElements.push_back(inputList[i]); } return smallestElements; } int main() { vector< int > lst1 = { 23, 1, 6, 2, 90 }; vector< int > lst2 = { 34, 21, 56, 42, 89, 90, -1 }; vector< int > n_minimum1 = nSmallestElements(lst1, 2); vector< int > n_minimum2 = nSmallestElements(lst2, 2); for ( int i = 0; i < n_minimum1.size(); i++) { cout << n_minimum1[i] << " " ; } cout << endl; for ( int i = 0; i < n_minimum2.size(); i++) { cout << n_minimum2[i] << " " ; } cout << endl; return 0; } //This Code contributed by Rohit Singh |
Java
// Java Code for the above approach import java.util.ArrayList; import java.util.Collections; import java.util.List; public class GFG { // Function to find the n smallest elements in a list public static List<Integer> nSmallestElements(List<Integer> inputList, int n) { // Sort the input list in ascending order. Collections.sort(inputList); // Return the first `n` elements of the sorted list. List<Integer> smallestElements = new ArrayList<>(); for ( int i = 0 ; i < n; i++) { smallestElements.add(inputList.get(i)); } return smallestElements; } // Main method public static void main(String[] args) { List<Integer> lst1 = new ArrayList<>(List.of( 23 , 1 , 6 , 2 , 90 )); List<Integer> lst2 = new ArrayList<>( List.of( 34 , 21 , 56 , 42 , 89 , 90 , - 1 )); List<Integer> n_minimum1 = nSmallestElements(lst1, 2 ); List<Integer> n_minimum2 = nSmallestElements(lst2, 2 ); for ( int i = 0 ; i < n_minimum1.size(); i++) { System.out.print(n_minimum1.get(i) + " " ); } System.out.println(); for ( int i = 0 ; i < n_minimum2.size(); i++) { System.out.print(n_minimum2.get(i) + " " ); } System.out.println(); } } // This code is contributed by Susobhan Akhuli |
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 )) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static List< int > NSmallestElements(List< int > inputList, int n) { // Sort the input list in ascending order. inputList.Sort(); // Return the first `n` elements of the sorted list. return inputList.Take(n).ToList(); } static void Main() { List< int > lst1 = new List< int > { 23, 1, 6, 2, 90 }; List< int > lst2 = new List< int > { 34, 21, 56, 42, 89, 90, -1 }; List< int > nMinimum1 = NSmallestElements(lst1, 2); List< int > nMinimum2 = NSmallestElements(lst2, 2); Console.WriteLine( "Smallest elements of lst1: " + string .Join( " " , nMinimum1)); Console.WriteLine( "Smallest elements of lst2: " + string .Join( " " , nMinimum2)); } } // This Code is Contributed by Shivam Tiwari |
Javascript
// JavaScript function to find the n smallest elements in an array function nSmallestElements(inputArray, n) { // Sort the input array in ascending order using a comparator function. inputArray.sort((a, b) => a - b); // Return the first n elements of the sorted array using the slice method. return inputArray.slice(0, n); } // Main function function main() { const lst1 = [23, 1, 6, 2, 90]; const lst2 = [34, 21, 56, 42, 89, 90, -1]; const n_minimum1 = nSmallestElements(lst1, 2); const n_minimum2 = nSmallestElements(lst2, 2); // Output the smallest elements from lst1 for (let i = 0; i < n_minimum1.length; i++) { console.log(n_minimum1[i]); } // Output the smallest elements from lst2 for (let i = 0; i < n_minimum2.length; i++) { console.log(n_minimum2[i]); } } // Call the main function to execute the code main(); |
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