.png)
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
Initialize
smallest = +∞ secondSmallest = +∞- Traverse the array
- For each element:
- If element < smallest
→ update secondSmallest = smallest
→ update smallest = element - Else if element > smallest AND element < secondSmallest
→ update secondSmallest = element
- If element < smallest
- 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 = +∞
| Element | Action |
|---|---|
| 12 | smallest = 12 |
| 35 | secondSmallest = 35 |
| 1 | secondSmallest = 12, smallest = 1 |
| 10 | secondSmallest = 10 |
| 34 | ignored |
Result
Second Smallest Element = 10
Time and Space Complexity
| Metric | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(1) |
Language-wise Implementation
C Implementation
#include<stdio.h>
#include<limits.h>
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<iostream>
#include<climits>
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.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
