Find Second Largest in Array using Loop - Optimal Solution

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpaceDetailed Ex

Visualization Player

Problem Statement❯

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.

Examples❯

Input Array Second Largest Description
[10, 20, 30, 40, 50] 40 50 is the largest, 40 is the next highestVisualization
[5, 1, 5, 3] 3 5 is the largest, 3 is the next distinct largestVisualization
[8, 8, 8] -1 All elements are the same, no second largestVisualization
[100] -1 Only one element, so no second largestVisualization
[20, 20, 10] 10 20 is the largest, 10 is the next distinctVisualization
[1, 2] 1 2 is the largest, 1 is the second largestVisualization
[7, 7, 7, 3] 3 7 is the largest, 3 is the next distinct valueVisualization
[] -1 Empty array, so no elements to compareVisualization
[9, 9] -1 Only one unique element presentVisualization

Solution❯

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.

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)The algorithm always traverses the entire array once to ensure it captures both the largest and second largest elements.
Average CaseO(n)Regardless of the input distribution, the algorithm iterates through all elements to maintain max and second max values.
Worst CaseO(n)Even in the worst case where the second largest is the last element, the algorithm still requires a full pass through the array.

Space Complexity❯

O(1)

Explanation: 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.

Detailed Step by Step Example❯

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

{ "array": [30,20,10,50,60,40], "showIndices": true }

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.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [0], "labels": {"0":"i"} }
{ "array": [0,30,null], "showIndices": false, "highlightIndicesGreen": [1, 2], "emptyCompIndices": [0], "labels": { "1": "max", "2": "secondMax" } }

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.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [1], "labels": {"1":"i"} }
{ "array": [0,30,20], "showIndices": false, "highlightIndicesGreen": [1, 2], "emptyCompIndices": [0], "labels": { "1": "max", "2": "secondMax" } }

Check index 2

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

No update required.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [2], "labels": {"2":"i"} }
{ "array": [0,30,20], "showIndices": false, "highlightIndicesGreen": [1, 2], "emptyCompIndices": [0], "labels": { "1": "max", "2": "secondMax" } }

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.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [3], "labels": {"3":"i"} }
{ "array": [0,50,30], "showIndices": false, "highlightIndicesGreen": [1, 2], "emptyCompIndices": [0], "labels": { "1": "max", "2": "secondMax" } }

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.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [4], "labels": {"4":"i"} }
{ "array": [0,60,50], "showIndices": false, "highlightIndicesGreen": [1, 2], "emptyCompIndices": [0], "labels": { "1": "max", "2": "secondMax" } }

Check index 5

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

No update required.

{ "array": [30,20,10,50,60,40], "showIndices": true, "highlightIndices": [5], "labels": {"5":"i"} }
{ "array": [0,60,50], "showIndices": false, "highlightIndicesGreen": [1, 2], "emptyCompIndices": [0], "labels": { "1": "max", "2": "secondMax" } }

Final Result:

Second Largest Element = 50

{ "array": [30,20,10,50,60,40], "showIndices": true, "labels": { "4": "max", "3": "secondMax" } }
{ "array": [0,60,50], "showIndices": false, "highlightIndicesGreen": [1, 2], "emptyCompIndices": [0], "labels": { "1": "max", "2": "secondMax" } }

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...