Given an array arr[] and an integer k, we need to print k maximum elements of given array. The elements should printed in the order of the input.
Note : k is always less than or equal to n.
Examples:
Input : arr[] = {10 50 30 60 15}
k = 2
Output : 50 60
The top 2 elements are printed
as per their appearance in original
array.
Input : arr[] = {50 8 45 12 25 40 84}
k = 3
Output : 50 45 84
Method 1: We search for the maximum element k times in the given array. Each time we find one maximum element, we print it and replace it with minus infinite (INT_MIN in C) in the array. Also, the position of all k maximum elements is marked using an array so that with the help of that array we can print the elements in the order given in the original array. The time complexity of this method is O(n*k).
Below is the implementation of the above approach:
C++
// C++ program to find k maximum elements// of array in original order#include <bits/stdc++.h>using namespace std;// Function to print k Maximum elementsvoid printMax(int arr[], int k, int n){ int brr[n]={0},crr[n]; // Copying the array arr // into crr so that it // can be used later for(int i=0;i<n;i++) { crr[i]=arr[i]; } // Iterating for K-times for(int i=0;i<k;i++) { // Finding the maximum element // along with its index int maxi=INT_MIN; int index; for(int j=0;j<n;j++) { if(maxi<arr[j]) { maxi=arr[j]; index=j; } } // Assigning 1 in order // to mark the position // of all k maximum numbers brr[index]=1; arr[index]=INT_MIN; } for(int i=0;i<n;i++) { // Printing the k maximum // elements array if(brr[i]==1) cout<<crr[i]<<" "; }}// Driver codeint main(){ int arr[] = { 50, 8, 45, 12, 25, 40, 84 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; printMax(arr, k, n); return 0;}// This code is contributed by Pushpesh Raj. |
Java
// JAVA program to find k maximum elements// of array in original orderimport java.util.*;class GFG { // Function to print k Maximum elements public static void printMax(int arr[], int k, int n) { int brr[] = new int[n]; int crr[] = new int[n]; for (int i = 0; i < n; i++) brr[i] = 0; // Copying the array arr // into crr so that it // can be used later for (int i = 0; i < n; i++) { crr[i] = arr[i]; } // Iterating for K-times for (int i = 0; i < k; i++) { // Finding the maximum element // along with its index int maxi = Integer.MIN_VALUE; int index = 0; for (int j = 0; j < n; j++) { if (maxi < arr[j]) { maxi = arr[j]; index = j; } } // Assigning 1 in order // to mark the position // of all k maximum numbers brr[index] = 1; arr[index] = Integer.MIN_VALUE; } for (int i = 0; i < n; i++) { // Printing the k maximum // elements array if (brr[i] == 1) System.out.print(crr[i] + " "); } } // Driver code public static void main(String[] args) { int arr[] = new int[] { 50, 8, 45, 12, 25, 40, 84 }; int n = arr.length; int k = 3; printMax(arr, k, n); }}// This code is contributed by Taranpreet |
Python3
# Function to print k Maximum elementsdef printMax(arr, k, n): brr = [0 for _ in range(n)] crr = [0 for _ in range(n)] # Copying the array arr # into crr so that it # can be used later for i in range(0, n): crr[i] = arr[i] # Iterating for K-times for i in range(0, k): # Finding the maximum element # along with its index maxi = -99999 index = 0 for j in range(0, n): if maxi < arr[j]: maxi = arr[j] index = j # Assigning 1 in order # to mark the position # of all k maximum numbers brr[index] = 1 arr[index] = -99999 for i in range(0, n): # Printing the k maximum # elements array if brr[i] == 1: print(crr[i], end='') print(" ", end='')if __name__ == "__main__": arr = [50, 8, 45, 12, 25, 40, 84] n = len(arr) k = 3 printMax(arr, k, n)# This code is contributed by Aarti_Rathi |
C#
// C# program to find k maximum// elements of array in original orderusing System;using System.Linq;class GFG { // Function to print m Maximum elements public static void printMax(int[] arr, int k, int n) { // Copying the array arr // into crr so that it // can be used later int[] brr = new int[n]; int[] crr = new int[n]; for (int i = 0; i < n; i++) { brr[i] = 0; crr[i] = arr[i]; } // Iterating for K-times for (int i = 0; i < k; i++) { // Finding the maximum element // along with its index int maxi = Int32.MinValue; int index = 0; for (int j = 0; j < n; j++) { if (maxi < arr[j]) { maxi = arr[j]; index = j; } } // Assigning 1 in order // to mark the position // of all k maximum numbers brr[index] = 1; arr[index] = Int32.MinValue; } for (int i = 0; i < n; i++) { // Printing the k maximum // elements array if (brr[i] == 1) Console.Write(crr[i] + " "); } } // Driver code public static void Main() { int[] arr = { 50, 8, 45, 12, 25, 40, 84 }; int n = arr.Length; int k = 3; printMax(arr, k, n); }}// This code is contributed by Aarti_Rathi |
Javascript
// Function to print k Maximum elementsfunction printMax(arr, k, n){ var brr = Array(n).fill(0); var crr = Array(n).fill(0); for (var i =0; i < n; i++) { brr[i] = 0; } // Copying the array arr // into crr so that it // can be used later for (var i=0; i < n; i++) { crr[i] = arr[i]; } // Iterating for K-times for (var i=0; i < k; i++) { // Finding the maximum element // along with its index var maxi = -Number.MAX_VALUE; var index = 0; for (var j =0; j < n; j++) { if (maxi < arr[j]) { maxi = arr[j]; index = j; } } // Assigning 1 in order // to mark the position // of all k maximum numbers brr[index] = 1; arr[index] = -Number.MAX_VALUE; } for (var i=0; i < n; i++) { // Printing the k maximum // elements array if (brr[i] == 1) { console.log(crr[i] + " "); } }}// Driver codevar arr = [50, 8, 45, 12, 25, 40, 84];var n = arr.length;var k = 3;printMax(arr, k, n);// This code is contributed by Aarti_Rathi |
Output
50 45 84
Time Complexity: O(n*k)
Auxiliary Space: O(n)
Method 2: In this method, we store the original array in a new array and will sort the new array in descending order. After sorting, we iterate the original array from 0 to n and print all those elements that appear in first k elements of new array. For searching, we can do Binary Search.
C++
// C++ program to find k maximum elements // of array in original order#include <bits/stdc++.h>using namespace std;// Function to print m Maximum elementsvoid printMax(int arr[], int k, int n){ // vector to store the copy of the // original array vector<int> brr(arr, arr + n); // Sorting the vector in descending // order. Please refer below link for // details sort(brr.begin(), brr.end(), greater<int>()); // Traversing through original array and // printing all those elements that are // in first k of sorted vector. // Please refer https://goo.gl/44Rwgt // for details of binary_search() for (int i = 0; i < n; ++i) if (binary_search(brr.begin(), brr.begin() + k, arr[i], greater<int>())) cout << arr[i] << " ";}// Driver codeint main(){ int arr[] = { 50, 8, 45, 12, 25, 40, 84 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; printMax(arr, k, n); return 0;} |
Java
// Java program to find k maximum // elements of array in original orderimport java.util.Arrays;import java.util.Collections;public class GfG { // Function to print m Maximum elements public static void printMax(int arr[], int k, int n) { // Array to store the copy // of the original array Integer[] brr = new Integer[n]; for (int i = 0; i < n; i++) brr[i] = arr[i]; // Sorting the array in // descending order Arrays.sort(brr, Collections.reverseOrder()); // Traversing through original array and // printing all those elements that are // in first k of sorted array. // Please refer https://goo.gl/uj5RCD // for details of Arrays.binarySearch() for (int i = 0; i < n; ++i) if (Arrays.binarySearch(brr, arr[i], Collections.reverseOrder()) >= 0 && Arrays.binarySearch(brr, arr[i], Collections.reverseOrder()) < k) System.out.print(arr[i]+ " "); } // Driver code public static void main(String args[]) { int arr[] = { 50, 8, 45, 12, 25, 40, 84 }; int n = arr.length; int k = 3; printMax(arr, k, n); }}// This code is contributed by Swetank Modi |
Python3
# Python3 program to find k maximum elements # of array in original order# Function to print m Maximum elementsdef printMax(arr, k, n): # vector to store the copy of the # original array brr = arr.copy() # Sorting the vector in descending # order. Please refer below link for # details brr.sort(reverse = True) # Traversing through original array and # print all those elements that are # in first k of sorted vector. for i in range(n): if (arr[i] in brr[0:k]): print(arr[i], end = " ")# Driver codearr = [ 50, 8, 45, 12, 25, 40, 84 ]n = len(arr)k = 3printMax(arr, k, n)# This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to find k maximum // elements of array in original orderusing System;using System.Linq;class GFG{ // Function to print m Maximum elementspublic static void printMax(int[] arr, int k, int n){ // Array to store the copy // of the original array int[] brr = new int[n]; for(int i = 0; i < n; i++) brr[i] = arr[i]; // Sorting the array in // descending order Array.Sort(brr); Array.Reverse(brr); int[] crr = new int[k]; for(int i = 0; i < k; i++) { crr[i] = brr[i]; } // Traversing through original array and // printing all those elements that are // in first k of sorted array. // Please refer https://goo.gl/uj5RCD // for details of Array.BinarySearch() for(int i = 0; i < n; ++i) { if (crr.Contains(arr[i])) { Console.Write(arr[i] + " "); } }}// Driver codepublic static void Main(){ int[] arr = { 50, 8, 45, 12, 25, 40, 84 }; int n = arr.Length; int k = 3; printMax(arr, k, n);}}// This code is contributed by Shubhamsingh10 |
Javascript
<script>// JavaScript program to find k maximum elements // of array in original order// Function to print m Maximum elementsfunction printMax(arr, k, n){ // vector to store the copy of the // original array var brr = arr.slice(); // Sorting the vector in descending // order. Please refer below link for // details brr.sort((a, b) => b - a); // Traversing through original array and // printing all those elements that are // in first k of sorted vector. // Please refer https://goo.gl/44Rwgt // for details of binary_search() for (var i = 0; i < n; ++i) if (brr.indexOf(arr[i]) < k) document.write(arr[i] +" ");}// Driver codevar arr = [ 50, 8, 45, 12, 25, 40, 84 ];var n = arr.length;var k = 3;printMax(arr, k, n);// This code is contributed by ShubhamSingh10</script> |
Output
50 45 84
Time Complexity: O(n Log n) for sorting.
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!
