smallest and largest number

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

Reference

Leave a Reply

avatar
  Subscribe  
Notify of