Find Second Smallest in Array

Find Second Smallest in Array using Loop - Optimal Algorithm

Topic Contents

Problem Examples Solution Visualization Algorithm Code Time Space Detailed Example

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 smallest
[7, 7, 7, 7]	-1	All elements are the same, no second smallest
[5]	-1	Only one element, second smallest doesn't exist
[]	-1	Empty array, no elements to compare
[9, 3, 6, 3, 5]	5	3 is the smallest, 5 is the smallest value strictly greater than 3
[2, 1]	2	1 is smallest, 2 is second smallest
[100, 50, 50, 50, 60]	60	50 is smallest, 60 is the next smallest value
[5, 4, 3, 2, 1]	2	1 is smallest, 2 is next smallest

Solution❯

To find the second smallest element in an array, we need to track the two smallest distinct values during a single pass through the array.

We begin by assuming that both the min_val (smallest value) and second_min are Infinity. As we loop through the array, we update these variables as follows:

If the current number is less than min_val, then we found a new smallest number. So, the previous min_val becomes the new second_min, and we update min_val.
If the current number is not equal to min_val but less than second_min, then it becomes our new second smallest number.

This way, we only pass through the array once and always keep track of the two smallest distinct numbers.

Edge Case Handling

Empty Array: There are no elements to compare, so we return -1.
Only One Element: We can't find a second smallest if there's only one value, so return -1.
All Elements Equal: If all numbers are the same, there is no second distinct value, so we return -1.

Why This Approach is Optimal

This solution uses only one pass through the array (O(n) time) and constant space (O(1)), making it optimal in terms of both time and memory. It avoids sorting or using extra space like sets or arrays to find unique values.

By comparing carefully and avoiding duplicates, this approach ensures that only distinct values are considered, which is crucial for finding the second smallest correctly.

Visualization

Algorithm Steps

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

Code

Python

JavaScript

Java

C++

def find_second_smallest(arr):
    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))

Time Complexity

Case	Time Complexity	Explanation
Best Case	O(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 Case	O(n)	The algorithm iterates through the array exactly once, making one comparison per element.
Average Case	O(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" } }