Array ( [0] => [1] => questions [2] => Arrays [3] => Second-Largest-and-Second-Smallest ) Arrays | Second Largest and Second Smallest | THE INQUISITIVE






Second Largest and Second Smallest

LEVEL:Beginner

Description

Given list of elements. You have to find the second largest and second smallest numbers in a given array.

Input Format

First line contains a number N. Next line contains N integers separated by spaces.

Output Format

Print the second largest and second smallest value.


Example 1:

Input
5
3 5 2 4 1
Output
4 2
Example 2:

Input
8
7 4 2 6 1 7 9 8
Output
8 2
Example 3:

Input
10
32 4 87 9 25 12 45 2 3 1
Output
32 2

oops

Login to see Discussion




Approach

Approach 1: sorting

Step-i) sort the given array
Step-ii) initialize small with first element of array and large with last element of the array
Step-iii)from 0 keep traversing the array till you find element greater than small and then break the loop
Step-iv) similarly from back traversing the array till you find the element smaller than large and then break
Step-v) return both the values

Time Complexity: O(nlogn)
Space Complexity: O(1)

Approach 2: Liner Approach

Step-i) In first traversal find the largest and smallest value in the array
Step-ii)now initialize sec_large to minimum possible value and sec_small to the max_possible value
Step-iii) once again traverse the array and if current element is smaller than largest and greater than sec_large
assign current element to sec_large
Step-iv) similarly if current element is greater than the smallest and smaller than sec_small
assign current value to sec_small
Step-v) return these values

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

Approach 3: Using heaps

Step-i) convert the array to min heap and max heap
Step-ii) remove the first element from both the heaps so that largest and smallest gets removed
Step-iii) now again remove the elements from both the heaps if these are equal to the previously removed number repeat step iii
Step-iv) else return the respective values

Time Complexity: O(n)
Space Complexity: (2*n) as n space is required for one heap and here there are two heaps


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Arrays

Beginner

1. Arithmetic Progression2. Geometric Progression3. Harmonic Progression4. No of triangles 5. Area of Polygon6. Trailing Zeros7. Min Platforms 8. Trapping Rain 9. Jump numbers10. Segregation of 0’s and 1’s11. Two SUM12. Triplet sum 13. Diagonal Sum14. Addition of two matrixes15. Subtraction of two matrixes16. Multiplication of two matrixes17. Transpose of given array18. Spiral Matrix19. Most Frequent Element20. Majority Element 21. Max difference 22. Odd occurring23. Second Largest and Second Smallest24. Next greater number25. Count Unique Elements26. Common elements 27. Removing Duplicates28. Balanced Array29. Rotating Array by k times30. Reverse Array31. Wave Array32. Merge arrays 33. Constraint Sort34. Find element in Sorted rotated array35. Sub Array Sum36. Largest subarray of 0’s and 1’s 37. K-Sub Array38. Max subarray sum39. Contiguous Square Sum