Given an array with all distinct elements, find the largest three elements. Expected time complexity is O[n] and extra space is O[1].
Examples :
Input: arr[] = {10, 4, 3, 50, 23, 90}
Output: 90, 50, 23Method 1:
Algorithm:
1] Initialize the largest three elements as minus infinite.
first = second = third = -∞
2] Iterate through all elements of array.
a] Let current array element be x.
b] If [x > first]
{
// This order of assignment is important
third = second
second = first
first = x
}
c] Else if [x > second and x != first]
{
third = second
second = x
}
d] Else if [x > third and x != second]
{
third = x
}
3] Print first, second and third.Below is the implementation of the above algorithm.
C++
#include
using namespace std;
void print3largest[int arr[], int arr_size]
{
int
first, second, third;
if [arr_size < 3]
{
cout first]
{
third = second;
second = first;
first = arr[i];
}
else if [arr[i] > second && arr[i] != first]
{
third = second;
second = arr[i];
}
else if [arr[i] > third && arr[i] != second]
third = arr[i];
}
cout first]:
third = second
second = first
first =
arr[i]
elif [arr[i] > second]:
third = second
second = arr[i]
elif [arr[i] > third]:
third = arr[i]
print["Three largest elements are",
first, second, third]
arr = [12, 13, 1, 10, 34, 1]
n = len[arr]
print3largest[arr, n]
C#
using
System;
class PrintLargest {
static void print3largest[int[] arr,
int arr_size]
{
int i, first, second, third;
if [arr_size < 3] {
Console.WriteLine["Invalid Input"];
return;
}
third = first = second = 000;
for [i = 0; i < arr_size; i++] {
if [arr[i] > first] {
third = second;
second = first;
first = arr[i];
}
else
if [arr[i] > second && arr[i] != first] {
third = second;
second = arr[i];
}
else if [arr[i] > third && arr[i]!=second]
third = arr[i];
}
Console.WriteLine["Three largest elements are " + first + " " + second + " " + third];
}
public static void Main[]
{
int[] arr = new int[] { 12, 13, 1, 10, 34, 1 };
int n = arr.Length;
print3largest[arr, n];
}
}
PHP
Javascript
function print3largest[arr, arr_size]
{
let first, second, third;
if [arr_size < 3]
{
document.write[" Invalid Input "];
return;
}
third = first = second = Number.MIN_VALUE;
for[let i = 0; i < arr_size; i++]
{
if
[arr[i] > first]
{
third = second;
second = first;
first = arr[i];
}
else if [arr[i] > second]
{
third = second;
second = arr[i];
}
else if [arr[i] > third]
third = arr[i];
}
document.write["Three largest elements are "
+ first + " " + second + " "
+ third + "
"];
}
let arr = [ 12, 13, 1, 10, 34, 1 ];
let n = arr.length;
print3largest[arr, n];
Output
Three largest elements are 34 13 12
Time Complexity: O[n]
Auxiliary Space: O[1]
Method 2:
An efficient way to solve this problem is to use any O[nLogn] sorting algorithm & simply returning the last 3 largest elements.
C++
#include
using
namespace std;
void find3largest[int arr[], int n]
{
sort[arr, arr + n];
int check = 0, count = 1;
for [int i = 1; i