Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Second Largest Element

Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Print the second largest distinct value in the array, or -1 if it does not exist.

Input

First line: n. Second line: n space-separated integers.

Output

The second largest distinct value, or -1.

Constraints

Try to do it in a single pass.

Example 1

Input

6
12 35 1 10 34 1

Output

34

Example 2

Input

3
10 10 10

Output

-1

Hints

  1. Track two values while scanning: the largest and the second largest.
  2. Only update "second" with values strictly smaller than "largest", so duplicates of the maximum don't count.

Approach

Scan once keeping first and second (both start at -1, since values are ≥ 0). For each x: if x > first, the old first becomes second and x becomes first; else if first > x > second, x becomes second. If second is still -1 at the end, no second distinct value exists.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long first = -1, second = -1, x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (x > first) {
            second = first;
            first = x;
        } else if (x < first && x > second) {
            second = x;
        }
    }
    cout << second << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
first = second = -1
for x in a[:n]:
    if x > first:
        first, second = x, first
    elif first > x > second:
        second = x
print(second)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long first = -1, second = -1;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            if (x > first) {
                second = first;
                first = x;
            } else if (x < first && x > second) {
                second = x;
            }
        }
        System.out.println(second);
    }
}

Solve Second Largest Element online · All practice problems