Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Second Maximum Without Sorting

EASYProblemSolveExternal Links

Description

Given an array of positive integers, find the second largest distinct element in the array. If no such element exists (for example, when all elements are the same), return -1.

The second largest element is defined as the largest value in the array that is strictly less than the maximum. Duplicate copies of the maximum do not count — we need a genuinely different, smaller value.

Examples

Example 1

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

Output: 34

Explanation: The largest element in the array is 35. Among the remaining distinct values — 12, 1, 10, and 34 — the largest is 34. Therefore, the second largest element is 34.

Example 2

Input: arr = [10, 5, 10]

Output: 5

Explanation: The largest element is 10. Even though 10 appears twice, we do not count a duplicate as the second largest. The only other distinct value is 5, so the second largest element is 5.

Example 3

Input: arr = [10, 10, 10]

Output: -1

Explanation: Every element in the array is 10. There is no value strictly less than 10 in the array, so the second largest element does not exist. We return -1.

Constraints

  • 2 ≤ arr.length ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^5

Editorial

Brute Force

Intuition

The most straightforward idea is to sort the array first. Once sorted in ascending order, the largest element sits at the very end. To find the second largest, we walk backward from the second-to-last position and look for the first element that is strictly less than the largest.

Think of it like lining up students by height from shortest to tallest. The tallest student is at the end. To find the second tallest, you walk backwards from the end and skip anyone who is exactly the same height as the tallest — the first shorter person you find is your answer. If everyone is the same height, there is no second tallest.

Step-by-Step Explanation

Let's trace through with arr = [12, 35, 1, 10, 34, 1]:

Step 1: Start with the unsorted array: [12, 35, 1, 10, 34, 1].

Step 2: Sort the array in ascending order: [1, 1, 10, 12, 34, 35].

Step 3: The largest element is arr[5] = 35 (last element).

Step 4: Check arr[4] = 34. Is 34 equal to 35? No. We found a distinct element that is smaller than the largest.

Step 5: Return 34 as the second largest element.

Note: If we had an array like [10, 10, 10] → sorted: [10, 10, 10], we would check index 2 (10 == 10, skip), index 1 (10 == 10, skip), index 0 (10 == 10, skip). No distinct smaller value found, so return -1.

Algorithm

  1. Sort the array in non-decreasing order.
  2. Identify the largest element as arr[n-1].
  3. Traverse the array backward from index n-2:
    • If the current element is strictly less than the largest, return it.
  4. If no such element is found, return -1.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int getSecondLargest(vector<int>& arr) {
        int n = arr.size();
        sort(arr.begin(), arr.end());

        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] != arr[n - 1]) {
                return arr[i];
            }
        }
        return -1;
    }
};
class Solution:
    def getSecondLargest(self, arr: list[int]) -> int:
        arr.sort()
        n = len(arr)
        largest = arr[n - 1]

        for i in range(n - 2, -1, -1):
            if arr[i] != largest:
                return arr[i]
        return -1
import java.util.Arrays;

class Solution {
    public int getSecondLargest(int[] arr) {
        int n = arr.length;
        Arrays.sort(arr);

        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] != arr[n - 1]) {
                return arr[i];
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(N log N)

Sorting the array takes O(N log N) time. The subsequent backward traversal takes at most O(N) in the worst case (when all elements are equal). The sorting step dominates, so the total time is O(N log N).

Space Complexity: O(1) to O(N)

Depends on the sorting algorithm. In-place sorts like quicksort use O(log N) stack space, while merge sort uses O(N) extra space.

Why This Approach Is Not Efficient

Sorting the entire array to answer a single question — "what is the second largest value?" — is overkill. Sorting performs O(N log N) comparisons and rearranges every element into a specific order. But we do not need the full sorted order. We only need to know two values: the largest and the second largest.

With N up to 100,000, the sorting approach performs roughly 100,000 × 17 ≈ 1,700,000 operations. While this is within time limits, it also modifies the original array, which may not be desirable.

The key insight is: we can find the largest value in O(N) with a single pass. Then, with one more pass, we can find the second largest by scanning for the largest value that is not equal to the first. This reduces the problem to two simple linear scans — no sorting needed.

Better Approach - Two Pass Linear Scan

Intuition

Instead of sorting, we can solve this in two separate passes through the array. In the first pass, we find the overall maximum element — exactly like solving "Find Maximum in Array." In the second pass, we scan the array again, this time looking for the largest element that is strictly less than the maximum we found.

Imagine a teacher collecting test scores. First, she reads through all scores to find the highest score in the class. Then she reads through them again, ignoring anyone who got the top score, and finds the next best score. Two read-throughs of the same list — simple and efficient.

Step-by-Step Explanation

Let's trace through with arr = [12, 35, 1, 10, 34, 1]:

Pass 1 — Find the largest:

Step 1: Initialize largest = -1.

Step 2: Check arr[0] = 12. Is 12 > -1? Yes. Update largest = 12.

Step 3: Check arr[1] = 35. Is 35 > 12? Yes. Update largest = 35.

Step 4: Check arr[2] = 1. Is 1 > 35? No. largest stays 35.

Step 5: Check arr[3] = 10. Is 10 > 35? No. largest stays 35.

Step 6: Check arr[4] = 34. Is 34 > 35? No. largest stays 35.

Step 7: Check arr[5] = 1. Is 1 > 35? No. largest stays 35.

After Pass 1: largest = 35.

Pass 2 — Find the second largest (ignoring elements equal to 35):

Step 8: Initialize secondLargest = -1.

Step 9: Check arr[0] = 12. Is 12 ≠ 35 and 12 > -1? Yes. Update secondLargest = 12.

Step 10: Check arr[1] = 35. Is 35 ≠ 35? No (skip — this is the maximum itself).

Step 11: Check arr[2] = 1. Is 1 ≠ 35 and 1 > 12? No (1 < 12). secondLargest stays 12.

Step 12: Check arr[3] = 10. Is 10 ≠ 35 and 10 > 12? No (10 < 12). secondLargest stays 12.

Step 13: Check arr[4] = 34. Is 34 ≠ 35 and 34 > 12? Yes. Update secondLargest = 34.

Step 14: Check arr[5] = 1. Is 1 ≠ 35 and 1 > 34? No (1 < 34). secondLargest stays 34.

After Pass 2: secondLargest = 34. Return 34.

Two-Pass Search — Finding Second Largest — Watch two separate scans: first we find the maximum (35), then we rescan to find the largest value below the maximum (34).

Algorithm

  1. Pass 1 — Find the largest element:
    • Initialize largest = -1.
    • For each element in the array, if it is greater than largest, update largest.
  2. Pass 2 — Find the second largest element:
    • Initialize secondLargest = -1.
    • For each element in the array:
      • If the element is not equal to largest AND is greater than secondLargest, update secondLargest.
  3. Return secondLargest.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int getSecondLargest(vector<int>& arr) {
        int n = arr.size();
        int largest = -1;

        // Pass 1: Find the largest
        for (int i = 0; i < n; i++) {
            if (arr[i] > largest) {
                largest = arr[i];
            }
        }

        // Pass 2: Find the second largest
        int secondLargest = -1;
        for (int i = 0; i < n; i++) {
            if (arr[i] != largest && arr[i] > secondLargest) {
                secondLargest = arr[i];
            }
        }

        return secondLargest;
    }
};
class Solution:
    def getSecondLargest(self, arr: list[int]) -> int:
        # Pass 1: Find the largest
        largest = -1
        for num in arr:
            if num > largest:
                largest = num

        # Pass 2: Find the second largest
        second_largest = -1
        for num in arr:
            if num != largest and num > second_largest:
                second_largest = num

        return second_largest
class Solution {
    public int getSecondLargest(int[] arr) {
        int n = arr.length;

        // Pass 1: Find the largest
        int largest = -1;
        for (int i = 0; i < n; i++) {
            if (arr[i] > largest) {
                largest = arr[i];
            }
        }

        // Pass 2: Find the second largest
        int secondLargest = -1;
        for (int i = 0; i < n; i++) {
            if (arr[i] != largest && arr[i] > secondLargest) {
                secondLargest = arr[i];
            }
        }

        return secondLargest;
    }
}

Complexity Analysis

Time Complexity: O(N)

We traverse the array twice. The first pass makes N comparisons to find the largest element. The second pass makes N comparisons to find the second largest. Total: 2N comparisons, which simplifies to O(N).

Space Complexity: O(1)

We use only two extra variables (largest and secondLargest). No additional data structures are needed, so space is constant.

Why This Approach Is Not Efficient

The two-pass approach correctly runs in O(N) time and is a significant improvement over sorting. However, it requires two complete traversals of the array — one to find the maximum and another to find the second maximum.

While the time complexity is already optimal at O(N), we are doing roughly 2N comparisons. We can ask: is it possible to find both the largest and second largest in a single pass through the array?

The answer is yes. By cleverly maintaining two variables simultaneously — one for the largest and one for the second largest — and updating them with the right logic at each step, we can achieve the same result in just one traversal with roughly N comparisons. This is both simpler and faster in practice.

Optimal Approach - Single Pass Tracking

Intuition

The key insight is that whenever we find a new largest element, the previous largest element becomes the new second largest. This simple observation allows us to track both values in a single traversal.

Imagine you are watching a race. You keep track of the leader and the runner-up. When a new racer overtakes the leader, the old leader drops to second place — you do not need to re-scan all the racers. And if a racer passes the runner-up but not the leader, you just update the runner-up. One continuous observation of the race gives you both positions.

Formally, for each element we encounter:

  • If it is greater than the current largest: the old largest becomes the new secondLargest, and this element becomes the new largest.
  • Else if it is strictly between secondLargest and largest (i.e., less than largest but greater than secondLargest): update secondLargest to this element.
  • Otherwise: this element is not useful — skip it.

Step-by-Step Explanation

Let's trace through with arr = [12, 35, 1, 10, 34, 1]:

Step 1: Initialize largest = -1, secondLargest = -1.

Step 2: Process arr[0] = 12.

  • Is 12 > largest (-1)? Yes.
  • secondLargest = largest = -1. (old largest becomes second)
  • largest = 12.
  • State: largest = 12, secondLargest = -1.

Step 3: Process arr[1] = 35.

  • Is 35 > largest (12)? Yes.
  • secondLargest = largest = 12. (12 drops to second place)
  • largest = 35.
  • State: largest = 35, secondLargest = 12.

Step 4: Process arr[2] = 1.

  • Is 1 > largest (35)? No.
  • Is 1 < largest (35) AND 1 > secondLargest (12)? No (1 < 12).
  • No update.
  • State: largest = 35, secondLargest = 12.

Step 5: Process arr[3] = 10.

  • Is 10 > largest (35)? No.
  • Is 10 < 35 AND 10 > secondLargest (12)? No (10 < 12).
  • No update.
  • State: largest = 35, secondLargest = 12.

Step 6: Process arr[4] = 34.

  • Is 34 > largest (35)? No.
  • Is 34 < 35 AND 34 > secondLargest (12)? Yes!
  • secondLargest = 34.
  • State: largest = 35, secondLargest = 34.

Step 7: Process arr[5] = 1.

  • Is 1 > largest (35)? No.
  • Is 1 < 35 AND 1 > secondLargest (34)? No (1 < 34).
  • No update.
  • State: largest = 35, secondLargest = 34.

Step 8: Return secondLargest = 34.

Single-Pass — Tracking Largest and Second Largest Simultaneously — Watch how we maintain two running trackers in one sweep. When a new maximum is found, the old maximum cascades down to become the second largest.

Algorithm

  1. Initialize two variables: largest = -1 and secondLargest = -1.
  2. For each element in the array:
    • If the element > largest:
      • Set secondLargest = largest (the old leader drops to second place).
      • Set largest = element (the new leader).
    • Else if the element < largest AND element > secondLargest:
      • Set secondLargest = element (it fits between the two trackers).
  3. Return secondLargest.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int getSecondLargest(vector<int>& arr) {
        int largest = -1;
        int secondLargest = -1;

        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] > largest) {
                secondLargest = largest;
                largest = arr[i];
            } else if (arr[i] < largest && arr[i] > secondLargest) {
                secondLargest = arr[i];
            }
        }

        return secondLargest;
    }
};
class Solution:
    def getSecondLargest(self, arr: list[int]) -> int:
        largest = -1
        second_largest = -1

        for num in arr:
            if num > largest:
                second_largest = largest
                largest = num
            elif num < largest and num > second_largest:
                second_largest = num

        return second_largest
class Solution {
    public int getSecondLargest(int[] arr) {
        int largest = -1;
        int secondLargest = -1;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > largest) {
                secondLargest = largest;
                largest = arr[i];
            } else if (arr[i] < largest && arr[i] > secondLargest) {
                secondLargest = arr[i];
            }
        }

        return secondLargest;
    }
}

Complexity Analysis

Time Complexity: O(N)

We traverse the array exactly once, making at most two comparisons per element (one against largest, and possibly one against secondLargest). The total number of comparisons is at most 2N, which simplifies to O(N). Compared to the two-pass approach, we save one complete traversal.

Space Complexity: O(1)

We use only two extra variables (largest and secondLargest). No sorting, no extra data structures — just constant space. The original array is not modified.