Given an input array of unsorted integers. Write a code to find second smallest number in an array.
For example :
arr = {-1, 7, 1, 34, 18}
The second smallest number in this array is 1.
In this tutorial, I am going to explain multiple approaches to solve this problem. Also, we will write it’s java code.
Let’s discuss how we can find second lowest number in an array by sorting and without sorting an array.
METHOD 1: Find second smallest number by sorting an array
The easiest approach is to sort the array. After sorting an array, the element present at 1st index is the second smallest number in an array.
Insertion Sort Program in Java
For sorting either we can write our own sort method using Sorting algorithms or we can use java inbuilt sort method.
The time complexity of sorting an array is O(nlogn).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//Find second smallest number in an array with sorting import java.util.Arrays; public class SecondSmallest { public static void main(String[] args) { //unsorted array int num[] = {1, 9, 5, 2, 8, -1, 3, 55}; //Length of an array int n = num.length; //Sort the array Arrays.sort(num); /** * After sorting * Second smallest number is at 1 position */ System.out.println("Second smallest Number: "+num[1]); } } |
NOTE: If the element of an array is repeated then this approach won’t work.
To understand this let’s take an example.
int num[] = {1, 9, 5, 1, 8, -1, 3, -1};
So what will be the second smallest number if we can use above method (sort and pick the element at 1st index). The element is -1 which is wrong.
How we can improve our previous approach?
The best approach is to traverse an array once to find second smallest number. Let’s implement this approach.
Find Second Smallest Number of an Array
Find Second Smallest Number in an Array without Sorting – Java Code
Let’s discuss how we can solve this problem in a single traversal using two variables (smallest and secondSmallest).
Here are the following steps –
i) Declare two variables smallest and secondSmallest. Initialize them with Integer.MAX_VALUE.
ii) Traverse an array and do the following checks –
a) If current element is smaller than the smallest. Then, update the value of smallest variable.
b) If current element is greater than smallest and less than secondSmallest than update the value of secondSmallest.
The time complexity of this approach is O(n).
Java Program to Find Second Largest Number in an Array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//Find second lowest number in an array public class SecondSmallest { public static int getSecondSmallest(int arr[]) { //Integer.MAX_VALUE is 2147483647 int smallest = Integer.MAX_VALUE; int secondSmallest = Integer.MAX_VALUE; //Traverse an array for(int i = 0; i < arr.length; i++) { if(arr[i] < smallest) { secondSmallest = smallest; smallest = arr[i]; } if(arr[i] > smallest && arr[i] < secondSmallest ) { secondSmallest = arr[i]; } } return secondSmallest; } public static void main(String[] args) { int arr[] = {-1, 70, 10, 34, 18, 78}; //Method Call int result = getSecondSmallest(arr); System.out.println(" Second smallest number " + result); } } |
In this video tutorial, I have explained multiple approaches to solve this problem.
