Finding the Third Largest Element in an Array

When dealing with arrays, finding the third largest element is a common problem that can be approached in various ways. In this blog post, we'll explore different strategies to find the third largest element in an array, and we'll provide code examples in both Java and C++.

Approach 1: Sorting the Array

One straightforward approach is to sort the array in descending order and then pick the third element. Let's see how this can be done in both Java and C++.

Java:

import java.util.Arrays;

public class ThirdLargestElement {
    public static int findThirdLargest(int[] arr) {
        Arrays.sort(arr); // Sorting the array in ascending order
        int n = arr.length;


        // The third largest element is at index n - 3
        return arr[n - 3];
    }


    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        int thirdLargest = findThirdLargest(array);


        System.out.println("Third largest element: " + thirdLargest);
    }
}

C++:

#include <iostream>
#include <algorithm>


int findThirdLargest(int arr[], int size) {
    std::sort(arr, arr + size); // Sorting the array in ascending order


    // The third largest element is at index size - 3
    return arr[size - 3];
}


int main() {
    int array[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(array) / sizeof(array[0]);


    int thirdLargest = findThirdLargest(array, size);


    std::cout << "Third largest element: " << thirdLargest << std::endl;


    return 0;
}

Approach 2: Tracking Three Maximum Elements

Another approach involves iterating through the array and keeping track of the three maximum elements encountered so far. This approach avoids the full sorting of the array.

Java:

public class ThirdLargestElement {
    public static int findThirdLargest(int[] arr) {
        int firstMax = Integer.MIN_VALUE;
        int secondMax = Integer.MIN_VALUE;
        int thirdMax = Integer.MIN_VALUE;


        for (int num : arr) {
            if (num > firstMax) {
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = num;
            } else if (num > secondMax) {
                thirdMax = secondMax;
                secondMax = num;
            } else if (num > thirdMax) {
                thirdMax = num;
            }
        }


        return thirdMax;
    }


    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        int thirdLargest = findThirdLargest(array);


        System.out.println("Third largest element: " + thirdLargest);
    }
}

C++:

#include <iostream>
#include <climits>


int findThirdLargest(int arr[], int size) {
    int firstMax = INT_MIN;
    int secondMax = INT_MIN;
    int thirdMax = INT_MIN;


    for (int i = 0; i < size; ++i) {
        if (arr[i] > firstMax) {
            thirdMax = secondMax;
            secondMax = firstMax;
            firstMax = arr[i];
        } else if (arr[i] > secondMax) {
            thirdMax = secondMax;
            secondMax = arr[i];
        } else if (arr[i] > thirdMax) {
            thirdMax = arr[i];
        }
    }


    return thirdMax;
}


int main() {
    int array[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(array) / sizeof(array[0]);


    int thirdLargest = findThirdLargest(array, size);


    std::cout << "Third largest element: " << thirdLargest << std::endl;


    return 0;
}

Conclusion

In this blog post, we explored two different approaches to finding the third largest element in an array. The sorting approach provides a clear and concise solution, but it may not be the most efficient for large arrays. The approach of tracking the three maximum elements while iterating through the array is more efficient and avoids the overhead of sorting.