C Program to find the second smallest element in an array

The second smallest element is the smallest value that is greater than the minimum value. In this article, duplicate copies of the minimum are ignored, so the result is the second-smallest distinct value.

For example:

Array: 8 3 5 3 1 9
Smallest element: 1
Second smallest element: 3

Although 3 occurs twice, its value is distinct from the minimum and is the next greater value after 1.

C Program to Find the Second Smallest Array Element

#include <stdio.h>

#define MAX_SIZE 100

int main(void) {
    int array[MAX_SIZE];
    int size;
    int smallest = 0;
    int secondSmallest = 0;
    int hasSmallest = 0;
    int hasSecondSmallest = 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 (!hasSmallest || value < smallest) {
            if (hasSmallest) {
                secondSmallest = smallest;
                hasSecondSmallest = 1;
            }

            smallest = value;
            hasSmallest = 1;
        } else if (value != smallest &&
                   (!hasSecondSmallest || value < secondSmallest)) {
            secondSmallest = value;
            hasSecondSmallest = 1;
        }
    }

    if (hasSecondSmallest) {
        printf("Second smallest element = %d\n", secondSmallest);
    } else {
        printf("The array has no second-smallest distinct element.\n");
    }

    return 0;
}

Sample Output

Enter the number of elements: 6
Enter 6 elements:
8 3 5 3 1 9
Second smallest element = 3

How the Program Works

The program keeps track of the two smallest distinct values seen so far:

• smallest stores the current minimum.
• secondSmallest stores the smallest value greater than smallest.
• The two has... flags indicate whether those variables contain valid results.

For every array element:

1. If no minimum exists yet, or the current value is smaller than smallest, the old minimum moves to secondSmallest and the current value becomes the new minimum.
2. Otherwise, if the value differs from smallest and is smaller than the current second minimum, it becomes secondSmallest.
3. A value equal to smallest is ignored because the program requires distinct values.

Here is a dry run for 8, 3, 5, 3, 1, 9:

Current value	Smallest	Second smallest	Action
8	8	—	Set first minimum
3	3	8	Move 8; set new minimum
5	3	5	Update second minimum
3	3	5	Ignore duplicate minimum
1	1	3	Move 3; set new minimum
9	1	3	No change

After the final iteration, 1 is the minimum and 3 is the second-smallest distinct value.

Why Use Validity Flags?

A common implementation initializes the two result variables to a large constant such as INT_MAX. Flags avoid relying on a sentinel value that could also be a valid array element.

This matters when the input contains the largest or smallest value supported by int. With flags, every possible int remains valid input.

How Are Duplicate Values Handled?

Duplicate copies of the minimum do not create a second distinct value. For example:

Array: 2 2 2 5 7
Second smallest distinct element: 5

The condition value != smallest prevents the extra 2 values from replacing secondSmallest.

Duplicates of the second-smallest value do not affect the result either.

What If a Second-Smallest Value Does Not Exist?

A second distinct value does not exist when the array contains fewer than two distinct elements:

Array: 4 4 4
The array has no second-smallest distinct element.

The same message is produced for a one-element array. hasSecondSmallest remains 0 because the program never finds a value different from the minimum.

Does It Work with Negative Numbers?

Yes. The algorithm compares values directly and works with negative numbers, positive numbers, and zero.

Array: -3 -10 4 -3 0
Smallest element: -10
Second smallest element: -3

Why Not Sort the Array?

Sorting places the values in order, after which the first value different from the minimum is the second-smallest distinct value. However, sorting generally takes O(n log n) time and changes the original order unless a copy is made.

Tracking two values finds the answer in one traversal without modifying the array.

Time and Space Complexity

• Time complexity: O(n), because each of the n elements is processed once.
• Extra space complexity: O(1), because the algorithm uses a fixed number of variables regardless of the array size.

Common Mistakes

• Treating a duplicate minimum as the second-smallest distinct value.
• Updating smallest without first moving its previous value to secondSmallest.
• Sorting the array when a one-pass solution is sufficient.
• Assuming a second-smallest value always exists.
• Using a fixed sentinel that might also occur in the input.
• Comparing array indices instead of array values.

By maintaining the two smallest distinct values during one traversal, the program finds the second-smallest element efficiently without sorting or modifying the array.