easyArray ProblemsJava

Find the Second Smallest Element in an Array Without Sorting

Find the second smallest distinct value in an array in a single pass, without sorting.

Quick Answer

Keep two variables, smallest and secondSmallest, both starting at Integer.MAX_VALUE. Scan the array once: when a value is smaller than smallest, push the old smallest down to secondSmallest and update smallest; otherwise if the value is between smallest and secondSmallest (and not equal to smallest), update secondSmallest. This finds the answer in O(n) with no sorting.

Problem Statement

Given an array of integers, find the second smallest distinct value in it. Sorting the array would be O(n log n) and also rearranges the data — instead, scan the array a single time while remembering the two smallest values seen so far.

Return the second smallest element. If every element is the same (so there is no distinct runner-up), report that no second smallest exists.

Input: An array of integers arr with at least two elements.

Output: The second smallest distinct integer in the array.

Examples

Example 1
Input:  [5, 2, 9, 1, 3]
Output: 2

The smallest is 1 and the next smallest distinct value is 2.

Example 2
Input:  [4, 4, 2, 8]
Output: 4

The smallest is 2; the duplicates of 4 collapse to a single distinct runner-up, 4.

Constraints

  • 2 <= arr.length <= 10^6
  • Elements may be negative, zero, or duplicated

Think Before You Code

Reveal the questions to ask yourself first
  • Can you find the smallest and the second smallest in the same loop?
  • What starting values guarantee the first real elements replace them?
  • How do you avoid treating a duplicate of the smallest as the second smallest?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
You do not need to sort. Two running variables are enough to remember the two smallest values.
Hint 2
Initialise both `smallest` and `secondSmallest` to `Integer.MAX_VALUE`, then update them as you scan.
Hint 3
When an element is smaller than `smallest`, the old `smallest` becomes `secondSmallest`. Otherwise, only update `secondSmallest` if the element is larger than `smallest` but smaller than `secondSmallest`.

Approach

Reveal the step-by-step approach

Walk the array once, keeping the two smallest distinct values found so far.

  1. Set smallest = Integer.MAX_VALUE and secondSmallest = Integer.MAX_VALUE.
  2. For each element x:
    • If x < smallest: the current smallest is now the runner-up, so secondSmallest = smallest, then smallest = x.
    • Else if x != smallest and x < secondSmallest: update secondSmallest = x.
  3. If secondSmallest is still Integer.MAX_VALUE, there was no distinct second value.
  4. Otherwise return secondSmallest.

The x != smallest guard is what makes the answer distinct, so repeated copies of the minimum do not masquerade as the runner-up.

Dry Run

Walk through the example step by step

Scanning [5, 2, 9, 1, 3]:

x | rule                         | smallest | secondSmallest
--+------------------------------+----------+---------------
5 | 5 < MAX -> shift             | 5        | MAX
2 | 2 < 5 -> shift               | 2        | 5
9 | 9 not < 2, 9 not < 5         | 2        | 5
1 | 1 < 2 -> shift               | 1        | 2
3 | 3 not < 1, 3 not < 2         | 1        | 2
------------------------------------------ answer = 2

Solution

Reveal the full Java solution
public class SecondSmallest {
    public static int secondSmallest(int[] arr) {
        int smallest = Integer.MAX_VALUE;
        int secondSmallest = Integer.MAX_VALUE;
        for (int x : arr) {
            if (x < smallest) {
                secondSmallest = smallest;
                smallest = x;
            } else if (x != smallest && x < secondSmallest) {
                secondSmallest = x;
            }
        }
        if (secondSmallest == Integer.MAX_VALUE) {
            throw new IllegalArgumentException("No distinct second smallest element");
        }
        return secondSmallest;
    }

    public static void main(String[] args) {
        System.out.println(secondSmallest(new int[]{5, 2, 9, 1, 3})); // 2
        System.out.println(secondSmallest(new int[]{4, 4, 2, 8}));    // 4
    }
}

A single pass is enough because the two smallest values can be maintained together: every time a new minimum appears, the previous minimum is exactly the new second smallest candidate. The x != smallest check keeps the result distinct, which is why the duplicate 4s in the second example do not count as their own runner-up.

Time: O(n)Space: O(1)

Common Mistakes

  • Initialising `secondSmallest` to `arr[0]`, which breaks when arr[0] is the true minimum.
  • Forgetting the `x != smallest` guard, so duplicates of the minimum are reported as the second smallest.
  • Sorting the array first, which is O(n log n) and needlessly rearranges the input.

Edge Cases to Test

  • All elements equal, e.g. [7, 7, 7] — there is no distinct second smallest.
  • Array with negative numbers, e.g. [-3, -1, -3], where the second smallest is -1.
  • Exactly two elements, e.g. [9, 4], where the second smallest is 9.

Interview Follow-Ups

  • How would you generalise this to find the k-th smallest element without full sorting?
  • How would you find the second largest element with the same single-pass idea?
  • What changes if duplicates should be allowed to count as the second smallest?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us