C Program to find the third largest element without sorting

The third-largest element is the value that comes after the largest and second-largest values. In this article, the ranking uses distinct values, so repeated copies of the same number do not occupy multiple positions.

For example:

Array: 12 5 8 19 19 3 15
Distinct values in descending order: 19 15 12 8 5 3
Third largest element: 12

We can find the answer in one traversal by maintaining the three largest distinct values seen so far. The array does not need to be sorted or modified.

C Program to Find the Third Largest Element Without Sorting

#include <stdio.h>

#define MAX_SIZE 100

int main(void) {
    int array[MAX_SIZE];
    int size;
    int largest = 0;
    int secondLargest = 0;
    int thirdLargest = 0;
    int hasLargest = 0;
    int hasSecondLargest = 0;
    int hasThirdLargest = 0;

    printf("Enter the number of elements: ");
    if (scanf("%d", &size) != 1 || size < 1 || size > MAX_SIZE) {
        printf("Please enter a size between 1 and %d.\n", MAX_SIZE);
        return 1;
    }

    printf("Enter %d elements:\n", size);
    for (int index = 0; index < size; index++) {
        if (scanf("%d", &array[index]) != 1) {
            printf("Invalid array element.\n");
            return 1;
        }
    }

    for (int index = 0; index < size; index++) {
        int value = array[index];

        if ((hasLargest && value == largest) ||
            (hasSecondLargest && value == secondLargest) ||
            (hasThirdLargest && value == thirdLargest)) {
            continue;
        }

        if (!hasLargest || value > largest) {
            if (hasSecondLargest) {
                thirdLargest = secondLargest;
                hasThirdLargest = 1;
            }

            if (hasLargest) {
                secondLargest = largest;
                hasSecondLargest = 1;
            }

            largest = value;
            hasLargest = 1;
        } else if (!hasSecondLargest || value > secondLargest) {
            if (hasSecondLargest) {
                thirdLargest = secondLargest;
                hasThirdLargest = 1;
            }

            secondLargest = value;
            hasSecondLargest = 1;
        } else if (!hasThirdLargest || value > thirdLargest) {
            thirdLargest = value;
            hasThirdLargest = 1;
        }
    }

    if (hasThirdLargest) {
        printf("Third largest element = %d\n", thirdLargest);
    } else {
        printf("The array has fewer than three distinct elements.\n");
    }

    return 0;
}

Sample Output

Enter the number of elements: 7
Enter 7 elements:
12 5 8 19 19 3 15
Third largest element = 12

How the Program Works

The program maintains three ordered values:

largest > secondLargest > thirdLargest

The three has... flags indicate whether each variable currently contains a valid distinct value. For every element:

1. If the value is already one of the tracked values, it is skipped as a duplicate.
2. If it is greater than largest, the old largest values shift down one rank.
3. Otherwise, if it is greater than secondLargest, the second-largest value shifts to third place.
4. Otherwise, if it is greater than thirdLargest, it becomes the new third-largest value.

Here is a dry run for the sample array:

Value	Largest	Second largest	Third largest	Action
12	12	—	—	Set largest
5	12	5	—	Set second largest
8	12	8	5	Shift 5; update second
19	19	12	8	Shift both tracked values
19	19	12	8	Skip duplicate
3	19	12	8	No change
15	19	15	12	Shift 12; update second

The final third-largest distinct value is 12.

Why Are Duplicate Values Ignored?

Without duplicate handling, an array such as 9, 9, 9, 7, 5 could incorrectly treat the repeated 9 values as the first three ranks.

Using distinct-value ranking gives:

Largest: 9
Second largest: 7
Third largest: 5

The continue statement skips a value when it already matches one of the tracked ranks.

Why Use Validity Flags?

Initializing the results to 0 or a fixed sentinel such as INT_MIN can be ambiguous because those values may legitimately occur in the array.

Validity flags keep initialization separate from the stored values, allowing the program to work with every value representable by int, including INT_MIN, negative values, and zero.

What If Three Distinct Values Do Not Exist?

The answer is undefined when the array contains fewer than three distinct values:

Array: 6 6 2 2
The array has fewer than three distinct elements.

Although this array contains four elements, it has only two distinct values. hasThirdLargest remains false, so the program reports the missing result.

Does It Work with Negative Numbers?

Yes. Direct comparisons handle negative values correctly:

Array: -10 -3 -7 -1 -3
Distinct values in descending order: -1 -3 -7 -10
Third largest element: -7

Why Avoid Sorting?

Sorting the array generally requires O(n log n) time and changes the element order unless a copy is made. After sorting, duplicate values still need to be skipped to find the third distinct value.

The one-pass method processes each element once, uses constant extra space, and leaves the original array unchanged.

Time and Space Complexity

• Time complexity: O(n), because every array element is processed once and each iteration performs only a fixed number of comparisons.
• Extra space complexity: O(1), because exactly three result values and three validity flags are maintained regardless of input size.

Common Mistakes

• Counting duplicate maximum values as separate ranks.
• Updating largest without shifting the previous values to second and third place.
• Assuming three distinct values exist merely because the array size is at least three.
• Initializing all results to 0, which fails for arrays containing only negative numbers.
• Sorting the array even though the problem explicitly forbids it.
• Using three separate if statements and updating more than one rank incorrectly for the same value.

By maintaining the three largest distinct values during a single traversal, the program finds the third-largest element in O(n) time without sorting or modifying the array.