.png)
Find the Second Largest Element in an Array
Problem Statement
Given an array of integers, the task is to find the second largest element in the array.
Important Conditions
- The array must contain at least two distinct elements
- Duplicate values should be handled correctly
- The second largest element is the largest value smaller than the maximum
Understanding the Problem
Consider the array:
[10, 5, 20, 8]
- Largest element = 20
- Second largest element = 10
Now consider:
[4, 4, 4, 4]
- There is no second largest element because all elements are equal
Why This Problem Is Important
This problem helps in understanding:
- Comparison logic
- Tracking multiple values during traversal
- Handling edge cases
- Efficient single-pass solutions
It is frequently asked in:
- Coding interviews
- Competitive programming
- Real-world ranking and analytics problems
Input and Output Format
Input
Array: [12, 35, 1, 10, 34, 1]
Output
Second Largest Element: 34
Approach 1: Single Traversal (Optimal)
Instead of sorting the array, we track:
- largest
- secondLargest
Step-by-Step Algorithm
- Initialize:
- largest = -∞
- secondLargest = -∞
- Traverse the array
- For each element:
- If element > largest
→ update secondLargest = largest
→ update largest = element - Else if element < largest AND element > secondLargest
→ update secondLargest = element
- If element > largest
- After traversal:
- If secondLargest is still -∞, second largest does not exist
- Else print secondLargest
Pseudocode
largest = -∞
secondLargest = -∞
for each element in array:
if element > largest:
secondLargest = largest
largest = element
else if element < largest AND element > secondLargest:
secondLargest = element
if secondLargest == -∞:
print "No second largest element"
else:
print secondLargest
Dry Run Example
Array = [12, 35, 1, 10, 34]
Initial:
largest = -∞
secondLargest = -∞
12 → largest = 12
35 → secondLargest = 12, largest = 35
1 → ignored
10 → secondLargest = 12 (unchanged)
34 → secondLargest = 34
Result = 34
Time and Space Complexity
| Metric | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(1) |
Language-wise Implementation
C Implementation
#include<stdio.h>
#include<limits.h>
int main() {
int arr[] = {12, 35, 1, 10, 34};
int n = sizeof(arr) / sizeof(arr[0]);
int largest = INT_MIN;
int secondLargest = INT_MIN;
for(int i = 0; i < n; i++) {
if(arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
}
else if(arr[i] < largest && arr[i] > secondLargest) {
secondLargest = arr[i];
}
}
if(secondLargest == INT_MIN)
printf("No second largest element");
else
printf("Second largest element: %d", secondLargest);
return 0;
}
Output
Second largest element: 34
C++ Implementation
#include<iostream>
#include<climits>
using namespace std;
int main() {
int arr[] = {12, 35, 1, 10, 34};
int n = sizeof(arr) / sizeof(arr[0]);
int largest = INT_MIN;
int secondLargest = INT_MIN;
for(int i = 0; i < n; i++) {
if(arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
}
else if(arr[i] < largest && arr[i] > secondLargest) {
secondLargest = arr[i];
}
}
if(secondLargest == INT_MIN)
cout << "No second largest element";
else
cout << "Second largest element: " << secondLargest;
return 0;
}
Output
Second largest element: 34
Java Implementation
public class Main {
public static void main(String[] args) {
int[] arr = {12, 35, 1, 10, 34};
int largest = Integer.MIN_VALUE;
int secondLargest = Integer.MIN_VALUE;
for(int num : arr) {
if(num > largest) {
secondLargest = largest;
largest = num;
}
else if(num < largest && num > secondLargest) {
secondLargest = num;
}
}
if(secondLargest == Integer.MIN_VALUE)
System.out.println("No second largest element");
else
System.out.println("Second largest element: " + secondLargest);
}
}
Output
Second largest element: 34
Python Implementation
arr = [12, 35, 1, 10, 34]
largest = float('-inf')
second_largest = float('-inf')
for num in arr:
if num > largest:
second_largest = largest
largest = num
elif num < largest and num > second_largest:
second_largest = num
if second_largest == float('-inf'):
print("No second largest element")
else:
print("Second largest element:", second_largest)
Output
Second largest element: 34
C# Implementation
using System;
class Program {
static void Main() {
int[] arr = {12, 35, 1, 10, 34};
int largest = int.MinValue;
int secondLargest = int.MinValue;
foreach(int num in arr) {
if(num > largest) {
secondLargest = largest;
largest = num;
}
else if(num < largest && num > secondLargest) {
secondLargest = num;
}
}
if(secondLargest == int.MinValue)
Console.WriteLine("No second largest element");
else
Console.WriteLine("Second largest element: " + secondLargest);
}
}
Output
Second largest element: 34
JavaScript Implementation
let arr = [12, 35, 1, 10, 34];
let largest = -Infinity;
let secondLargest = -Infinity;
for (let num of arr) {
if (num > largest) {
secondLargest = largest;
largest = num;
} else if (num < largest && num > secondLargest) {
secondLargest = num;
}
}
if (secondLargest === -Infinity)
console.log("No second largest element");
else
console.log("Second largest element:", secondLargest);
Output
Second largest element: 34
Common Mistakes to Avoid
- Sorting the array unnecessarily
- Not handling duplicate values
- Ignoring edge cases with identical elements
- Using extra space when not needed
Interview Variations
- Find third largest element
- Find second smallest element
- Find k-th largest element
- Find largest and second largest together
Detailed Summary
Finding the second largest element in an array is a classic comparison-based problem that demonstrates efficient traversal and value tracking. By maintaining two variables—largest and second largest—we can determine the result in a single pass without sorting or using extra memory. This approach ensures optimal time and space complexity while also handling duplicates and edge cases effectively. Mastery of this problem builds a strong foundation for more advanced ranking, selection, and optimization algorithms.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
