Searching: Find the k maximum elements of an array in original array.

Problem Statement:

You are given an unsorted array and a value k.

You need to find the K max elements and they should be in original order

Example:

Input : arr[] = {10 50 30 60 15}
        k = 2
Output : 50 60

they are the top 2 elements and are in original order

Solution 1: Brute force approach

In this approach, we iterate the array k times.

Each time we will find one maximum element.

For that, we need to create a extra temp array.

Time Complexity: O(n*k)
Space Complexity: O(n)

Solution 2: Binary search approach

Copy the elements into a temp array and sort the array in descending order.

Then iterate the original array form 0 to n-1 and print all those elements that appear in first k elements of new array,

Time Complexity: O(n log n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;

void solution_1 (int arr[], int k, int n) 
{ 
	int brr[n]={0},crr[n]; 
	
	for(int i=0;i<n;i++) 
	{ 
		crr[i]=arr[i]; 
	} 

	for(int i=0;i<k;i++) 
	{ 

		int maxi = INT_MIN; 
		int index; 
		for(int j=0;j<n;j++) 
		{ 
			if(maxi<arr[j]) 
			{ 
				maxi=arr[j]; 
				index=j; 
			} 
		} 

		brr[index]=1; 
		arr[index]=INT_MIN; 
	} 
	
	for(int i=0;i<n;i++) 
	{ 

		if(brr[i]==1) 
		cout<<crr[i]<<" "; 
	} 
} 



void solution_2 (int arr[], int k, int n) 
{ 

    vector<int> brr(arr, arr + n); 
  
    sort(brr.begin(), brr.end(), greater<int>()); 
  
    for (int i = 0; i < n; ++i) 
        if (binary_search(brr.begin(), 
                 brr.begin() + k, arr[i],  
                        greater<int>())) 
            cout << arr[i] << " "; 
} 
  


int main() 
{ 
	int arr[] = { 10, 50, 30, 60, 15 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	int k = 2; 

	solution_1(arr, k, n); 
	//solution_2(arr, k, n); 

	return 0; 
} 

Output

50 60