Find Second Smallest in Array using Loop - Optimal Algorithm

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace Detailed Exmpl

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

Visualization Player

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.

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

Python
JavaScript
Java
C++
C
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))

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" } }