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 scanning the line, trying to keep track of both the shortest and the second shortest people. You’ll need to update both of them as you encounter shorter individuals down the line.
How To Think About It
Instead of assuming the first person is both the shortest and second shortest, let’s be a bit more robust from the start:
Initialize both the minElement and the secondMinElement with INT_MAX.
Why?
This ensures that any number in the array will be smaller than this initial placeholder and can update it. It also safely handles arrays with:
Very large numbers
Negative values
Or uniform elements
Alternatively, you can start with:
minElement = arr[0]
secondMinElement = INT_MAX
This works too if you're confident the array has at least one element.
Traversal Logic – Step by Step
As you go through the array:
- If the current number is less than minElement, it becomes your new minimum.
The previous minElement now becomes your new secondMinElement. - If the current number is not equal to minElement (to handle duplicates), but less than secondMinElement, then just update the second minimum.
Let’s walk through an example:
nums = [3, 7, 11, 2, 1, 10]
Start:
minElement = INT_MAX
secondMinElement = INT_MAX
As you loop through each number:
- You update minElement whenever a smaller number is found.
- If a number is greater than minElement but smaller than secondMinElement, update secondMinElement.
By the end:
minElement = 1
secondMinElement = 2
Done!
What About Duplicates?
An important detail! Suppose the array is:
[1, 1, 2, 3]
Now, what should be considered the second minimum?
- Should it be 1 again (the duplicate)?
- Or should it be 2, the next distinct smallest number?
This is something you should always ask the interviewer to clarify: “Should second minimum mean second distinct smallest?”
If the Answer Is “Distinct”:
A safe and clear approach is:
- First loop: Find the minimum.
- Second loop: Find the smallest number that is greater than minElement.
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 : O(n)
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 : O(1)
Auxiliary Space Complexity: This refers to any extra space used by the algorithm that is independent of the input space and output space. In this case, 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. so the auxiliary space complexity is O(1).
Total Space Complexity: This includes the space required for the input, output and extra space used by the algorithm as well. The input array nums[] is of size n, So the space required for input space is O(n). No output space is used. Also, the algorithm too takes constant extra space.
Total Space Complexity = O(n) + O(1) + O(1) = O(n)