Find Second Smallest in Array

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

• The second smallest element is the smallest number that is strictly greater than the minimum value.
• If the array has fewer than 2 distinct elements, then the second smallest does not exist.

If a second smallest number cannot be found, return -1.

Understanding the Problem

We are given an array of numbers and our task is to find the second smallest distinct element in that array.

In simple terms, we are looking for the number that comes right after the smallest number — but it must be different from the smallest.

This problem can be tricky for beginners, especially when the array has duplicate values or not enough distinct elements. That’s why we will solve it step by step using a simple and intuitive approach.

Step-by-Step Solution

Let’s go through the logic using a beginner-friendly example:

Input: [4, 1, 7, 1, 3, 2]

We want to find the two smallest distinct numbers. To do this efficiently, we’ll maintain two variables:

• min_val: the smallest number so far
• second_min: the second smallest distinct number

We initialize both with Infinity, which is larger than any number in the array. This helps us compare and replace values as we go.

Algorithm Walkthrough:

• Start iterating over each number in the array.
• If a number is less than min_val:
  • Then update second_min = min_val
  • And update min_val = current number
• If a number is not equal to min_val and less than second_min, then update second_min.

This way, we track both values in a single pass.

Example in Action:

Start: min_val = Infinity, second_min = Infinity

Number: 4 → min_val = 4, second_min = Infinity  
Number: 1 → min_val = 1, second_min = 4  
Number: 7 → skip (7 > second_min)  
Number: 1 → skip (duplicate of min_val)  
Number: 3 → second_min = 3 (since 3 > min_val and 3 < 4)  
Number: 2 → second_min = 2 (2 < 3 and 2 != min_val)

Final min_val = 1, second_min = 2

Output: 2 — the second smallest distinct element.

Handling Edge Cases

Let’s now think about what could go wrong or what needs special handling:

• Empty Array: No numbers to compare → return -1.
• Only One Element: No second element → return -1.
• All Elements Are Equal: Only one unique number → return -1.

1. Given an array of numbers arr.
2. Initialize min_val and second_min to Infinity.
3. Iterate through each element in the array.
4. If the current element is less than min_val, update second_min to min_val, and then update min_val.
5. Else if the current element is less than second_min and not equal to min_val, update second_min.
6. After the loop, return second_min.

Worked example

Let's find the second smallest number in the array using a loop.

Initialize min = Infinity and secondMin = Infinity.

Check index 0

Current element is 30. Compare with min = Infinity and secondMin = Infinity.

30 is smaller than current min. Update: secondMin = Infinity, min = 30.

Check index 1

Current element is 20. Compare with min = 30 and secondMin = Infinity.

20 is smaller than current min. Update: secondMin = 30, min = 20.

Check index 2

Current element is 10. Compare with min = 20 and secondMin = 30.

10 is smaller than current min. Update: secondMin = 20, min = 10.

Check index 3

Current element is 50. Compare with min = 10 and secondMin = 20.

No update required.

Check index 4

Current element is 60. Compare with min = 10 and secondMin = 20.

No update required.

Check index 5

Current element is 40. Compare with min = 10 and secondMin = 20.

No update required.

Final Result:

Second Smallest Element = 20

#include <stdio.h>
#include <limits.h>

int isDistinct(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] != arr[j]) return 1;
        }
    }
    return 0;
}

int findSecondSmallest(int arr[], int n) {
    if (n < 2 || !isDistinct(arr, n)) return -1;
    int minVal = INT_MAX, secondMin = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (arr[i] < minVal) {
            secondMin = minVal;
            minVal = arr[i];
        } else if (arr[i] < secondMin && arr[i] != minVal) {
            secondMin = arr[i];
        }
    }
    return secondMin;
}

int main() {
    int arr[] = {30, 20, 10, 50, 60, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Second Smallest: %d\n", findSecondSmallest(arr, n));
    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_set>
#include <limits>
using namespace std;

int findSecondSmallest(const vector<int>& arr) {
    unordered_set<int> s(arr.begin(), arr.end());
    if (s.size() < 2) return -1;

    int minVal = INT_MAX, secondMin = INT_MAX;
    for (int num : arr) {
        if (num < minVal) {
            secondMin = minVal;
            minVal = num;
        } else if (num < secondMin && num != minVal) {
            secondMin = num;
        }
    }
    return secondMin;
}

int main() {
    vector<int> arr = {30, 20, 10, 50, 60, 40};
    cout << "Second Smallest: " << findSecondSmallest(arr) << endl;
    return 0;
}

def find_second_smallest(arr):
    if len(set(arr)) < 2:
        return -1
    min_val = float('inf')
    second_min = float('inf')
    for num in arr:
        if num < min_val:
            second_min = min_val
            min_val = num
        elif num < second_min and num != min_val:
            second_min = num
    return second_min

# Sample Input
arr = [30, 20, 10, 50, 60, 40]
print("Second Smallest:", find_second_smallest(arr))

import java.util.*;
public class SecondSmallest {
    public static int findSecondSmallest(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int num : arr) set.add(num);
        if (set.size() < 2) return -1;

        int minVal = Integer.MAX_VALUE;
        int secondMin = Integer.MAX_VALUE;
        for (int num : arr) {
            if (num < minVal) {
                secondMin = minVal;
                minVal = num;
            } else if (num < secondMin && num != minVal) {
                secondMin = num;
            }
        }
        return secondMin;
    }

    public static void main(String[] args) {
        int[] arr = {30, 20, 10, 50, 60, 40};
        System.out.println("Second Smallest: " + findSecondSmallest(arr));
    }
}

function findSecondSmallest(arr) {
    const unique = [...new Set(arr)];
    if (unique.length < 2) return -1;
    let minVal = Infinity;
    let secondMin = Infinity;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < minVal) {
            secondMin = minVal;
            minVal = arr[i];
        } else if (arr[i] < secondMin && arr[i] !== minVal) {
            secondMin = arr[i];
        }
    }
    return secondMin;
}

// Sample Input
const arr = [30, 20, 10, 50, 60, 40];
console.log('Second Smallest:', findSecondSmallest(arr));

package main

import (
    "fmt"
    "math"
)

func findSecondSmallest(arr []int) int {
    unique := make(map[int]bool)
    for _, val := range arr {
        unique[val] = true
    }
    if len(unique) < 2 {
        return -1
    }

    minVal := math.MaxInt
    secondMin := math.MaxInt
    for _, num := range arr {
        if num < minVal {
            secondMin = minVal
            minVal = num
        } else if num < secondMin && num != minVal {
            secondMin = num
        }
    }
    return secondMin
}

func main() {
    arr := []int{30, 20, 10, 50, 60, 40}
    fmt.Println("Second Smallest:", findSecondSmallest(arr))
}

use std::collections::HashSet;

fn find_second_smallest(arr: &[i32]) -> i32 {
    let unique: HashSet<i32> = arr.iter().cloned().collect();
    if unique.len() < 2 {
        return -1;
    }

    let mut min_val = i32::MAX;
    let mut second_min = i32::MAX;
    for &num in arr {
        if num < min_val {
            second_min = min_val;
            min_val = num;
        } else if num < second_min && num != min_val {
            second_min = num;
        }
    }
    second_min
}

fn main() {
    let arr = [30, 20, 10, 50, 60, 40];
    println!("Second Smallest: {}", find_second_smallest(&arr));
}

fun findSecondSmallest(arr: IntArray): Int {
    val unique = arr.toSet()
    if (unique.size < 2) return -1
    var minVal = Int.MAX_VALUE
    var secondMin = Int.MAX_VALUE
    for (num in arr) {
        if (num < minVal) {
            secondMin = minVal
            minVal = num
        } else if (num < secondMin && num != minVal) {
            secondMin = num
        }
    }
    return secondMin
}

fun main() {
    val arr = intArrayOf(30, 20, 10, 50, 60, 40)
    println("Second Smallest: ${findSecondSmallest(arr)}")
}

import Foundation

func findSecondSmallest(_ arr: [Int]) -> Int {
    let unique = Set(arr)
    if unique.count < 2 {
        return -1
    }
    var minVal = Int.max
    var secondMin = Int.max
    for num in arr {
        if num < minVal {
            secondMin = minVal
            minVal = num
        } else if num < secondMin && num != minVal {
            secondMin = num
        }
    }
    return secondMin
}

let arr = [30, 20, 10, 50, 60, 40]
print("Second Smallest:", findSecondSmallest(arr))

function findSecondSmallest(arr: number[]): number {
    const unique = new Set(arr);
    if (unique.size < 2) return -1;
    let minVal = Number.POSITIVE_INFINITY;
    let secondMin = Number.POSITIVE_INFINITY;
    for (const num of arr) {
        if (num < minVal) {
            secondMin = minVal;
            minVal = num;
        } else if (num < secondMin && num !== minVal) {
            secondMin = num;
        }
    }
    return secondMin;
}

const arr = [30, 20, 10, 50, 60, 40];
console.log("Second Smallest:", findSecondSmallest(arr));

Time complexity

Space complexity

O(1)

The algorithm uses a constant amount of space, with only two variables needed for tracking smallest and second smallest.