Find Second Smallest in Array using Loop - Optimal Algorithm

Visualization Player

Problem Statement

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.

Examples

Input Array Second Smallest Description
[3, 1, 4, 2] 2 1 is the smallest, 2 is the next smallestVisualization
[7, 7, 7, 7] -1 All elements are the same, no second smallestVisualization
[5] -1 Only one element, second smallest doesn't existVisualization
[] -1 Empty array, no elements to compareVisualization
[9, 3, 6, 3, 5] 5 3 is the smallest, 5 is the smallest value strictly greater than 3Visualization
[2, 1] 2 1 is smallest, 2 is second smallestVisualization
[100, 50, 50, 50, 60] 60 50 is smallest, 60 is the next smallest valueVisualization
[5, 4, 3, 2, 1] 2 1 is smallest, 2 is next smallestVisualization

Solution

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.

Algorithm Steps

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)Even in the best case, all elements must be checked at least once to ensure the smallest and second smallest are correctly identified.
Average CaseO(n)The algorithm iterates through the array exactly once, making one comparison per element.
Worst CaseO(n)Regardless of element arrangement, all values must be visited to determine the second smallest accurately.

Space Complexity

O(1)

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

Detailed Step by Step Example

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

{ "array": [30,20,10,50,60,40], "showIndices": true }

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.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [0], "labels": {"0":"i"} }
{ "array": ["",30,null], "showIndices": false, "emptyIndices": [1, 2], "emptyCompIndices": [0], "labels": { "1": "min", "2": "secondMin" } }

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.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [1], "labels": {"1":"i"} }
{ "array": ["",20,30], "showIndices": false, "emptyIndices": [1, 2], "emptyCompIndices": [0], "labels": { "1": "min", "2": "secondMin" } }

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.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [2], "labels": {"2":"i"} }
{ "array": ["",10,20], "showIndices": false, "emptyIndices": [1, 2], "emptyCompIndices": [0], "labels": { "1": "min", "2": "secondMin" } }

Check index 3

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

No update required.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [3], "labels": {"3":"i"} }
{ "array": ["",10,20], "showIndices": false, "emptyIndices": [1, 2], "emptyCompIndices": [0], "labels": { "1": "min", "2": "secondMin" } }

Check index 4

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

No update required.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [4], "labels": {"4":"i"} }
{ "array": ["",10,20], "showIndices": false, "emptyIndices": [1, 2], "emptyCompIndices": [0], "labels": { "1": "min", "2": "secondMin" } }

Check index 5

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

No update required.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [5], "labels": {"5":"i"} }
{ "array": ["",10,20], "showIndices": false, "emptyIndices": [1, 2], "emptyCompIndices": [0], "labels": { "1": "min", "2": "secondMin" } }

Final Result:

Second Smallest Element = 20

{ "array": [30,20,10,50,60,40], "showIndices": true, "labels": { "2": "min", "1": "secondMin" } }
{ "array": ["",10,20], "showIndices": false, "emptyIndices": [1, 2], "emptyCompIndices": [0], "labels": { "1": "min", "2": "secondMin" } }

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...