Second Largest and Second Smallest Element in C Array

Finding the second largest and second smallest elements in an array can be done in a single pass through the data — O(n) time, O(1) space — without sorting. The key is maintaining four running extremes: largest, second_largest, smallest, second_smallest. The original program sorted the array first (O(n²) with bubble sort), then accessed fixed indices — correct but slow and wasteful.

One-Pass Algorithm

For each element, update the top-2 and bottom-2 independently:

If it beats largest: demote largest to second_largest, update largest
Else if it beats second_largest (and is different from largest): update second_largest
Same logic for smallest / second_smallest, reversed

Trace for [3, 1, 4, 1, 5]

i	a[i]	largest	2nd_largest	smallest	2nd_smallest
0	3	3	—	3	—
1	1	3	1	1	3
2	4	4	3	1	3
3	1	4	3	1	3
4	5	5	4	1	3

Result: largest=5, 2nd=4, smallest=1, 2nd_smallest=3 ✓ (the duplicate 1 is correctly skipped for 2nd_smallest)

C Program: Second Largest and Second Smallest

/* Find second largest and second smallest — O(n) one-pass
 * Compile: gcc -ansi -Wall -Wextra second.c -o second */
#include <stdio.h>
#define MAX 100
#define INT_MIN_VAL (-2147483647 - 1)
#define INT_MAX_VAL 2147483647

int main(void)
{
    int a[MAX], n, i;
    int largest, second_largest, smallest, second_smallest;

    printf("How many elements (2-%d)? ", MAX);
    if (scanf("%d", &n) != 1 || n < 2 || n > MAX) {
        printf("Need at least 2 elements.\n"); return 1;
    }
    printf("Enter %d integers:\n", n);
    for (i = 0; i < n; i++)
        if (scanf("%d", &a[i]) != 1) { printf("Invalid.\n"); return 1; }

    largest = second_largest = INT_MIN_VAL;
    smallest = second_smallest = INT_MAX_VAL;

    for (i = 0; i < n; i++) {
        if (a[i] > largest) {
            second_largest = largest;
            largest = a[i];
        } else if (a[i] > second_largest && a[i] != largest) {
            second_largest = a[i];
        }
        if (a[i] < smallest) {
            second_smallest = smallest;
            smallest = a[i];
        } else if (a[i] < second_smallest && a[i] != smallest) {
            second_smallest = a[i];
        }
    }

    if (second_largest == INT_MIN_VAL)
        printf("All elements are equal — no second largest.\n");
    else {
        printf("Largest        = %d\n", largest);
        printf("Second largest = %d\n", second_largest);
    }
    if (second_smallest == INT_MAX_VAL)
        printf("All elements are equal — no second smallest.\n");
    else {
        printf("Smallest        = %d\n", smallest);
        printf("Second smallest = %d\n", second_smallest);
    }
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra second.c -o second
./second

Sample Output

How many elements (2-100)? 5
Enter 5 integers:
3 1 4 1 5
Largest        = 5
Second largest = 4
Smallest        = 1
Second smallest = 3

How many elements (2-100)? 4
Enter 4 integers:
2 2 2 2
All elements are equal — no second largest.
All elements are equal — no second smallest.

Code Explanation

Initialize to INT extremes — largest = second_largest = INT_MIN_VAL ensures the first element always beats the initial value. INT_MIN_VAL is defined as (-2147483647 - 1) rather than -2147483648 directly, because the C89 standard doesn’t guarantee that a literal -2147483648 parses as an int (the parser sees it as the positive value 2147483648, which overflows, then negates). The two-step form avoids this.
a[i] != largest handles duplicates — without this guard, if the array is [5,5,3], the second update path would set second_largest = 5 (equal to largest) on the second 5. The guard ensures second_largest is always a strictly different value from largest.
Why update second before checking the else — when a new element beats largest, the old largest becomes the new second_largest (second_largest = largest; largest = a[i];). This is correct because the previous largest is the second-best seen so far. If you reversed the assignments (largest = a[i]; second_largest = largest;), second_largest would get the new value, losing the old one.
Two independent top-2/bottom-2 trackers — the largest/second_largest and smallest/second_smallest computations are completely independent. An element can update both at once (unlikely for random data but possible for small arrays).

What This Program Teaches

Top-K in O(n) — maintaining K running extremes instead of sorting gives O(n) time versus O(n log n). For K=2 (as here) or K=10, this is a huge win for large n. The same pattern drives streaming algorithms, percentile estimation, and top-K ranking.
Integer limits as sentinels — using INT_MIN_VAL and INT_MAX_VAL as initial values is a common trick for running-extreme algorithms. It eliminates the need to special-case the first element and makes the update logic uniform across all iterations.
Duplicate handling — the a[i] != largest / a[i] != smallest conditions define “second” as the second distinct value. If you want the second occurrence regardless of value, remove these conditions.

Related Programs

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.

C Program to Find Second Largest and Second Smallest Element in an Array