Find Second Smallest Element in an Array in Java

What is the Second Smallest Element in an Array?

Just like its counterpart problem (second largest), finding the second smallest element in an array is a classic test of whether you reach for an unnecessary sort or recognize the elegant single-pass solution.

This guide covers the optimal algorithm, correct duplicate handling, and every important edge case.

Problem Statement

Given an array like:

{10, 45, 23, 3, 67}

The smallest element is 3, and the second smallest is 10.

The goal is to find this value without fully sorting the array, ideally in a single traversal.

Optimal Single-Pass Algorithm

public class SecondSmallestElement {

    public static void main(String[] args) {

        int[] numbers = {10, 45, 23, 3, 67};

        int smallest = numbers[0];
        int secondSmallest = Integer.MAX_VALUE;

        for (int i = 1; i < numbers.length; i++) {

            if (numbers[i] < smallest) {

                secondSmallest = smallest;
                smallest = numbers[i];

            } else if (numbers[i] < secondSmallest && numbers[i] != smallest) {

                secondSmallest = numbers[i];
            }
        }

        System.out.println("Second Smallest Element: " + secondSmallest);
    }
}

This solution:

• Runs in a single O(n) pass.

• Uses only O(1) extra space.

• Avoids sorting the array.

Step-by-Step Explanation

Initialization

smallest starts as the first element of the array.

secondSmallest starts as Integer.MAX_VALUE, ensuring that any real value encountered during traversal will initially be considered smaller.

Main Loop

For each element:

• If the current element is smaller than smallest:

  • The previous smallest becomes secondSmallest.

  • Update smallest with the current value.

• Otherwise, if the current element is smaller than secondSmallest and is not equal to smallest:

  • Update secondSmallest.

Why the != smallest Check Matters

Without this condition, a duplicate of the smallest value could incorrectly become the second smallest.

The check ensures that the algorithm returns the second smallest distinct value.

Handling Duplicates Correctly

Consider the array:

{3, 3, 8, 10}

• Smallest = 3

• Second Smallest = 8

The condition:

numbers[i] != smallest

prevents another 3 from being reported as the second smallest.

If your problem definition treats duplicates as valid (second smallest by position rather than distinct value), remove this condition.

Always clarify this assumption during interviews.

Internal Working (Memory View)

For the array:

{10, 45, 23, 3, 67}

Final Result

smallest = 3
secondSmallest = 10

Real-Life Analogy

Imagine finding the two shortest students in a class lineup.

You initially assume the first student is the shortest.

As you move through the line:

• If you find someone shorter, the previous shortest becomes the second shortest.

• If someone is taller than the shortest but shorter than the current second shortest, they become the new second shortest.

By the end, you've identified both students without ever sorting the entire lineup.

Best Practices

• Initialize secondSmallest with Integer.MAX_VALUE.

• Validate that the array contains at least two elements.

• Clearly define how duplicate minimum values should be handled.

• Prefer the O(n) single-pass solution over sorting.

Common Mistakes

• Forgetting the != smallest condition when duplicate minimum values exist.

• Initializing secondSmallest to 0, which fails for arrays containing negative numbers.

• Not validating the array length.

• Accidentally using > instead of < while adapting the second-largest algorithm.

Expert Tips

• This approach naturally extends to finding the k-th smallest element using a Max Heap (Priority Queue).

• Always clarify whether the interviewer expects the second smallest distinct value.

• For streaming or extremely large datasets, the single-pass solution is much more practical than sorting.

Edge Cases

if (numbers == null || numbers.length < 2) {
    throw new IllegalArgumentException("Array must contain at least two elements");
}

Null Array

Reject the input before processing.

Array with Fewer Than Two Elements

There is no meaningful second smallest value.

All Elements Identical

Depending on the requirements, there may be no distinct second smallest value.

Comparison Table

Frequently Asked Questions

What is the time complexity of the optimal algorithm?

O(n) because the array is traversed only once using constant extra space.

Why initialize secondSmallest with Integer.MAX_VALUE?

It ensures that every actual array element will initially be considered smaller, allowing correct comparisons from the first iteration.

How do duplicates affect the algorithm?

Without the != smallest condition, duplicate minimum values could incorrectly become the second smallest instead of the next distinct value.

What if the array has fewer than two elements?

There is no valid second smallest value.

The program should throw an exception.

Is sorting an acceptable solution?

Yes, it produces the correct result.

However, it is less efficient (O(n log n)) than the optimal O(n) solution and is generally not preferred during interviews.

Can I use a TreeSet?

Yes.

TreeSet<Integer> automatically removes duplicates and stores values in sorted order, allowing you to retrieve the second smallest value using its navigation methods.

How can I find the k-th smallest element?

Use a Max Heap (Priority Queue) of size k.

This is the standard efficient solution for the generalized problem.

What if all elements in the array are equal?

There is no distinct second smallest value.

Your implementation should explicitly handle or report this situation based on the project requirements.