🚀 Find the Second Largest Element in an Array

Avnii Thakur
3d
2.8k
0
1

Article

Introduction

Finding the second largest element in an array is a very common DSA interview question. It helps beginners understand how to work with arrays, loops, and conditions efficiently.

In this article, we’ll break it down with:
✅ Problem understanding
✅ Examples
✅ Different approaches
✅ Code in C++, Java, and Python

🔍 Problem Statement

Given an array of integers, your task is to find the second largest element in it.

👉 If the array has less than two distinct elements, return something like "Not Found".

🧮 Example

Input

arr = [12, 35, 1, 10, 34, 1]

Output

Second largest element = 34

Explanation

Largest = 35
Second largest = 34

💡 Approaches

1️⃣ Naive Approach (Sorting)

Sort the array in descending order.
Pick the second element.
Time Complexity: O(n log n)
Not optimal if only the second largest is required.

2️⃣ Efficient Approach (Single Traversal) ✅

Keep track of two variables:
- first = largest
- second = second largest
Traverse the array once and update accordingly.
Time Complexity: O(n)

👩‍💻 Code Implementation

🔹 C++ Code

#include <iostream>
#include <climits>
using namespace std;

int secondLargest(int arr[], int n) {
    int first = INT_MIN, second = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > first) {
            second = first;
            first = arr[i];
        } else if (arr[i] > second && arr[i] != first) {
            second = arr[i];
        }
    }
    return (second == INT_MIN) ? -1 : second;
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int result = secondLargest(arr, n);
    if (result == -1)
        cout << "Second largest element not found";
    else
        cout << "Second largest element = " << result;
    return 0;
}

🔹 Java Code

class SecondLargest {
    static int findSecondLargest(int arr[], int n) {
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (arr[i] > first) {
                second = first;
                first = arr[i];
            } else if (arr[i] > second && arr[i] != first) {
                second = arr[i];
            }
        }
        return (second == Integer.MIN_VALUE) ? -1 : second;
    }

    public static void main(String args[]) {
        int arr[] = {12, 35, 1, 10, 34, 1};
        int n = arr.length;
        int result = findSecondLargest(arr, n);
        if (result == -1)
            System.out.println("Second largest element not found");
        else
            System.out.println("Second largest element = " + result);
    }
}

🔹 Python Code

def second_largest(arr):
    first, second = float('-inf'), float('-inf')
    for num in arr:
        if num > first:
            second, first = first, num
        elif num > second and num != first:
            second = num
    return None if second == float('-inf') else second

arr = [12, 35, 1, 10, 34, 1]
result = second_largest(arr)
if result is None:
    print("Second largest element not found")
else:
    print("Second largest element =", result)

🧾 Key Takeaways

Sorting works, but takes O(n log n) time.
A single traversal solution works in O(n) and is more efficient.
Always handle cases where the array has fewer than 2 unique elements.