BL
U

31. Second Largest Distinct Element

Easy

Problem Description

Find the second-largest distinct element in an array of NN integers without sorting. If fewer than two distinct elements exist, output -1.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.

Output Format

Print the second-largest distinct integer, or -1.

Example 1:
Input:
6
12 35 1 10 34 1
Output:
34
Explanation: Largest is 35, second-largest distinct is 34.
Example 2:
Input:
3
10 10 10
Output:
-1
Explanation: Only one distinct value exists; output -1.
Example 3:
Input:
2
-5 -2
Output:
-5
Explanation: Largest is -2, second-largest is -5.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online