Largest three distinct elements in an array

Given an array arr[], the task is to find the top three largest distinct integers present in the array.

Note: If there are less than three distinct elements in the array, then return the available distinct numbers in descending order.

Examples :

Input: arr[] = [10, 4, 3, 50, 23, 90]
Output: [90, 50, 23]

Input: arr[] = [10, 9, 9]
Output: [10, 9]
There are only two distinct elements

Input: arr[] = [10, 10, 10]
Output: [10]
There is only one distinct element

Input: arr[] = []
Output: []

Naive Solution - Three Traversals

1. Find the first largest element by doing one traversal
2. Find the second largest by finding the largest element that is not equal to the element found in set 1.
3. Find the third largest by finding the largest that is neither equal to first and second.

Efficient Solution - One Traversal

Initialize first, second and third largest elements as -INF (minus infinite). Traverse through the array and handle the following cases for every element x.

1. If x is greater than first, update first as x, second as first and third as second.
2. Else If x is greater than second and not equal to first, update second as x and third as second
3. Else If x is greater third and not equal to first and second, update, third as x.

// C++ program for find the largest  // three elements in an array #include <bits/stdc++.h> using namespace std; // Function to return three largest elements vector<int> get3largest(vector<int> &arr) {  int fst = INT_MIN, sec = INT_MIN, thd = INT_MIN;  for (int x : arr)  {  // If current element is greater than fst  if (x > fst)  {  thd = sec;  sec = fst;  fst = x;  }  // If x is between fst and sec  else if (x > sec && x != fst)  {  thd = sec;  sec = x;  }  // If x is between sec and thd  else if (x > thd && x != sec && x != fst)  thd = x;  }  vector<int> res = {};  if (fst == INT_MIN)  return res;  res.push_back(fst);  if (sec == INT_MIN)  return res;  res.push_back(sec);  if (thd == INT_MIN)  return res;  res.push_back(thd);  return res; } // Driver code int main() {  vector<int> arr = {12, 13, 1, 10, 34, 1};  vector<int> res = get3largest(arr);  for (int x : res)  cout << x << " ";  cout << endl;  return 0; } 

#include <stdio.h> #include <limits.h> void get3largest(int arr[], int n) {  int fst = INT_MIN, sec = INT_MIN, thd = INT_MIN;  for (int i = 0; i < n; i++) {  int x = arr[i];  // If current element is greater than fst  if (x > fst) {  thd = sec;  sec = fst;  fst = x;  }  // If x is between fst and sec  else if (x > sec && x != fst) {  thd = sec;  sec = x;  }  // If x is between sec and thd  else if (x > thd && x != sec && x != fst) {  thd = x;  }  }  if (fst != INT_MIN) printf("%d ", fst);  if (sec != INT_MIN) printf("%d ", sec);  if (thd != INT_MIN) printf("%d ", thd);  printf("\n"); } int main() {  int arr[] = {12, 13, 1, 10, 34, 1};  int n = sizeof(arr) / sizeof(arr[0]);  get3largest(arr, n);  return 0; } 

import java.util.*; public class Main {  // Function to return three largest elements  public static List<Integer> get3largest(int[] arr) {  int fst = Integer.MIN_VALUE, sec = Integer.MIN_VALUE, thd = Integer.MIN_VALUE;  for (int x : arr) {  // If current element is greater than fst  if (x > fst) {  thd = sec;  sec = fst;  fst = x;  }  // If x is between fst and sec  else if (x > sec && x != fst) {  thd = sec;  sec = x;  }  // If x is between sec and thd  else if (x > thd && x != sec && x != fst) {  thd = x;  }  }  List<Integer> res = new ArrayList<>();  if (fst == Integer.MIN_VALUE) return res;  res.add(fst);  if (sec == Integer.MIN_VALUE) return res;  res.add(sec);  if (thd == Integer.MIN_VALUE) return res;  res.add(thd);  return res;  }  public static void main(String[] args) {  int[] arr = {12, 13, 1, 10, 34, 1};  List<Integer> res = get3largest(arr);  for (int x : res) {  System.out.print(x + " ");  }  System.out.println();  } } 

def get3largest(arr): fst = sec = thd = float('-inf') for x in arr: # If current element is greater than fst if x > fst: thd = sec sec = fst fst = x # If x is between fst and sec elif x > sec and x != fst: thd = sec sec = x # If x is between sec and thd elif x > thd and x != sec and x != fst: thd = x res = [] if fst == float('-inf'): return res res.append(fst) if sec == float('-inf'): return res res.append(sec) if thd == float('-inf'): return res res.append(thd) return res # Driver code arr = [12, 13, 1, 10, 34, 1] res = get3largest(arr) print(" ".join(map(str, res))) 

using System; using System.Collections.Generic; class Program {  // Function to return three largest elements  public static List<int> Get3Largest(int[] arr)  {  int fst = int.MinValue, sec = int.MinValue, thd = int.MinValue;  foreach (int x in arr)  {  // If current element is greater than fst  if (x > fst)  {  thd = sec;  sec = fst;  fst = x;  }  // If x is between fst and sec  else if (x > sec && x != fst)  {  thd = sec;  sec = x;  }  // If x is between sec and thd  else if (x > thd && x != sec && x != fst)  thd = x;  }  List<int> res = new List<int>();  if (fst == int.MinValue) return res;  res.Add(fst);  if (sec == int.MinValue) return res;  res.Add(sec);  if (thd == int.MinValue) return res;  res.Add(thd);  return res;  }  static void Main()  {  int[] arr = {12, 13, 1, 10, 34, 1};  List<int> res = Get3Largest(arr);  foreach (int x in res)  Console.Write(x + " ");  Console.WriteLine();  } } 

function get3largest(arr) {  let fst = -Infinity, sec = -Infinity, thd = -Infinity;  arr.forEach(x => {  // If current element is greater than fst  if (x > fst) {  thd = sec;  sec = fst;  fst = x;  }  // If x is between fst and sec  else if (x > sec && x !== fst) {  thd = sec;  sec = x;  }  // If x is between sec and thd  else if (x > thd && x !== sec && x !== fst) {  thd = x;  }  });  let res = [];  if (fst !== -Infinity) res.push(fst);  if (sec !== -Infinity) res.push(sec);  if (thd !== -Infinity) res.push(thd);  return res; } // Driver code let arr = [12, 13, 1, 10, 34, 1]; let res = get3largest(arr); console.log(res.join(' ')); 

34 13 12 

Time Complexity: O(n)
Auxiliary Space: O(1)