Second Largest Number

Easy
0/40
Average time to solve is 23m
profile
Contributed by
788 upvotes
Asked in company
Samsung

Problem statement

You have been given an array ‘a’ of ‘n’ unique non-negative integers.


Find the second largest and second smallest element from the array.


Return the two elements (second largest and second smallest) as another array of size 2.


Example : 
Input: ‘n’ = 5, ‘a’ = [1, 2, 3, 4, 5]
Output: [4, 2]

The second largest element after 5 is 4, and the second smallest element after 1 is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line will contain the integer ‘n’, the number of elements in the array ‘a’, and the next line will contain the ‘n’ spaced integers in the array elements.
Output Format: 
Print two elements, the second largest and the second smallest element, from the array.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function.
Sample Input 1 :
4
3 4 5 2
Sample Output 1 :
4 3
Explanation For Sample Input 1 :
The second largest element after 5 is 4 only, and the second smallest element after 2 is 3.
Sample Input 2 :
5
4 5 3 6 7
Sample Output 2 :
6 4
Expected Time Complexity:
O(n), Where ‘n’ is the size of an input array ‘a’.
Constraints:
2 ≤ 'n' ≤ 10^5
0 ≤ 'a'[i] ≤ 10^9

Time limit: 1 sec


Hints:
1. Sort the array.
2. More efficiently, can you use the largest and smallest elements to find the required elements?
Approaches (2)
Naive Approach

Approach: 
 

In this approach, we will sort the given array, and the answer will be the second and second last element as the second smallest and second largest elements respectively.
 

Algorithm: 
 

  • Sort the given array ‘a’
  • Return {a[n - 2], a[1]}
Time Complexity

O(n * Log(n)), where ‘n’ is the size of the array ‘a’.
 

As we are sorting the array, it will take the O(n * Log(n)) time.
 

Hence, the time complexity is O(n * Log(n)).

Space Complexity

O(1).

 

As we are using constant extra space.

 

Hence, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Second Largest Number
Full screen
Console