703436. First and Second Smallests
Basic
First and Second Smallests
Slug: find-the-smallest-and-second-smallest-element-in-an-array3226
Difficulty: Basic
Id: 703436
Topic Tags: Arrays, Data Structures
Company Tags: Amazon, Goldman Sachs
Summary
Find the first and second smallest elements in an array. This problem involves basic array manipulation and finding the minimum and maximum values in an array.
Detailed Explanation
To solve this problem, we can iterate through the array once to find the smallest element and then again to find the next smallest element that is not equal to the previous one.
Here's a step-by-step breakdown of the solution:
- Initialize two variables
minandsecond_minto store the smallest and second smallest elements respectively. - Iterate through the array from left to right.
- In each iteration, check if the current element is smaller than
min. If it is, updateminwith the current element. - Continue iterating until the end of the array.
- After the first pass,
minwill store the smallest element andsecond_minwill be updated to the second smallest element (which could be equal tominif there are duplicate elements). - Return
minandsecond_minas the first and second smallest elements.
Time complexity: O(n) where n is the number of elements in the array. Space complexity: O(1) since we only use a constant amount of space to store the minimum and second minimum values.
Optimized Solutions
Java
public class FirstAndSecondSmallest {
public static int[] find(int[] arr) {
int min = arr[0];
int second_min = Integer.MAX_VALUE;
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
second_min = min;
min = arr[i];
} else if (arr[i] < second_min && arr[i] != min) {
second_min = arr[i];
}
}
return new int[]{min, second_min};
}
}