Find 2nd Minimum in Array
Once we've determined the minimum value in an array, the next logical step in certain situations is to find the second smallest value. This might represent the next lowest cost, a close competitor's score, or the second least critical threshold. Let’s see how to approach this task while carefully handling edge cases.
Given an array of integers, we need to find the 2nd minimum element in the array. The function should print the 2nd minimum value found in the array. If no such value is found print -1.
Example
Input: nums = [3, 7, 11, 2, 1, 10]
Output: 7
Explanation: The 2nd minimum element in the array is 7.
Input: nums = [3, 4, 1, 5, 2, 5, 1, 10]
Output: 2
Explanation: The 2nd minimum element in the array is 2.
Intuition
Imagine you're back in that queue, but now your goal is to find not just the shortest person but the second shortest. You start by assuming the first person you see is the shortest. As you move down the line, you keep track of the shortest person you've seen so far. But this time, you also need to keep track of the second shortest person.
How To Think About It
You begin by assuming the first person in line is both the shortest and the second shortest. However, as you move along the queue and find someone shorter, you need to update both your shortest and second shortest. If the new person is shorter than your current shortest, the previous shortest becomes the second shortest.
For each person in line, you compare them to your current shortest. If they are shorter, you update your shortest to this new person, and the previous shortest becomes the second shortest. If they aren’t shorter but still shorter than your second shortest, you only update your second shortest.
By the time you reach the end of the queue, the person you’ve identified as the second shortest will be the second shortest in the entire line.
Applying This Intuition to the Array
Start by assuming the first element in the array is both the minimum and second minimum. This gives you a reference point, just like starting with the first person in the queue.
As you traverse the array, compare each element with the current minimum and second minimum:
- If the current element is less than the minimum, update the second minimum to the previous minimum and update the minimum to the current element.
- If the current element is not less than the minimum but less than the second minimum, then update the second minimum to the current element.
Continue this process until you’ve gone through all the elements. By the end, your second minimum variable will hold the second lowest value in the array.
Let’s Walk Through an Example:
Consider the array nums = [3, 7, 11, 2, 1, 10].
- Start by assuming minElement = 3 and secondMinElement = INT_MAX (since there’s no valid second minimum at the start).
Why initialize 2nd Minimum as INT_MAX?
Initializing secondMinElement with INT_MAX ensures that any valid array element will be smaller, allowing it to be correctly updated during traversal. This approach handles cases where the array may contain large or uniform values or there is no 2nd smaller element. Without this, if no smaller value is found, secondMinElement might remain incorrectly initialized. This guarantees a valid comparison throughout the process.
Approach
The goal of the problem is to find the second minimum element in an array of integers. If there is no valid second minimum (e.g., if the array has fewer than two distinct elements), the function should return -1. Here's a detailed step-by-step approach to solving this problem:
1. Initialization:
Start by initializing two variables:
- minElement to INT_MAX (the largest possible integer).
- secondMinElement to INT_MAX (the same initial value).
This ensures that even if all the elements are positive, we have valid initial comparison points.
- minElement will keep track of the smallest element encountered so far.
- secondMinElement will store the second smallest element.
2. Iterate through the Array:
Loop through each element of the array using a for loop.
3. Condition 1 (If element is less than minElement):
- If the current element is smaller than minElement, it means we've found a new smallest element.
- Update secondMinElement to the old minElement (since the previous smallest element will now become the second smallest).
- Update minElement to the current element (since it is now the smallest).
4. Condition 2 (If element is between minElement and secondMinElement):
- If the current element is greater than minElement but smaller than secondMinElement, update secondMinElement to the current element.
- This ensures that secondMinElement always stores the second smallest distinct value.
5. Edge Case Handling:
After iterating through the array:
- If secondMinElement is still equal to INT_MAX, it means a valid second minimum wasn't found (i.e., the array has fewer than two distinct elements).
- In this case, print -1.
- Otherwise, print the value of secondMinElement.
6. Return the Result:
- Print the second minimum element, or -1 if no valid second minimum exists.
Dry Run
Input: nums = [3, 7, 11, 2, 1, 10].
Initialization:
- minElement = INT_MAX (a very large value, initially considered the smallest value).
- secondMinElement = INT_MAX (similarly, the second smallest is initialized to the same large value).
First Iteration (i = 0):
- nums[i] = 3
- Check condition: 3 < minElement (3 < INT_MAX) is true.
- Update secondMinElement = minElement = INT_MAX
- Update minElement = 3
- After the first iteration, the values are:
- minElement = 3
- secondMinElement = INT_MAX
Second Iteration (i = 1):
- nums[i] = 7
- Check condition: 7 < minElement (7 < 3) is false.
- Check next condition: 7 < secondMinElement and 7 > minElement (7 < INT_MAX and 7 > 3) is true.
- Update secondMinElement = 7
- After the second iteration, the values are:
- minElement = 3
- secondMinElement = 7
Third Iteration (i = 2):
- nums[i] = 11
- Check condition: 11 < minElement (11 < 3) is false.
- Check next condition: 11 < secondMinElement and 11 > minElement (11 < 7 and 11 > 3) is false.
- After the third iteration, the values are:
- minElement = 3
- secondMinElement = 7
Fourth Iteration (i = 3):
- nums[i] = 2
- Check condition: 2 < minElement (2 < 3) is true.
- Update secondMinElement = minElement = 3
- Update minElement = 2
- After the fourth iteration, the values are:
- minElement = 2
- secondMinElement = 3
Fifth Iteration (i = 4):
- nums[i] = 1
- Check condition: 1 < minElement (1 < 2) is true.
- Update secondMinElement = minElement = 2
- Update minElement = 1
- After the fifth iteration, the values are:
- minElement = 1
- secondMinElement = 2
Sixth Iteration (i = 5):
- nums[i] = 10
- Check condition: 10 < minElement (10 < 1) is false.
- Check next condition: 10 < secondMinElement and 10 > minElement (10 < 2 and 10 > 1) is false.
- After the sixth iteration, the values are:
- minElement = 1
- secondMinElement = 2
End of Iteration:
The loop ends after checking all elements of the array.
Final Check:
Since secondMinElement = 2, which is not equal to INT_MAX, we print the second maximum element: 2.
Final Output:
The second maximum element in the array is 10.
Code for All Languages
C++
// Function to find the 2nd minimum element in the array
void findSecondMinElement(int nums[], int n) {
// Initialize the minimum and second minimum with the largest possible value
int minElement = INT_MAX;
int secondMinElement = INT_MAX;
// Iterate through the array to find the minimum element
for (int i = 0; i < n; ++i) {
if (nums[i] < minElement) {
// Update second minimum
secondMinElement = minElement;
// Update minimum
minElement = nums[i];
}
else if (nums[i] < secondMinElement && nums[i] > minElement) {
// Update second minimum if it's greater than minElement and less than the current secondMinElement
secondMinElement = nums[i];
}
}
// Check if a valid second minimum was found
if (secondMinElement == INT_MAX) {
// Print -1 if no valid second minimum found
cout << -1 << endl;
}
else {
// Print the 2nd minimum element found in the array
cout << secondMinElement << endl;
}
}
Java
public class Main {
// Function to find the 2nd minimum element in the array
public static void findSecondMinElement(int[] nums, int n) {
// Initialize the minimum and second minimum with the largest possible value
int minElement = Integer.MAX_VALUE;
int secondMinElement = Integer.MAX_VALUE;
// Iterate through the array to find the minimum element
for (int i = 0; i < n; ++i) {
if (nums[i] < minElement) {
// Update second minimum
secondMinElement = minElement;
// Update minimum
minElement = nums[i];
} else if (nums[i] < secondMinElement && nums[i] > minElement) {
// Update second minimum if it's greater than minElement and less than the current secondMinElement
secondMinElement = nums[i];
}
}
// Check if a valid second minimum was found
if (secondMinElement == Integer.MAX_VALUE) {
// Print -1 if no valid second minimum found
System.out.println(-1);
} else {
// Print the 2nd minimum element found in the array
System.out.println(secondMinElement);
}
}
}
Python
# Function to find the 2nd minimum element in the array
def find_second_min_element(nums, n):
# Initialize the minimum and second minimum with the largest possible value
min_element = float('inf')
second_min_element = float('inf')
# Iterate through the array to find the minimum element
for num in nums:
if num < min_element:
# Update second minimum
second_min_element = min_element
# Update minimum
min_element = num
elif num < second_min_element and num > min_element:
# Update second minimum if it's greater than min_element and less than the current second_min_element
second_min_element = num
# Check if a valid second minimum was found
if second_min_element == float('inf'):
# Print -1 if no valid second minimum found
print(-1)
else:
# Print the 2nd minimum element found in the array
print(second_min_element)Javascript
// Function to find the 2nd minimum element in the array
function findSecondMinElement(nums) {
// Initialize the minimum and second minimum with the largest possible value
let minElement = Infinity;
let secondMinElement = Infinity;
// Iterate through the array to find the minimum element
for (let num of nums) {
if (num < minElement) {
// Update second minimum
secondMinElement = minElement;
// Update minimum
minElement = num;
} else if (num < secondMinElement && num > minElement) {
// Update second minimum if it's greater than minElement and less than the current secondMinElement
secondMinElement = num;
}
}
// Check if a valid second minimum was found
if (secondMinElement === Infinity) {
// Print -1 if no valid second minimum found
console.log(-1);
} else {
// Print the 2nd minimum element found in the array
console.log(secondMinElement);
}
}Time Complexity
We need to traverse all n elements in the array exactly once. During this single pass through the array, we compare each element to find the minimum and second minimum elements.Each comparison operation (to update minElement or secondMinElement) takes constant time, O(1). Since these operations are repeated for every element in the array.The overall time complexity remains O(n).
Space Complexity
The total space complexity consists of two parts: the space required for the input array and the auxiliary space used by the algorithm.
Total Space Complexity:The total space complexity is O(n) because the input array nums[] takes up O(n) space. This is necessary to store the n elements.
Auxiliary Space Complexity:The auxiliary space complexity is O(1). This is because we only use a constant amount of extra space, specifically for the variables minElement and secondMinElement. These variables do not depend on the size of the array and therefore take up constant space.