Find the Second Smallest Element in an Array

Problem Statement

Given an array of integers, the task is to find the second smallest element in the array.

Important Conditions

• The array must contain at least two distinct elements
• Duplicate values should be handled correctly
• The second smallest element is the smallest value greater than the minimum

Understanding the Problem

Consider the array:

[10, 5, 20, 8]

• Smallest element = 5
• Second smallest element = 8

Now consider:

[4, 4, 4, 4]

• There is no second smallest element because all elements are equal

Why This Problem Is Important

This problem helps in understanding:

• Comparison-based logic
• Tracking multiple values during traversal
• Handling duplicates and edge cases
• Writing efficient single-pass algorithms

It is frequently asked in:

• Coding interviews
• Competitive programming
• Data processing and analytics tasks

Input and Output Format

Input

Array: [12, 35, 1, 10, 34, 1]

Output

Second Smallest Element: 10

Approach 1: Single Traversal (Optimal)

Instead of sorting the array, we track:

• smallest
• secondSmallest

This ensures optimal performance.

Step-by-Step Algorithm

1. Initialize

   smallest = +∞  
   secondSmallest = +∞
   

2. Traverse the array
3. For each element:
   • If element < smallest
     → update secondSmallest = smallest
     → update smallest = element
   • Else if element > smallest AND element < secondSmallest
     → update secondSmallest = element
4. After traversal:
   • If secondSmallest is still +∞, second smallest does not exist
   • Else print secondSmallest

Pseudocode

smallest = +∞
secondSmallest = +∞

for each element in array:
    if element < smallest:
        secondSmallest = smallest
        smallest = element
    else if element > smallest AND element < secondSmallest:
        secondSmallest = element

if secondSmallest == +∞:
    print "No second smallest element"
else:
    print secondSmallest

Dry Run Example

Array = [12, 35, 1, 10, 34]

Initial State

smallest = +∞
secondSmallest = +∞

Result

Second Smallest Element = 10

Time and Space Complexity

Language-wise Implementation

C Implementation

#include 
#include 

int main() {
    int arr[] = {12, 35, 1, 10, 34};
    int n = sizeof(arr) / sizeof(arr[0]);

    int smallest = INT_MAX;
    int secondSmallest = INT_MAX;

    for(int i = 0; i < n; i++) {
        if(arr[i] < smallest) {
            secondSmallest = smallest;
            smallest = arr[i];
        }
        else if(arr[i] > smallest && arr[i] < secondSmallest) {
            secondSmallest = arr[i];
        }
    }

    if(secondSmallest == INT_MAX)
        printf("No second smallest element");
    else
        printf("Second smallest element: %d", secondSmallest);

    return 0;
}

C++ Implementation

#include 
#include 
using namespace std;

int main() {
    int arr[] = {12, 35, 1, 10, 34};
    int n = sizeof(arr) / sizeof(arr[0]);

    int smallest = INT_MAX;
    int secondSmallest = INT_MAX;

    for(int i = 0; i < n; i++) {
        if(arr[i] < smallest) {
            secondSmallest = smallest;
            smallest = arr[i];
        }
        else if(arr[i] > smallest && arr[i] < secondSmallest) {
            secondSmallest = arr[i];
        }
    }

    if(secondSmallest == INT_MAX)
        cout << "No second smallest element";
    else
        cout << "Second smallest element: " << secondSmallest;

    return 0;
}

Java Implementation

public class Main {
    public static void main(String[] args) {
        int[] arr = {12, 35, 1, 10, 34};

        int smallest = Integer.MAX_VALUE;
        int secondSmallest = Integer.MAX_VALUE;

        for(int num : arr) {
            if(num < smallest) {
                secondSmallest = smallest;
                smallest = num;
            }
            else if(num > smallest && num < secondSmallest) {
                secondSmallest = num;
            }
        }

        if(secondSmallest == Integer.MAX_VALUE)
            System.out.println("No second smallest element");
        else
            System.out.println("Second smallest element: " + secondSmallest);
    }
}

Python Implementation

arr = [12, 35, 1, 10, 34]

smallest = float('inf')
second_smallest = float('inf')

for num in arr:
    if num < smallest:
        second_smallest = smallest
        smallest = num
    elif num > smallest and num < second_smallest:
        second_smallest = num

if second_smallest == float('inf'):
    print("No second smallest element")
else:
    print("Second smallest element:", second_smallest)

C# Implementation

using System;

class Program {
    static void Main() {
        int[] arr = {12, 35, 1, 10, 34};

        int smallest = int.MaxValue;
        int secondSmallest = int.MaxValue;

        foreach(int num in arr) {
            if(num < smallest) {
                secondSmallest = smallest;
                smallest = num;
            }
            else if(num > smallest && num < secondSmallest) {
                secondSmallest = num;
            }
        }

        if(secondSmallest == int.MaxValue)
            Console.WriteLine("No second smallest element");
        else
            Console.WriteLine("Second smallest element: " + secondSmallest);
    }
}

JavaScript Implementation

let arr = [12, 35, 1, 10, 34];

let smallest = Infinity;
let secondSmallest = Infinity;

for (let num of arr) {
    if (num < smallest) {
        secondSmallest = smallest;
        smallest = num;
    } else if (num > smallest && num < secondSmallest) {
        secondSmallest = num;
    }
}

if (secondSmallest === Infinity)
    console.log("No second smallest element");
else
    console.log("Second smallest element:", secondSmallest);

Common Mistakes to Avoid

• Sorting the array unnecessarily
• Not checking for duplicate values
• Forgetting edge cases with all identical elements
• Using extra data structures when not needed

Interview Variations

• Find third smallest element
• Find k-th smallest element
• Find smallest and second smallest together
• Find second smallest in a stream of numbers

Detailed Summary

Finding the second smallest element in an array is a fundamental algorithmic problem that strengthens understanding of comparison logic and efficient traversal. By maintaining two variables—smallest and secondSmallest—we can solve the problem in a single pass with constant space. This approach avoids unnecessary sorting and handles duplicates and edge cases effectively, making it ideal for interviews and real-world applications.

Next Problem in the Series

Remove Duplicate Elements from an Array