In this article, we will explore three different methods to find the second smallest number in an array using Java. These methods include:
- Using Array Sorting
- Using Single Pass Through
- Using Min Heap
1. Using Array Sorting
One of the simplest ways to find the second smallest integer in an array is by sorting the array and then selecting the second element. Here is how you can do it:
1.1 Code Example and output
package com.jcg.example;
import java.util.Arrays;
public class SecondSmallest {
public static void main(String[] args) {
int[] array = {
5,
1,
4,
2,
8
};
Arrays.sort(array);
int secondSmallest = array[1];
System.out.println("The second smallest element is: " + secondSmallest);
}
}
The above code sorts the array using Arrays.sort() method, and then accesses the second element of the sorted array which is the second smallest integer. The code gives the following output on the IDE console:
The second smallest element is: 2
2. Using Single Pass Through
This method involves a single pass through the array to find the smallest and second smallest elements without sorting the array.
2.1 Code Example and output
package com.jcg.example;
public class SecondSmallest {
public static void main(String[] args) {
int[] array = {
5,
1,
4,
2,
8
};
if (array.length < 2) {
System.out.println("Array is too small to find the second smallest element.");
return;
}
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int num: array) {
if (num < first) {
second = first;
first = num;
} else if (num < second && num != first) {
second = num;
}
}
if (second == Integer.MAX_VALUE) {
System.out.println("No second smallest element found.");
} else {
System.out.println("The second smallest element is: " + second);
}
}
}
The code initializes two variables first and second to store the smallest and second smallest elements respectively. It then iterates through the array to update these variables based on the current element. The code gives the following output on the IDE console:
The second smallest element is: 2
3. Using Min Heap
A Min Heap can be used to efficiently find the second smallest element by extracting the two smallest elements from the heap.
3.1 Code Example and output
package com.jcg.example;
import java.util.PriorityQueue;
public class SecondSmallest {
public static void main(String[] args) {
int[] array = {
5,
1,
4,
2,
8
};
PriorityQueue minHeap = new PriorityQueue ();
for (int num: array) {
minHeap.offer(num);
}
if (minHeap.size() < 2) {
System.out.println("Array is too small to find the second smallest element.");
return;
}
minHeap.poll(); // remove the smallest element
int secondSmallest = minHeap.poll(); // get the second smallest element
System.out.println("The second smallest element is: " + secondSmallest);
}
}
The code uses a PriorityQueue (which is a Min Heap) to store the elements of the array. The smallest element is removed using poll(), and the next call to poll() retrieves the second smallest element. The code gives the following output on the IDE console:
The second smallest element is: 2
4. Conclusion
We have explored three different methods to find the second smallest integer in an array in Java. Each method has its advantages and use cases:
- Array Sorting: Simple and straightforward but not the most efficient with O(n log n) time complexity.
- Single Pass Through: Efficient with O(n) time complexity, suitable for most scenarios.
- Min Heap: Efficient with O(n log k) time complexity and useful for finding other small elements as well.
Depending on the specific requirements of your application, you can choose the method that best suits your needs.
