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, 23
Method 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 <bits/stdc++.h>
using namespace std;
void print3largest(int arr[], int arr_size)
{
int first, second, third;
if (arr_size < 3)
{
cout << " Invalid Input ";
return;
}
third = first = second = INT_MIN;
for(int 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 && arr[i] != first)
third = arr[i];
}
cout << "Three largest elements are "
<< first << " " << second << " "
<< third << endl;
}
int main()
{
int arr[] = { 12, 13, 1, 10, 34, 11, 34 };
int n = sizeof(arr) / sizeof(arr[0]);
print3largest(arr, n);
return 0;
}
|
C
#include <limits.h> /* For INT_MIN */
#include <stdio.h>
void print3largest(int arr[], int arr_size)
{
int i, first, second, third;
if (arr_size < 3) {
printf(" Invalid Input ");
return;
}
third = first = second = INT_MIN;
for (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];
}
printf("Three largest elements are %d %d %d\n", first, second, third);
}
int main()
{
int arr[] = { 12, 13, 1, 10, 34, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
print3largest(arr, n);
return 0;
}
|
Java
class PrintLargest {
static void print3largest(int arr[], int arr_size)
{
int i, first, second, third;
if (arr_size < 3) {
System.out.print(" Invalid Input ");
return;
}
third = first = second = Integer.MIN_VALUE;
for (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];
}
System.out.println("Three largest elements are " + first + " " + second + " " + third);
}
public static void main(String[] args)
{
int arr[] = { 12, 13, 1, 10, 34, 1 };
int n = arr.length;
print3largest(arr, n);
}
}
|
Python3
import sys
def print3largest(arr, arr_size):
if (arr_size < 3):
print(" Invalid Input ")
return
third = first = second = -sys.maxsize
for i in range(0, arr_size):
if (arr[i] > 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);
}
}
|
Javascript
<script>
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 + "<br>");
}
let arr = [ 12, 13, 1, 10, 34, 1 ];
let n = arr.length;
print3largest(arr, n);
</script>
|
PHP
<?php
function print3largest($arr, $arr_size)
{
$i; $first; $second; $third;
if ($arr_size < 3)
{
echo " Invalid Input ";
return;
}
$third = $first = $second = PHP_INT_MIN;
for ($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];
}
echo "Three largest elements are ",
$first, " ", $second, " ", $third;
}
$arr = array(12, 13, 1,
10, 34, 1);
$n = count($arr);
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 <bits/stdc++.h>
using namespace std;
void find3largest(int arr[], int n)
{
sort(arr, arr + n);
int check = 0, count = 1;
for (int i = 1; i <= n; i++) {
if (count < 4) {
if (check != arr[n - i]) {
cout << arr[n - i] << " ";
check = arr[n - i];
count++;
}
}
else
break;
}
}
int main()
{
int arr[] = { 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 };
int n = sizeof(arr) / sizeof(arr[0]);
find3largest(arr, n);
}
|
C
#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
void find3largest(int arr[], int n)
{
qsort(arr, n, sizeof(int),
cmpfunc);
int check = 0, count = 1;
for (int i = 1; i <= n; i++) {
if (count < 4) {
if (check != arr[n - i]) {
printf("%d ", arr[n - i]);
check = arr[n - i];
count++;
}
}
else
break;
}
}
int main()
{
int arr[] = { 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 };
int n = sizeof(arr) / sizeof(arr[0]);
find3largest(arr, n);
}
|
Java
import java.io.*;
import java.util.Arrays;
class GFG {
void find3largest(int[] arr)
{
Arrays.sort(arr);
int n = arr.length;
int check = 0, count = 1;
for (int i = 1; i <= n; i++) {
if (count < 4) {
if (check != arr[n - i]) {
System.out.print(arr[n - i] + " ");
check = arr[n - i];
count++;
}
}
else
break;
}
}
public static void main(String[] args)
{
GFG obj = new GFG();
int[] arr = { 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 };
obj.find3largest(arr);
}
}
|
Python3
def find3largest(arr, n):
arr = sorted(arr)
check = 0
count = 1
for i in range(1, n + 1):
if(count < 4):
if(check != arr[n - i]):
print(arr[n - i], end = " ")
check = arr[n - i]
count += 1
else:
break
arr = [12, 45, 1, -1, 45,
54, 23, 5, 0, -10]
n = len(arr)
find3largest(arr, n)
|
C#
using System;
class GFG {
void find3largest(int[] arr)
{
Array.Sort(arr);
int n = arr.Length;
int check = 0, count = 1;
for (int i = 1; i <= n; i++) {
if (count < 4) {
if (check != arr[n - i]) {
Console.Write(arr[n - i] + " ");
check = arr[n - i];
count++;
}
}
else
break;
}
}
public static void Main()
{
GFG obj = new GFG();
int[] arr = { 12, 45, 1, -1, 45,
54, 23, 5, 0, -10 };
obj.find3largest(arr);
}
}
|
Javascript
<script>
function find3largest(arr) {
arr.sort((a,b)=>a-b);
let check = 0, count = 1;
for (let i = 1; i <= arr.length; i++) {
if (count < 4) {
if (check != arr[arr.length - i]) {
document.write(arr[arr.length - i] + " ");
check = arr[arr.length - i];
count++;
}
}
else
break;
}
}
let arr = [ 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 ];
find3largest(arr);
</script>
|
Time Complexity: O(n log n)
Auxiliary Space: O(1)
Method 3:
We can use Partial Sort of C++ STL. partial_sort uses Heapselect, which provides better performance than Quickselect for small M. As a side effect, the end state of Heapselect leaves you with a heap, which means that you get the first half of the Heapsort algorithm “for free”. The complexity is “approximately” O(N log(M)), where M is distance(middle-first).
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> V = { 11, 65, 193, 36, 209, 664, 32 };
partial_sort(V.begin(), V.begin() + 3, V.end(), greater<int>());
cout << "first = " << V[0] << "\n";
cout << "second = " << V[1] << "\n";
cout << "third = " << V[2] << "\n";
return 0;
}
|
Java
import java.io.*;
import java.util.Arrays;
class GFG{
public static void main(String[] args)
{
int[] V = { 11, 65, 193, 36, 209, 664, 32 };
Arrays.sort(V);
int x = V.length;
System.out.println("first = " + V[x-1] );
System.out.println("second = " + V[x-2]);
System.out.println("third = " + V[x-3] );
}
}
|
Python3
V = [ 11, 65, 193, 36, 209, 664, 32 ];
V.sort()
V.reverse()
print(f"first = {V[0]}");
print(f"second = {V[1]}");
print(f"third = {V[2]}");
|
C#
using System;
class GFG
{
public static void Main()
{
int[] V = { 11, 65, 193, 36, 209, 664, 32 };
Array.Sort(V);
Array.Reverse(V);
Console.WriteLine("first = " + V[0] );
Console.WriteLine("second = " + V[1]);
Console.WriteLine("third = " + V[2] );
}
}
|
Javascript
<script>
let V = [ 11, 65, 193, 36, 209, 664, 32 ];
V.sort((a, b) => a - b)
V.reverse()
document.write("first = " + V[0] + "<br>");
document.write("second = " + V[1] + "<br>");
document.write("third = " + V[2] + "<br>");
</script>
|
Output
first = 664
second = 209
third = 193
Time Complexity: O(n log m) where m is distance(middle-first).
Auxiliary Space: O(1)
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!
