Find the second biggest element in an unsorted array – Single Traversal

Given an input array of integers, your goal is to find the second biggest element 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 result by traversing through the array only once.

Algorithm:

Below is the efficient algorithm for doing this

1. Declare/provide input array
2. Initialize two variables firstBig and secondBig with Integer.MIN_VALUE
3. Input array validation: Check if atleast two elements present in array.
4. For loop: Start Traversing the array - single traversal
   4.1 Check if the current element is greater than the firstBig, if yes then set secondBig to firstBig (secondBig = firstBig) and set firstBig to current element (firstBig = current element)
   4.2 Check if current element is NOT greater than firstBig, then check if that is greater than secondBig and NOT EQUAL to firstBig, if yes then set secondBig to current element (secondBig = current element)
5. Print the value stored in the secondBig variable, which is the second biggest element in the array.

Solution to find second biggest:

package com.sneppets.dsalgo.examples;

/**
 * Java Program to find the second biggest element in an unsorted array of integers in single traversal
 * @author sneppets.com
 */
public class SecondBiggestInArray {	
	
	public static void main (String[] args)
	{
		int inArray[] = {2, 4, 7, 6, 5, 1, 3, 10};
		int arraySize = inArray.length;
		findSecondBiggest(inArray, arraySize);
	}

	private static void findSecondBiggest(int[] inArray, int arraySize) {
		
		//Initialize two variables with Integer.MIN_VALUE
		int firstBig = Integer.MIN_VALUE; 
		int secondBig = Integer.MIN_VALUE;
		
		//Check if atleast two elements present in array.
		if(arraySize < 2)
		{
			System.out.println(" There should be atleast 
					     two elements in arrays. Invalid input !!");
			return;
		}
		
		//Traversing the array
		for (int i=0; i< arraySize; i++)
		{
			//if the current element is greater than the firstBig 
			if(inArray[i] > firstBig)
			{
				//set secondBig to firstBig
				secondBig = firstBig;
				//set firstBig to current element.
				firstBig = inArray[i];
			}
			//if current element is NOT greater than firstBig, 
			//then check if that is greater than secondBig and NOT EQUAL to firstBig
			else if (inArray[i] > secondBig && inArray[i] !=firstBig)
			{
				//set secondBig to current element
				secondBig = inArray[i];
			}
		}
		
		System.out.println("Second biggest element 
			            in the input array is: " + secondBig);
	}

}

Output

Second biggest element in the input array is: 7

Time Complexity – Single Traversal – O(n)

Space complexity – O(1)

Recommended Posts

• Running time in Big O notation for Java Arrays Algorithms
• 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

Reference

• Arrays API Documentation