714126. Second smallest number
Medium
Second Smallest Number
Slug: second-smallest-number--170647
Difficulty: Medium
Id: 714126
Topic Tags: Greedy, Mathematical, Algorithms
Company Tags: VMWare
Summary
The problem is to find the second smallest number in a given array of distinct integers. This problem involves mathematical and greedy algorithmic concepts.
Detailed Explanation
To solve this problem, we can use a greedy approach by first finding the smallest number in the array and then moving on to the next smallest number. Here's a step-by-step breakdown of the solution:
- Initialize the second smallest number as infinity (or any large value).
- Iterate through the array from left to right.
- For each element, check if it is smaller than the current second smallest number.
- If it is, update the second smallest number.
- Return the second smallest number.
Here's a sample diagram illustrating this approach:
+----------------+
| Array |
+----------------+
|
v
+----------------+
| Smallest |
| (e.g., 1) |
+----------------+
|
v
+----------------+
| Second Smallest|
| (e.g., 2) |
+----------------+
Time complexity: O(n), where n is the size of the array. We need to iterate through the entire array once. Space complexity: O(1), as we only use a constant amount of space to store the second smallest number.
Optimized Solutions
Java
public class Main {
public static int findSecondSmallest(int[] arr) {
int min = Integer.MAX_VALUE;
int secMin = Integer.MAX_VALUE;
for (int num : arr) {
if (num < min) {
secMin = min;
min = num;
} else if (num < secMin && num != min) {
secMin = num;
}
}
return secMin;
}
}