Array V
In problem-solving, identifying the least or smallest value in a dataset is a crucial skill, as it often represents the baseline, minimum requirement, or the most critical limiting factor. For instance, finding the minimum element in an array helps us determine the lowest score, minimum cost, or the least significant value in a given context. Let’s explore how to efficiently achieve this fundamental task.
13. Given an array of integers, we need to find the minimum element in the array. The function should print the minimum value found in the array.
Example
Input: nums = [3, 7, 11, 2, 1, 10]
Output: 1
Explanation: The minimum element in the array is 1.
Input: nums = [3, 4, 9, 5, 2, 5, 9, 10]
Output: 2
Explanation: The minimum element in the array is 2.
Intuition
Imagine you're in a queue of people, and your goal is to find the shortest person. You start by assuming that the first person you see is the shortest. As you walk down the line, you compare each person with the shortest one you've seen so far. If you find someone shorter, you update your "shortest" to that person. By the time you reach the end of the queue, the last person you identified as the shortest is indeed the shortest person in the entire line. This is exactly how the algorithm for finding the minimum element in an array works.
We will use this logic to find the minimum number in a given array.
To solve this problem, we need to traverse the entire array (just like walking along the entire queue) and keep track of the minimum element (shortest person) encountered during the traversal. We start by assuming that the first element in the array is the minimum.
Why assume the minimum as the first element (nums[0]) in the beginning?
Assuming the first element to be the minimum initially provides a reference point for comparison. As we iterate through the array, we compare each element with this assumed minimum, updating it whenever we find a smaller value. This method simplifies finding the minimum by ensuring we always have the smallest value encountered so far.
Let's say our array is nums = [3, 7, 11, 2, 1, 10]. Initially, we assume the minimum element is 3 (the first element). We then iterate through the array, starting from the second element. For each element, we compare it with the current minimum element. If the current element is smaller than the current minimum, we update the minimum element to be the current element.
Approach
- Initialize the minimum value as the first element of the array (nums[0]). This acts as our starting point for comparison. Iterate through the array starting from the second element (i = 1).
For each element, compare it with the current minimum value.If the current element is smaller, update the minimum value to this element.
- After the loop finishes, the minimum value is guaranteed to hold the smallest element in the array.
- Print the minimum value.
Dry Run
Initialization:
- The array nums contains: [3, 7, 11, 2, 1, 10].
- The size of the array
nis 6. - The variable minElement is initialized to the first element of the array, minElement = nums[0] = 3.
Iteration Process:
- First Iteration (i = 1):
- Current element: nums[1] = 7.
- Compare: Is nums[1] < minElement? (7 < 3).
- Result: No. The value of minElement remains 3.
- Second Iteration (i = 2):
- Current element: nums[2] = 11.
- Compare: Is nums[2] < minElement? (11 < 3).
- Result: No. The value of minElement remains 3.
- Third Iteration (i = 3):
- Current element: nums[3] = 2.
- Compare: Is nums[3] < minElement? (2 < 3).
- Result: Yes. Update minElement to 2. Now, minElement = 2.
- Fourth Iteration (i = 4):
- Current element: nums[4] = 1.
- Compare: Is nums[4] < minElement? (1 < 2).
- Result: Yes. Update minElement to 1. Now, minElement = 1.
- Fifth Iteration (i = 5):
- Current element: nums[5] = 10.
- Compare: Is nums[5] < minElement? (10 < 1).
- Result: No. The value of minElement remains 1.
Final Step:
After completing all iterations, the smallest element in the array is found to be minElement = 1.
Output:
The minimum element is: 1.
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to find the minimum element in the array
void findMinElement(int nums[], int n) {
// Initialize the minimum with the first element of the array
int minElement = nums[0];
// Iterate through the array starting from the second element
for (int i = 1; i < n; ++i) {
// Compare the current element with the minimum element
if (nums[i] < minElement) {
// Update the minimum element if the current element is smaller
minElement = nums[i];
}
}
// Print the minimum element found in the array
cout << "The minimum element is: " << minElement << endl;
}Java
import java.util.Scanner;
public class LearnYard {
// Function to find the minimum element in the array
static void findMinElement(int[] nums, int n) {
// Initialize the minimum with the first element of the array
int minElement = nums[0];
// Iterate through the array starting from the second element
for (int i = 1; i < n; i++) {
// Compare the current element with the minimum element
if (nums[i] < minElement) {
// Update the minimum element if the current element is smaller
minElement = nums[i];
}
}
// Print the minimum element found in the array
System.out.println("The minimum element is: " + minElement);
}
}
Python
def find_min_element(nums):
# Initialize the minimum with the first element of the array
min_element = nums[0]
# Iterate through the array starting from the second element
for i in range(1, len(nums)):
# Compare the current element with the minimum element
if nums[i] < min_element:
# Update the minimum element if the current element is smaller
min_element = nums[i]
# Print the minimum element found in the array
print(f"The minimum element is: {min_element}")
Javascript
function findMinElement(nums) {
// Initialize the minimum with the first element of the array
let minElement = nums[0];
// Iterate through the array starting from the second element
for (let i = 1; i < nums.length; i++) {
// Compare the current element with the minimum element
if (nums[i] < minElement) {
// Update the minimum element if the current element is smaller
minElement = nums[i];
}
}
// Print the minimum element found in the array
console.log("The minimum element is: " + minElement);
}Time Complexity
The time complexity of this solution is linear, O(n), because we need to traverse all n elements in the array exactly once to determine the minimum.
Space Complexity
- Total Space Complexity: The total space complexity is O(n) because the input array takes up O(n) space.
- Auxiliary Space: The auxiliary space complexity is O(1) since we only need a single variable to keep track of the minimum element, which does not depend on the size of the array.
After identifying the maximum value in an array, the next step in some scenarios is to find the second-highest value. This could represent the runner-up score or the next best option in a dataset. Let’s explore how to determine the second maximum efficiently, ensuring we account for all edge cases.
14. Given an array of integers, we need to find the 2nd maximum element in the array. The function should print the 2nd maximum value found in the array. If no such value is found print -1.
Example
Input: nums = [3, 7, 11, 2, 1, 10]
Output: 10
Explanation: The 2nd maximum element in the array is 10
Input: nums = [3, 4, 1, 5, 2, 5, 1, 10]
Output: 5
Explanation: The 2nd maximum element in the array is 5.
Intuition
Imagine you're back in that queue, but now your goal is to find not just the tallest person but the second tallest. You start by assuming the first person you see is the tallest. As you move down the line, you keep track of the tallest person you've seen so far. But this time, you also need to keep track of the second tallest person.
How To Think About It
- You begin by assuming the first person in line is both the tallest and the second tallest. However, as you move along the queue and find someone taller, you need to update both your tallest and second tallest. If the new person is taller than your current tallest, the previous tallest becomes the second tallest.
- For each person in line, you compare them to your current tallest. If they are taller, you update your tallest to this new person, and the previous tallest becomes the second tallest. If they aren’t taller but still taller than your second tallest, you only update your second tallest.
- By the time you reach the end of the queue, the person you’ve identified as the second tallest will be the second tallest in the entire line.
Applying This Intuition to the Array
- Start by assuming the first element in the array is both the maximum and second maximum. This gives you a reference point, just like starting with the first person(in finding maximum problem) in the queue.
- As you traverse the array, compare each element with the current maximum and second maximum:
- If the current element is greater than the maximum, update the second maximum to the previous maximum and update the maximum to the current element.
- If the current element is not greater than the maximum but greater than the second maximum, then update the second maximum to the current element.
- Continue this process until you’ve gone through all the elements. By the end, your second maximum variable will hold the second highest value in the array.
Let’s walk through an example:
Consider the array nums = [3, 7, 11, 2, 1, 10].
- Start by assuming maxElement = 3 and secondMaxElement = INT_MIN (since there’s no valid second maximum at the start).
Why initialize the 2nd Maximum as INT_MIN?
Initializing a secondMaxElement with INT_MIN ensures that any valid array element will be larger, allowing it to be correctly updated during traversal. This approach handles cases where the array may contain very small or uniform values or there is no 2nd larger element. Without this, if no larger value is found, secondMaxElement might remain incorrectly initialized. This guarantees a valid comparison throughout the process.
Approach
The goal of the problem is to find the second maximum element in an array of integers. If there is no valid second maximum (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:
- Initialization:
- Start by initializing two variables maxElement and secondMaxElement to INT_MIN (the smallest possible integer). This ensures that even if all the elements are negative, we have a valid initial comparison comparison point.
- maxElement will keep track of the largest element encountered so far.
- secondMaxElement will store the second largest element.
- Start by initializing two variables maxElement and secondMaxElement to INT_MIN (the smallest possible integer). This ensures that even if all the elements are negative, we have a valid initial comparison comparison point.
- Iterate through the Array:
Loop through each element of the array using a for loop.
- Condition 1 (If element is greater than maxElement):
- If the current element is greater than maxElement, it means we've found a new largest element.
- Update secondMaxElement to the old maxElement (since the previous largest element will now become the second largest).
- Update maxElement to the current element (since it is now the largest).
- Condition 2 (If element is between maxElement and secondMaxElement):
- If the current element is smaller than maxElement but larger than secondMaxElement, update secondMaxElement to the current element.
- This ensures that secondMaxElement always stores the second largest distinct value.
- Edge Case Handling:
- After iterating through the array, if secondMaxElement is still INT_MIN, it means a valid second maximum wasn't found (i.e., the array has fewer than two distinct elements). In this case, print -1.
- Otherwise, print the value of secondMaxElement.
4. Return the Result:
- Print the second maximum element, or -1 if no valid second maximum exists.
Dry Run
- Initialize Variables:
- maxElement = INT_MIN (or -∞ in practical terms)
- secondMaxElement = INT_MIN (or -∞)
- Start Iterating through the Array:First Iteration (i = 0):
- nums[0] = 3
- Check if nums[0] > maxElement → 3 > -∞, which is true.
- So, update secondMaxElement = maxElement = -∞, and then maxElement = nums[0] = 3.
- maxElement = 3, secondMaxElement = -∞
- Second Iteration (i = 1):
- nums[1] = 7
- Check if nums[1] > maxElement → 7 > 3, which is true.
- So, update secondMaxElement = maxElement = 3, and then maxElement = nums[1] = 7.
- maxElement = 7, secondMaxElement = 3
- Third Iteration (i = 2):
- nums[2] = 11
- Check if nums[2] > maxElement → 11 > 7, which is true.
- So, update secondMaxElement = maxElement = 7, and then maxElement = nums[2] = 11.
- maxElement = 11, secondMaxElement = 7
- Fourth Iteration (i = 3):
- nums[3] = 2
- Check if nums[3] > maxElement → 2 > 11, which is false.
- Check if nums[3] > secondMaxElement && nums[3] < maxElement → 2 > 7 && 2 < 11, which is false.
- No changes to maxElement or secondMaxElement.
- maxElement = 11, secondMaxElement = 7
- Fifth Iteration (i = 4):
- nums[4] = 1
- Check if nums[4] > maxElement → 1 > 11, which is false.
- Check if nums[4] > secondMaxElement && nums[4] < maxElement → 1 > 7 && 1 < 11, which is false.
- No changes to maxElement or secondMaxElement.
- maxElement = 11, secondMaxElement = 7
- Sixth Iteration (i = 5):
- nums[5] = 10
- Check if nums[5] > maxElement → 10 > 11, which is false.
- Check if nums[5] > secondMaxElement && nums[5] < maxElement → 10 > 7 && 10 < 11, which is true.
- So, update secondMaxElement = nums[5] = 10.
- maxElement = 11, secondMaxElement = 10
- End of Iteration:
- The loop ends after checking all elements of the array.
- Final Check:
- Since secondMaxElement = 10, which is not equal to INT_MIN, we print the second maximum element: 10.
Final Output:
The second maximum element in the array is 10.
Code for All Languages
C++
#include <iostream>
#include <climits>
using namespace std;
// Function to find the 2nd maximum element in the array
void findSecondMaxElement(int nums[], int n) {
// Initialize the maximum and second maximum with the smallest possible value
int maxElement = INT_MIN;
int secondMaxElement = INT_MIN;
// Iterate through the array to find the maximum element
for (int i = 0; i < n; ++i) {
if (nums[i] > maxElement) {
// Update second maximum
secondMaxElement = maxElement;
// Update maximum
maxElement = nums[i];
}
else if (nums[i] > secondMaxElement && nums[i] < maxElement) {
// Update second maximum if it's less than maxElement and
// greater than the current secondMaxElement
secondMaxElement = nums[i];
}
}
// Check if a valid second maximum was found
if (secondMaxElement == INT_MIN) {
// Print -1 if no valid second maximum found
cout << -1 << endl;
}
else {
// Print the 2nd maximum element found in the array
cout << secondMaxElement << endl;
}
}
int main() {
int n;
// Read size of the array
cin >> n;
// Declare the array with size n
int nums[n];
// Read array elements
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
// Find and print the 2nd maximum element in the array
findSecondMaxElement(nums, n);
return 0;
}
Java
import java.util.Scanner;
public class LearnYard {
// Function to find the 2nd maximum element in the array
public static void findSecondMaxElement(int[] nums, int n) {
// Initialize the maximum and second maximum with the smallest possible value
int maxElement = Integer.MIN_VALUE;
int secondMaxElement = Integer.MIN_VALUE;
// Iterate through the array to find the maximum element
for (int i = 0; i < n; ++i) {
if (nums[i] > maxElement) {
// Update second maximum
secondMaxElement = maxElement;
// Update maximum
maxElement = nums[i];
}
else if (nums[i] > secondMaxElement && nums[i] < maxElement) {
// Update second maximum if it's less than maxElement and greater than the current secondMaxElement
secondMaxElement = nums[i];
}
}
// Check if a valid second maximum was found
if (secondMaxElement == Integer.MIN_VALUE) {
System.out.println(-1);
}
else {
// Print the 2nd maximum element found in the array
System.out.println(secondMaxElement);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Read size of the array
int n = scanner.nextInt();
// Declare the array with size n
int[] nums = new int[n];
// Read array elements
for (int i = 0; i < n; ++i) {
nums[i] = scanner.nextInt();
}
// Find and print the 2nd maximum element in the array
findSecondMaxElement(nums, n);
}
}
Python
# Function to find the 2nd maximum element in the array
def findSecondMaxElement(nums, n):
# Initialize the maximum and second maximum with the smallest possible value
maxElement = float('-inf')
secondMaxElement = float('-inf')
# Iterate through the array to find the maximum element
for num in nums:
if num > maxElement:
# Update second maximum
secondMaxElement = maxElement
# Update maximum
maxElement = num
elif num > secondMaxElement and num < maxElement:
# Update second maximum if it's less than maxElement and greater than the current secondMaxElement
secondMaxElement = num
# Check if a valid second maximum was found
if secondMaxElement == float('-inf'):
print(-1)
else:
# Print the 2nd maximum element found in the array
print(secondMaxElement)
# Read size of the array
n = int(input())
# Read array elements
nums = list(map(int, input().split()))
# Find and print the 2nd maximum element in the array
findSecondMaxElement(nums, n)
Javascript
// Function to find the 2nd maximum element in the array
function findSecondMaxElement(nums, n) {
// Initialize the maximum and second maximum with the smallest possible value
let maxElement = -Infinity;
let secondMaxElement = -Infinity;
// Iterate through the array to find the maximum element
for (let i = 0; i < n; ++i) {
if (nums[i] > maxElement) {
// Update second maximum
secondMaxElement = maxElement;
// Update maximum
maxElement = nums[i];
} else if (nums[i] > secondMaxElement && nums[i] < maxElement) {
// Update second maximum if it's less than maxElement and greater than the current secondMaxElement
secondMaxElement = nums[i];
}
}
// Check if a valid second maximum was found
if (secondMaxElement === -Infinity) {
console.log(-1);
} else {
// Print the 2nd maximum element found in the array
console.log(secondMaxElement);
}
}
// Read size of the array
let n = parseInt(prompt());
// Read array elements
let nums = prompt().split(' ').map(Number);
// Find and print the 2nd maximum element in the array
findSecondMaxElement(nums, n);
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 maximum and second maximum elements.Each comparison operation (to update maxElement or secondMaxElement) 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 maxElement and secondMaxElement. These variables do not depend on the size of the array and therefore take up constant space.
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.
15. 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++
#include <iostream>
#include <climits>
using namespace std;
// 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;
}
}
int main() {
// Size of the array
int n;
cin >> n;
// Example input array
int nums[n];
// Reading array elements
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
// Find and print the 2nd minimum element in the array
findSecondMinElement(nums, n);
return 0;
}
Java
import java.util.Scanner;
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);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Size of the array
int n = sc.nextInt();
// Input array
int[] nums = new int[n];
// Reading array elements
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
// Find and print the 2nd minimum element in the array
findSecondMinElement(nums, n);
sc.close();
}
}
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)
# Input
n = int(input()) # Array size
nums = list(map(int, input().split())) # Array elements
# Find and print the 2nd minimum element in the array
find_second_min_element(nums, n)
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);
}
}
// Input
let n = parseInt(prompt()); // Array size
let nums = prompt().split(' ').map(Number); // Array elements
// Find and print the 2nd minimum element in the array
findSecondMinElement(nums);
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.