Second Largest element in Array

print the second largest distinct element from an array.

Example 1:

Input: 
N = 6
Arr[] = {14, 48, 9, 17, 35, 1}
Output: 35
Explanation: second largest element
is 35.

Example 2:

Input: 
N = 4
Arr[] = {10, 5, 10, 9}
Output: 9
Explanation: The largest element of 
the array is 10 and the second 
largest element is 9.

If the second-largest element does not exist in the array, return -1.

method 1:

First, find the largest element in the array by iterating over all the elements of the array and comparing them with the variable largest. If an element is greater than the largest, it becomes the new value of the largest. After finding the largest element, then search for the second largest element in the array by iterating over all the elements of the array again and comparing them with a variable secondLargest. If an element is greater than secondLargest but less than the largest, it becomes the new value of secondLargest. Finally, the function returns the value of secondLargest.

Java implementation:

class Solution {
    int print2largest(int arr[], int n) {
        int largest=0;
        for(int i=0;i<n;i++) {
            if(arr[i]>largest) {
                largest=arr[i];
            }
        }
        int secondLargest=-1;
       for(int i=0;i<n;i++) {
            if(arr[i]>secondLargest && arr[i]<largest) {
                secondLargest=arr[i];
            }
        }
        
        return secondLargest;
    }
}

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

c++ implementation:

    int print2largest(int arr[], int n) {
        int largest = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] > largest) {
                largest = arr[i];
            }
        }
        int secondLargest = -1;
        for(int i = 0; i < n; i++) {
            if(arr[i] > secondLargest && arr[i] < largest) {
                secondLargest = arr[i];
            }
        }
        return secondLargest;
    }

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

python implementation:

    def print2largest(self, arr, n):
        largest = max(arr)
        second_largest = -1
        for i in range(n):
            if arr[i] > second_largest and arr[i] < largest:
                second_largest = arr[i]
        return second_largest

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

method 2: Use Set 

1)Create a set of integers and add each element of the input array to the set using a for-each loop.

2)If the size of the set is less than 2, return -1 because there is no second largest element.

3)Get the largest element in the set and remove the largest element from the set.

4)Return the new last element in the set, which is the second largest element in the input array.

Overall, the code sorts the input array and finds the second largest element in O(n log n) time complexity due to the underlying sorting algorithm.

java implementation:

class Solution {
    int print2largest(int arr[], int n) {

    SortedSet<Integer> ss = new TreeSet<Integer>();
    for (int num : arr) {
            ss.add(num);
     }
        
    if(ss.size()<2){
        return -1;
    }
        
    int largest = ss.last();
    ss.remove(largest);
    
    return  ss.last();
    }
}

 Time Complexity: O(n log n).  
Auxiliary Space: O(1).

c++ implementation:

int print2largest(int arr[], int n) {
    set<int> s;
    for (int i = 0; i < n; i++) {
        s.insert(arr[i]);
    }
    if (s.size() < 2) {
        return -1;
    }
    s.erase(s.find(*s.rbegin()));
    return *s.rbegin();
}

 Time Complexity: O(n log n).  
Auxiliary Space: O(1).

python implementation:

def print2largest(arr):
    ss = set(arr)
    if len(ss) < 2:
        return -1
    largest = max(ss)
    ss.remove(largest)
    return max(ss)

 Time Complexity: O(n log n).  
Auxiliary Space: O(1).