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

1. Initialize:
   • largest = -∞
   • secondLargest = -∞
2. Traverse the array
3. For each element:
   • If element > largest
     → update secondLargest = largest
     → update largest = element
   • Else if element < largest AND element > secondLargest
     → update secondLargest = element
4. 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

Language-wise Implementation

C Implementation

#include 
#include 

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 
#include 
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.

Next Problem in the Series

Find the Second Smallest Element in an Array