Find the Second Smallest Element in an Array
Brute Force Approach
Idea
The simplest way to solve this problem is to sort the array and return the second element. Sorting ensures that the smallest element is at the beginning and the second smallest element comes next.
Steps
- Sort the array in ascending order.
- Return the second element of the sorted array.
Time Complexity
- Sorting takes O(n log n), where
n is the size of the array.
Space Complexity
- The space complexity is O(1) if the sorting is done in place, otherwise O(n) for additional memory needed.
Example Code
Dry Run
For array [5, 2, 8, 1, 3]:
- Sort the array to get
[1, 2, 3, 5, 8].
- Return the second element, which is
2.
Efficient Approach
Idea
A more efficient way is to traverse the array only once and find both the smallest and second smallest elements.
Steps
- Initialize two variables
min1 and min2 to hold the smallest and second smallest values.
- Traverse the array:
- Update
min1 if the current element is smaller.
- Update
min2 if the current element is larger than min1 but smaller than the previous min2.
Time Complexity
- The time complexity is O(n) since we are traversing the array only once.
Space Complexity
- The space complexity is O(1) because only a fixed amount of extra space is used.
Example Code
Dry Run
For array [5, 2, 8, 1, 3]:
- Initialize
min1 = Infinity, min2 = Infinity.
- Traverse the array:
- Compare 5:
min1 = 5, min2 = Infinity.
- Compare 2:
min1 = 2, min2 = 5.
- Compare 8: No update.
- Compare 1:
min1 = 1, min2 = 2.
- Compare 3: No update.
- Return
min2, which is 2.
Example Test Cases
Test Case 1
Input: [5, 2, 8, 1, 3]
Output: 2
Test Case 2
Input: [12, 13, 5, 10, 34, 1]
Output: 5
Test Case 3
Input: [1, 1, 1, 1]
Output: null (No second distinct smallest element)
Complexity Analysis
Brute Force Approach
- Time Complexity:
O(n log n) (due to sorting)
- Space Complexity:
O(1) (if sorting in place) or O(n) (if extra space is used)
Efficient Approach
- Time Complexity:
O(n) (single traversal of the array)
- Space Complexity:
O(1) (constant extra space)
Conclusion
The brute force approach is simple but inefficient due to the sorting operation. The efficient approach solves the problem in linear time with constant space, making it a better choice for larger arrays.