Find Second Largest in Array

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

• The second largest element is the value that is smaller than the maximum but larger than all other elements in the array.
• If there is no valid second largest (like in case of duplicate values or very small arrays), return -1.

Understanding the Problem

We are given an array of numbers, and we are asked to find the second largest number in that array. But there's a twist: the second largest must be distinct from the largest — meaning we cannot just return the same value again.

Let’s understand this with a simple example:

Example: [10, 20, 30, 25]

Here, the largest number is 30, and the second largest is 25 — because it’s the next highest distinct number after 30.

How We Will Solve It Step-by-Step

1. We will go through the array once, from left to right.
2. We'll keep track of two variables:
   • max_val — stores the largest number found so far.
   • second_max — stores the second largest distinct number found so far.
3. If the current number is greater than max_val, it becomes the new max_val, and the old max_val becomes the new second_max.
4. If the number is less than max_val but still greater than second_max, we update second_max.
5. We skip duplicates — we do not want to count the same number twice.

Incorporating Edge Cases

Let’s walk through common edge cases and how our solution handles them:

Case 1: Array with All Elements the Same

[5, 5, 5] — All elements are equal, so there is no second largest distinct number. We return -1.

Case 2: Array with Only One Element

[42] — Only one number exists, so we return -1 because there’s no second number to compare.

Case 3: Normal Case

[10, 20, 30] — 30 is the largest, 20 is the second largest. Our algorithm will correctly find them in one pass.

Case 4: Duplicates with Distinct Second Largest

[5, 5, 3] — 5 is the largest, 3 is distinct and smaller, so 3 is the second largest.

Case 5: Empty Array

[] — No elements exist, so we return -1.

Why This Approach Works Well

• It runs in O(n) time — only one loop through the array.
• It uses O(1) space — no extra memory needed.
• It handles edge cases clearly — single elements, duplicates, or no valid second largest.
• It avoids sorting — which would take extra time and isn’t needed here.

1. Given an array of numbers arr.
2. If there are less than two unique elements in the array, then return -1.
3. Initialize max_val and second_max to -Infinity.
4. Iterate through each element in the array.
5. If the current element is greater than max_val, update second_max to max_val, and then update max_val.
6. Else if the current element is greater than second_max and not equal to max_val, update second_max.
7. After the loop, return second_max.

Worked example

Let's find the second largest number in the array using a loop.

Initialize max = -Infinity and secondMax = -Infinity.

Check index 0

Current element is 30. Compare with max = -Infinity and secondMax = -Infinity.

30 is greater than current max. Update: secondMax = -Infinity, max = 30.

Check index 1

Current element is 20. Compare with max = 30 and secondMax = -Infinity.

20 is greater than current secondMax and not equal to max. Update: secondMax = 20.

Check index 2

Current element is 10. Compare with max = 30 and secondMax = 20.

No update required.

Check index 3

Current element is 50. Compare with max = 30 and secondMax = 20.

50 is greater than current max. Update: secondMax = 30, max = 50.

Check index 4

Current element is 60. Compare with max = 50 and secondMax = 30.

60 is greater than current max. Update: secondMax = 50, max = 60.

Check index 5

Current element is 40. Compare with max = 60 and secondMax = 50.

No update required.

Final Result:

Second Largest Element = 50

#include <stdio.h>
#include <limits.h>

int isDistinct(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] != arr[j]) return 1;
        }
    }
    return 0;
}

int findSecondLargest(int arr[], int n) {
    if (n < 2 || !isDistinct(arr, n)) return -1;
    int maxVal = INT_MIN, secondMax = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxVal) {
            secondMax = maxVal;
            maxVal = arr[i];
        } else if (arr[i] > secondMax && arr[i] != maxVal) {
            secondMax = arr[i];
        }
    }
    return secondMax;
}

int main() {
    int arr[] = {30, 20, 10, 50, 60, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Second Largest: %d\n", findSecondLargest(arr, n));
    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_set>
#include <limits>
using namespace std;

int findSecondLargest(const vector<int>& arr) {
    unordered_set<int> s(arr.begin(), arr.end());
    if (s.size() < 2) return -1;
    int maxVal = INT_MIN, secondMax = INT_MIN;
    for (int num : arr) {
        if (num > maxVal) {
            secondMax = maxVal;
            maxVal = num;
        } else if (num > secondMax && num != maxVal) {
            secondMax = num;
        }
    }
    return secondMax;
}

int main() {
    vector<int> arr = {30, 20, 10, 50, 60, 40};
    cout << "Second Largest: " << findSecondLargest(arr) << endl;
    return 0;
}

def find_second_largest(arr):
    if len(set(arr)) < 2:
        return -1
    max_val = float('-inf')
    second_max = float('-inf')
    for num in arr:
        if num > max_val:
            second_max = max_val
            max_val = num
        elif num > second_max and num != max_val:
            second_max = num
    return second_max

# Sample Input
arr = [30, 20, 10, 50, 60, 40]
print("Second Largest:", find_second_largest(arr))

public class SecondLargest {
    public static int findSecondLargest(int[] arr) {
        java.util.Set<Integer> set = new java.util.HashSet<>();
        for (int num : arr) set.add(num);
        if (set.size() < 2) return -1;

        int maxVal = Integer.MIN_VALUE;
        int secondMax = Integer.MIN_VALUE;
        for (int num : arr) {
            if (num > maxVal) {
                secondMax = maxVal;
                maxVal = num;
            } else if (num > secondMax && num != maxVal) {
                secondMax = num;
            }
        }
        return secondMax;
    }

    public static void main(String[] args) {
        int[] arr = {30, 20, 10, 50, 60, 40};
        System.out.println("Second Largest: " + findSecondLargest(arr));
    }
}

function findSecondLargest(arr) {
    const unique = [...new Set(arr)];
    if (unique.length < 2) return -1;
    let maxVal = -Infinity;
    let secondMax = -Infinity;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > maxVal) {
            secondMax = maxVal;
            maxVal = arr[i];
        } else if (arr[i] > secondMax && arr[i] !== maxVal) {
            secondMax = arr[i];
        }
    }
    return secondMax;
}

// Sample Input
const arr = [30, 20, 10, 50, 60, 40];
console.log('Second Largest:', findSecondLargest(arr));

package main

import (
    "fmt"
    "math"
)

func findSecondLargest(arr []int) int {
    unique := make(map[int]bool)
    for _, v := range arr {
        unique[v] = true
    }
    if len(unique) < 2 {
        return -1
    }
    maxVal := math.MinInt
    secondMax := math.MinInt
    for _, v := range arr {
        if v > maxVal {
            secondMax = maxVal
            maxVal = v
        } else if v > secondMax && v != maxVal {
            secondMax = v
        }
    }
    return secondMax
}

func main() {
    arr := []int{30, 20, 10, 50, 60, 40}
    fmt.Println("Second Largest:", findSecondLargest(arr))
}

use std::collections::HashSet;

fn find_second_largest(arr: &[i32]) -> i32 {
    let set: HashSet<i32> = arr.iter().cloned().collect();
    if set.len() < 2 {
        return -1;
    }
    let mut max_val = i32::MIN;
    let mut second_max = i32::MIN;
    for &num in arr {
        if num > max_val {
            second_max = max_val;
            max_val = num;
        } else if num > second_max && num != max_val {
            second_max = num;
        }
    }
    second_max
}

fn main() {
    let arr = vec![30, 20, 10, 50, 60, 40];
    println!("Second Largest: {}", find_second_largest(&arr));
}

fun findSecondLargest(arr: IntArray): Int {
    if (arr.toSet().size < 2) return -1
    var maxVal = Int.MIN_VALUE
    var secondMax = Int.MIN_VALUE
    for (num in arr) {
        if (num > maxVal) {
            secondMax = maxVal
            maxVal = num
        } else if (num > secondMax && num != maxVal) {
            secondMax = num
        }
    }
    return secondMax
}

fun main() {
    val arr = intArrayOf(30, 20, 10, 50, 60, 40)
    println("Second Largest: ${findSecondLargest(arr)}")
}

func findSecondLargest(_ arr: [Int]) -> Int {
    let unique = Set(arr)
    if unique.count < 2 { return -1 }
    var maxVal = Int.min
    var secondMax = Int.min
    for num in arr {
        if num > maxVal {
            secondMax = maxVal
            maxVal = num
        } else if num > secondMax && num != maxVal {
            secondMax = num
        }
    }
    return secondMax
}

let arr = [30, 20, 10, 50, 60, 40]
print("Second Largest:", findSecondLargest(arr))

function findSecondLargest(arr: number[]): number {
    const unique = [...new Set(arr)];
    if (unique.length < 2) return -1;
    let maxVal = Number.MIN_SAFE_INTEGER;
    let secondMax = Number.MIN_SAFE_INTEGER;
    for (const num of arr) {
        if (num > maxVal) {
            secondMax = maxVal;
            maxVal = num;
        } else if (num > secondMax && num !== maxVal) {
            secondMax = num;
        }
    }
    return secondMax;
}

const arr: number[] = [30, 20, 10, 50, 60, 40];
console.log("Second Largest:", findSecondLargest(arr));

Time complexity

Space complexity

O(1)

The algorithm uses only a fixed number of variables (max_val and second_max) and does not require any extra space that grows with input size.