Tutorialspoint.dev

Third largest element in an array of distinct elements

Given an array of distinct elements, find third largest element in it.

Example :

Input  : arr[] = {1, 14, 2, 16, 10, 20}
Output : The third Largest element is 14 

Input  : arr[] = {19, -10, 20, 14, 2, 16, 10}
Output : The third Largest element is 16



Method 1 (Simple) Simplest way to solve this question is to first iterate through the array and find first maximum. Store this first maximum as well as its index. Now traverse the whole array finding the second max with the changed condition. Finally traverse the array third time and find the third largest element.

C++

// C++ program to find third Largest element in an array
// of distinct elements
#include <bits/stdc++.h>
  
void thirdLargest(int arr[], int arr_size)
{
    /* There should be atleast three elements */
    if (arr_size < 3)
    {
        printf(" Invalid Input ");
        return;
    }
  
    // Find first largest element
    int first = arr[0];
    for (int i = 1; i < arr_size ; i++)
        if (arr[i] > first)
            first = arr[i];
  
    // Find second largest element
    int second = INT_MIN;
    for (int i = 0; i < arr_size ; i++)
        if (arr[i] > second && arr[i] < first)
            second = arr[i];
  
    // Find third largest element
    int third = INT_MIN;
    for (int i = 0; i < arr_size ; i++)
        if (arr[i] > third && arr[i] < second)
            third = arr[i];
  
    printf("The third Largest element is %d ", third);
}
  
/* Driver program to test above function */
int main()
{
    int arr[] = {12, 13, 1, 10, 34, 16};
    int n = sizeof(arr)/sizeof(arr[0]);
    thirdLargest(arr, n);
    return 0;
}

Java

// Java program to find third 
// Largest element in an array
// of distinct elements
  
class GFG
{
static void thirdLargest(int arr[],
                         int arr_size)
{
    /* There should be 
    atleast three elements */
    if (arr_size < 3)
    {
        System.out.printf(" Invalid Input ");
        return;
    }
  
    // Find first 
    // largest element
    int first = arr[0];
    for (int i = 1;
             i < arr_size ; i++)
        if (arr[i] > first)
            first = arr[i];
  
    // Find second 
    // largest element
    int second = Integer.MIN_VALUE;
    for (int i = 0
             i < arr_size ; i++)
        if (arr[i] > second && 
            arr[i] < first)
            second = arr[i];
  
    // Find third
    // largest element
    int third = Integer.MIN_VALUE;
    for (int i = 0
             i < arr_size ; i++)
        if (arr[i] > third && 
            arr[i] < second)
            third = arr[i];
  
    System.out.printf("The third Largest "
                  "element is %d ", third);
}
  
// Driver code
public static void main(String []args)
{
    int arr[] = {12, 13, 1
                 10, 34, 16};
    int n = arr.length;
    thirdLargest(arr, n);
}
}
  
// This code is contributed
// by Smitha

Python3

# Python 3 program to find 
# third Largest element in 
# an array of distinct elements
import sys
def thirdLargest(arr, arr_size):
  
    # There should be 
    # atleast three elements 
    if (arr_size < 3):
      
        print(" Invalid Input ")
        return
      
  
    # Find first 
    # largest element
    first = arr[0]
    for i in range(1, arr_size):
        if (arr[i] > first):
            first = arr[i]
  
    # Find second
    # largest element
    second = -sys.maxsize
    for i in range(0, arr_size):
        if (arr[i] > second and 
            arr[i] < first):
            second = arr[i]
  
    # Find third 
    # largest element
    third = -sys.maxsize
    for i in range(0, arr_size):
        if (arr[i] > third and
            arr[i] < second):
            third = arr[i]
  
    print("The Third Largest"
          "element is", third)
  
# Driver Code
arr = [12, 13, 1
       10, 34, 16]
n = len(arr)
thirdLargest(arr, n)
  
# This code is contributed 
# by Smitha

C#

// C# program to find third 
// Largest element in an array 
// of distinct elements
using System;
  
class GFG
{
static void thirdLargest(int []arr,
                         int arr_size)
{
    /* There should be 
    atleast three elements */
    if (arr_size < 3)
    {
        Console.Write(" Invalid Input ");
        return;
    }
  
    // Find first 
    // largest element
    int first = arr[0];
    for (int i = 1;
             i < arr_size ; i++)
        if (arr[i] > first)
            first = arr[i];
  
    // Find second
    // largest element
    int second = -int.MaxValue;
    for (int i = 0; 
             i < arr_size ; i++)
        if (arr[i] > second && 
            arr[i] < first)
            second = arr[i];
  
    // Find third 
    // largest element
    int third = -int.MaxValue;
    for (int i = 0;
             i < arr_size ; i++)
        if (arr[i] > third && 
            arr[i] < second)
            third = arr[i];
  
    Console.Write("The third Largest "
                  "element is "+ third);
}
  
// Driver code
public static void Main()
{
    int []arr = {12, 13, 1,     
                 10, 34, 16};
    int n = arr.Length;
    thirdLargest(arr, n);
}
}
  
// This code is contributed by Smitha

/div>

PHP

<?php
// PHP program to find third 
// Largest element in an array
// of distinct elements
  
function thirdLargest($arr, $arr_size)
{
    /* There should be atleast
    three elements */
    if ($arr_size < 3)
    {
        echo " Invalid Input ";
        return;
    }
  
    // Find first largest element
    $first = $arr[0];
    for ($i = 1; $i < $arr_size ; $i++)
        if ($arr[$i] > $first)
            $first = $arr[$i];
  
    // Find second largest element
    $second = PHP_INT_MIN;
    for ($i = 0; $i < $arr_size ; $i++)
        if ($arr[$i] > $second && 
               $arr[$i] < $first)
            $second = $arr[$i];
  
    // Find third largest element
    $third = PHP_INT_MIN;
    for ($i = 0; $i < $arr_size ; $i++)
        if ($arr[$i] > $third && 
              $arr[$i] < $second)
            $third = $arr[$i];
  
    echo "The third Largest element is "
                             $third," ";
}
  
// Driver Code
$arr = array(12, 13, 1, 
             10, 34, 16);
$n = sizeof($arr);
thirdLargest($arr, $n);
  
// This code is contributed by m_kit
?>


Output :

The third Largest element is 13

Method 2 In this method, we need not to iterate array three times. We can find third largest in one traversal only.

  1. Initialize first = a[0] and second = -INF, third = -INF
  2. Iterate the array and compare each element with first.
    • If a[i] is greater than first then update all first, second and third:
      third = second
      second = first
      first = arr[i]
    • Else compare arr[i] with second, if its greater than second, then update:
      third = second
      second = arr[i]
    • Else compare arr[i] with third, if its greater than third, then update:
      third = arr[i]
  3. Return third

C++

// C++ program to find third Largest element in an array
#include <bits/stdc++.h>
  
void thirdLargest(int arr[], int arr_size)
{
    /* There should be atleast three elements */
    if (arr_size < 3)
    {
        printf(" Invalid Input ");
        return;
    }
  
    // Initialize first, second and third Largest element
    int first = arr[0], second = INT_MIN, third = INT_MIN;
  
    // Traverse array elements to find the third Largest
    for (int i = 1; i < arr_size ; i ++)
    {
        /* If current element is greater than first,
           then update first, second and third */
        if (arr[i] > first)
        {
            third  = second;
            second = first;
            first  = arr[i];
        }
  
        /* If arr[i] is in between first and second */
        else if (arr[i] > second)
        {
            third = second;
            second = arr[i];
        }
  
        /* If arr[i] is in between second and third */
        else if (arr[i] > third)
            third = arr[i];
    }
  
    printf("The third Largest element is %d ", third);
}
  
/* Driver program to test above function */
int main()
{
    int arr[] = {12, 13, 1, 10, 34, 16};
    int n = sizeof(arr)/sizeof(arr[0]);
    thirdLargest(arr, n);
    return 0;
}

Java

// Java program to find third Largest element in an array
class GFG {
  
    static void thirdLargest(int arr[], int arr_size) {
        /* There should be atleast three elements */
        if (arr_size < 3) {
            System.out.printf(" Invalid Input ");
            return;
        }
  
        // Initialize first, second and third Largest element
        int first = arr[0], second = Integer.MIN_VALUE,
                            third = Integer.MIN_VALUE;
  
        // Traverse array elements to find the third Largest
        for (int i = 1; i < arr_size; i++) {
            /* If current element is greater than first,
        then update first, second and third */
            if (arr[i] > first) {
                third = second;
                second = first;
                first = arr[i];
            } /* If arr[i] is in between first and second */
            else if (arr[i] > second) {
                third = second;
                second = arr[i];
            } /* If arr[i] is in between second and third */
            else if (arr[i] > third) {
                third = arr[i];
            }
        }
  
        System.out.printf("The third Largest element is %d ", third);
    }
  
    /* Driver program to test above function */
    public static void main(String []args) {
        int arr[] = {12, 13, 1, 10, 34, 16};
        int n = arr.length;
        thirdLargest(arr, n);
    }
}
//This code is contributed by 29AjayKumar

Python3

# Python3 program to find 
# third Largest element in 
# an array
import sys
def thirdLargest(arr, arr_size):
  
    # There should be 
    # atleast three elements 
    if (arr_size < 3):
      
        print(" Invalid Input ")
        return
      
    # Initialize first, second
    # and third Largest element
    first = arr[0]
    second = -sys.maxsize
    third = -sys.maxsize
  
    # Traverse array elements
    # to find the third Largest
    for i in range(1, arr_size):
      
        # If current element is
        # greater than first,
        # then update first, 
        # second and third 
        if (arr[i] > first):
          
            third = second
            second = first
            first = arr[i]
          
  
        # If arr[i] is in between 
        # first and second 
        elif (arr[i] > second):
          
            third = second
            second = arr[i]
          
        # If arr[i] is in between
        # second and third 
        elif (arr[i] > third):
            third = arr[i]
      
    print("The third Largest"
                  "element is", third)
  
# Driver Code
arr = [12, 13, 1,
       10, 34, 16]
n = len(arr)
thirdLargest(arr, n)
  
# This code is contributed
# by Smitha

C#

// C# program to find third Largest element in an array
using System;
class GFG {
  
static void thirdLargest(int[] arr, int arr_size) 
{
    /* There should be atleast three elements */
    if (arr_size < 3)
    {
        Console.Write(" Invalid Input ");
        return;
          
    }
  
    // Initialize first, second and third Largest element
    int first = arr[0], second = int.MinValue,
                            third = int.MinValue;
  
    // Traverse array elements to find the third Largest
    for (int i = 1; i < arr_size; i++) 
    {
        /* If current element is greater than first,
        then update first, second and third */
        if (arr[i] > first) {
            third = second;
            second = first;
            first = arr[i];
        }
          
        /* If arr[i] is in between first and second */
        else if (arr[i] > second) {
            third = second;
            second = arr[i];
        
        /* If arr[i] is in between second and third */
        else if (arr[i] > third) {
            third = arr[i];
        }
    }
  
    Console.Write("The third Largest element is "+ third);
}
  
/* Driver program to test above function */
public static void Main() {
        int[] arr = {12, 13, 1, 10, 34, 16};
        int n = arr.Length;
        thirdLargest(arr, n);
    }
}
  
// This code is contributed
// by Ita_c

PHP

<?php
// PHP program to find third 
// Largest element in an array
  
function thirdLargest($arr, $arr_size)
{
    /* There should be atleast
       three elements */
    if ($arr_size < 3)
    {
        echo " Invalid Input ";
        return;
    }
  
    // Initialize first, second and 
    // third Largest element
    $first = $arr[0]; 
    $second = PHP_INT_MIN;
    $third = PHP_INT_MIN;
  
    // Traverse array elements to
    // find the third Largest
    for ($i = 1; $i < $arr_size ; $i ++)
    {
        /* If current element is greater 
        than first, then update first, 
        second and third */
        if ($arr[$i] > $first)
        {
            $third = $second;
            $second = $first;
            $first = $arr[$i];
        }
  
        /* If arr[i] is in between
        first and second */
        else if ($arr[$i] > $second)
        {
            $third = $second;
            $second = $arr[$i];
        }
  
        /* If arr[i] is in between
        second and third */
        else if ($arr[$i] > $third)
            $third = $arr[$i];
    }
  
    echo "The third Largest element is "
                                  $third;
}
  
// Driver Code
$arr = array (12, 13, 1, 
              10, 34, 16);
$n = sizeof($arr);
thirdLargest($arr, $n);
  
// This code is contributed by jit_t
?>


Output :

The third Largest element is 13

Exercise :
Extend the above solution to find third largest when array may have duplicates. For example, if the input array is {10, 5, 15, 5, 15, 10, 1, 1}, then output should be 5. The extended solution should also work in one traversal.

Related Articles:

  1. Find the smallest and second smallest element in an array
  2. k largest(or smallest) elements in an array
  3. K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter