Find Smallest and Largest Number in Unsorted Array – O(n) Time
Given an input array of integers, your goal is to find both smallest and largest number present in the array in an effective way. Note, you need to achieve this in O(n) time i.e., you should be able to find the results by traversing through the array only once.
Algorithm:
Below is the efficient algorithm for doing this. While traversing through the array keep track of maximum and minimum numbers found so far and when you reach the end of the array, then you will get smallest and largest numbers present in the array.
1) Declare/provide input array 2) Initialize max and min numbers to some random numbers in array, let's say inArray[0] 3) Traverse through the array 3.1) Check if the current element is greater than the max, if yes then set max to current element. 3.2) Check if the current element is lesser than the min,if yes then set min to current element. 4) print the smallest and largest numbers in the input array.
Solution to find smallest and largest number
package com.sneppets.dsalgo.examples;
/**
* Java program find largest and smallest number in unsorted array
* @author sneppets.com
*
*/
public class SmallestLargestInArray {
public static void main(String[] args)
{
int inArray[] = {2, 4, 7, 6, 5, 1, 3, 10};
int arraySize = inArray.length;
findSmallestlargestElement(inArray, arraySize);
}
private static void findSmallestlargestElement(int[] inArray, int arraySize) {
//initialize max and min numbers to some random numbers in array, let's say inArray[0]
int min = inArray[0];
int max = inArray[0];
//Traverse through the array
for (int i=0; i< arraySize; i++)
{
//if the current element is greater than the max, then set max to current element
if (inArray[i] > max)
{
max = inArray[i];
}
//if the current element is lesser than the min, then set min to current element
if (inArray[i] < min)
{
min = inArray[i];
}
}
//print smallest and largest numbers in the input array
System.out.println("The smallest number in the input array is: " + min);
System.out.println("The largest number in the input array is: " + max);
}
}
Output
The smallest number in the input array is: 1 The largest number in the input array is: 10
Time Complexity – Single Traversal – O(n)
Space complexity – O(1)
Recommended Posts
- Running time in Big O notation for Java Arrays Algorithms
- Find Second Largest Element in an unsorted array – O(n)
- Program to reverse a string or word
- Efficient sorting mechanism for Unsorted Array – List Insertion Sort
- Find all possible combinations of numbers to print given sum