Problem

Submissions

Hints & solutions

Discuss

Day 8 : Second largest element in the array

Easy

0/40

Average time to solve is 15m

Contributed by

245 upvotes

Asked in companies

Problem statement

You have been given an array/list 'ARR' of integers. Your task is to find the second largest element present in the 'ARR'.

Note:

a) Duplicate elements may be present.

b) If no such element is present return -1.

Example:

Input: Given a sequence of five numbers 2, 4, 5, 6, 8.

Output:  6

Explanation:
In the given sequence of numbers, number 8 is the largest element, followed by number 6 which is the second-largest element. Hence we return number 6 which is the second-largest element in the sequence.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. 

The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers denoting the elements in the array.

Output Format:

For each test case, print a single line containing a single integer denoting the second largest element in the array.

The output of each test case will be printed in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of, Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 5000
-10 ^ 9 <= 'SIZE' <= 10 ^ 9 

Where ‘T’ is the total number of test cases, ‘N’ denotes the number of elements in the array and ‘SIZE’ denotes the range of the elements in the array.

Time limit: 1 sec.

Sample Input 1:

2
6
12 1 35 10 34 1
5
10 10 10 10 10

Sample Output 1:

34
-1

Explanation of sample input 1:

Test case 1: In the given sequence of numbers, number 35 is the largest element, followed by number 34 which is the second-largest element. Hence we return number 34 which is the second-largest element in the sequence.

Test case 2: In the given sequence of numbers, number 10 is the largest element. However, since all the elements are the same, the second largest element does not exist. So, we return -1.

Sample Input 2:

1
6
7 8 8 1 4 3

Sample Output 2:

Explanation of sample input 2:

In the given sequence of numbers, 8 exists two times and is the largest element, followed by 7 which is the second-largest element. Hence we return the number 7 as the second-largest element.

Hints:

Think about how the sorting of the array can help.

Hint 1

Hint 2

Think about how to use the largest element of the array to find the second-largest element.

Approaches (3)

Approach 1

Approach 2

Approach 3

Simple solution

The idea is to sort the array in decreasing order and return the second largest element in the array.

Sort the array in decreasing order.
We can create a function to sort the elements using a sorting algorithm such as quicksort or use inbuilt sorting functions.
Traverse from index 1(0-based indexing) because the element at index 0 will clearly be the first largest and check whether duplicates of the larger elements exist or not. Finally, return the second element which is not equal to the largest element from the sorted array.
If no such element is found, return -1.

Time Complexity

O(N * log(N)), where ‘N’ is the total number of elements in the array.

The time required to sort is of the order (N * log(N)).

Space Complexity

O(1).

As it uses constant space.

(100% EXP penalty)

Day 8 : Second largest element in the array

Console