# 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

## Leave a Reply