Second Largest Element

Solved

Difficulty: Easy Accuracy: — Submissions: 0 Points: 2

Given an array arr[] of positive integers, return the second largest distinct value in it. If there is no such value (every element is the same, or the array has one element), return -1.

Examples:

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

Output: 34

Explanation: The largest is 35 and the next distinct value below it is 34.

Input: arr[] = [10, 5, 10]

Output: 5

Explanation: 10 appears twice; the second largest distinct value is 5.

Input: arr[] = [10, 10]

Output: -1

Explanation: There is only one distinct value.

Constraints:

1 ≤ arr.size() ≤ 10^5
1 ≤ arr[i] ≤ 10^9

Expected Complexities

Time Complexity: O(n) Auxiliary Space: O(1)

Company Tags

Amazon Samsung

Topic Tags

Arrays Easy

Sorting works but costs O(n log n). A single pass is enough: keep the largest and the second largest seen so far. When a new value beats the largest, the old largest becomes the second largest; when it sits strictly between the two, it replaces the second largest. Equal values are skipped, which is what makes the answer distinct.

class Solution {
public:
    int secondLargest(vector<int>& arr) {
        int first = -1, second = -1;
        for (int x : arr) {
            if (x > first) {
                second = first;
                first = x;
            } else if (x < first && x > second) {
                second = x;
            }
        }
        return second;
    }
};