Problem

Given an array of integers, our task is to write a program that efficiently finds the second largest element present in the array.

Similar problem - Find smallest and second smallest elements in an array

Examples

Example 1:

1
2

Input : arr[] = {12, 35, 1, 10, 34, 1}
Output : 34

Example 2:

1
2

Input : arr[] = {10, 5, 10}
Output : 5

Example 3:

1
2

Input : arr[] = {10, 10, 10}
Output : -1
Similar Problems

Solution

Method 1 - Sorting

A simple solution will be first sort the array in descending order and then return the second element from the sorted array. The time complexity of this solution is O(nlogn).

Method 2 - Two pass

A Better Solution is to traverse the array twice. In the first traversal find the maximum element. In the second traversal find the greatest element less than the element obtained in first traversal. The time complexity of this solution is O(n).

Method 3 - One pass solution

A more Efficient Solution can be to find the second largest element in a single traversal.

Algorithm

  • Takes an integer array arr as input.
  • Checks if the array size is less than 2. If so, it returns -1.
  • Initializes largest and secondLargest with the minimum possible integer value (Integer.MIN_VALUE).
  • Iterates through the array using a single loop.
  • Within the loop, compares the current element arr[i] with both largest and secondLargest.
    • If arr[i] is greater than largest, it becomes the new largest and the previous largest becomes the secondLargest.
    • If arr[i] is greater than the current secondLargest but not equal to the current largest, it becomes the new secondLargest.
Edge case

We should return -1 if secondLargest remains Integer.MIN_VALUE after the loop (indicating all elements are equal).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static int findSecondLargest(int[] arr) {
	int n = arr.length;
	// if we have less than 2 elements
	if (n < 2) {
		return -1;
	}

	int largest = Integer.MIN_VALUE;
	int secondLargest = Integer.MIN_VALUE;

	for (int i = 0; i < n; i++) {
		// Update largest and secondLargest if necessary
		if (arr[i] > largest) {
			secondLargest = largest;
			largest = arr[i];
		} else if (arr[i] > secondLargest && arr[i] != largest) {
			secondLargest = arr[i];
		}
	}

	// Return -1 if all elements are equal
	return secondLargest == Integer.MIN_VALUE ? -1 : secondLargest;
}

Complexity

  • Time complexity: O(n)
  • Auxiliary Space : O(1)