Second Largest Element

Greetings, dear readers! Today, we delve into an interesting problem in the realm of algorithms and data structures. We’re going to tackle the task of finding the second-largest distinct element in an array. This problem requires a keen understanding of array manipulation and comparative analysis. Let’s dive in!

Understanding the Problem:

Given an array Arr of size N, our task is to find and print the second largest distinct element from the array. If the second largest element doesn’t exist, we should return -1.

Let’s walk through a couple of examples to gain a clearer understanding:

Example1 : 
Input: 
N = 7
Arr[] = {11, 30, 17, 8, 40, 21}
Output: 30

In this example, the second largest distinct element in the array is 30.

Example2:
N = 4
Arr[] = {1, 15, 17, 15}
Output: 15

Here, the second largest distinct element in the array is 15.

Approach Overview:

Before delving into the solutions, let’s outline our approach to tackle this problem effectively:

Sorting Array (Solution 1):

• Sort the array in ascending order.
• Traverse the sorted array to find the second largest distinct element.
• Return the second largest element if found; otherwise, return -1.

Linear Search (Solution 2):

• Find the maximum and minimum elements of the array.
• Iterate through the array to find the element that is greater than the minimum but less than the maximum.
• Return this element as the second largest if found; otherwise, return -1.
• By understanding these approaches, we can now delve into the detailed solutions. 

Let’s explore both solutions step by step.

Solution 1: Sorting Array

This solution involves sorting the array and then traversing it to find the second largest distinct element.

Step-by-Step Explanation:

Sort Array: 

• Sort the array in ascending order using any efficient sorting algorithm.

Traverse Array: 

• Start traversing the sorted array from the second last element.
• Compare each element with the largest element to identify the second largest distinct element.
• If found, return this element; otherwise, return -1.

Code:

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

class Solution{
public: 
    // Function returns the second
    // largest elements
    int print2largest_sort(int arr[], int n) {
        if(n==1)
            return -1;  

        // sorting the array in ascending order
        sort(arr,arr+n);
        for(int i = n-2; i>=0;i--){
            // it will check if the element is same as the largest element or not
            if(arr[i]!=arr[n-1]){ 
                return arr[i];  
            }
        }
        // if the array has all same element then there will be no second largest element
        return -1;
    }
};

int main() {
    int arr1[] = {11, 30, 17, 8, 40, 21};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    Solution sol;

    cout << "Solution 1: " << sol.print2largest_sort(arr1, n1) << endl;

    int arr2[] = {1, 15, 17, 15};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    cout << "Solution 1: " << sol.print2largest_sort(arr2, n2) << endl;

    return 0;
}

Code Explanation:

• The function first checks if there’s only one element in the array, in which case there can’t be a second largest, and returns -1.
• It sorts the array in ascending order.
• It iterates from the second last element towards the first, checking for an element that is different from the largest element.
• Once found, it returns that element as the second largest.
• If all elements are the same, it returns -1.

Time Complexity:

Sorting the array takes O(N log N) time, where N is the size of the array. The subsequent iteration over the array takes O(N) time. Thus, the overall time complexity of this solution is O(N log N).

Solution 2: Linear Search

This solution involves a linear search approach without sorting the array explicitly.

Step-by-Step Explanation:

Find Maximum and Minimum:

• Find the maximum and minimum elements of the array using built-in functions or iterating through the array.

Search for Second Largest:

• Iterate through the array and update the minimum element if a value greater than the current minimum but less than the maximum is found.
• Return the updated minimum element as the second largest if it exists; otherwise, return -1.

Code: 

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

class Solution{
public: 

    // Function returns the second
    // largest elements
    int print2largest_linear(int arr[], int n) {
        // code here
         int maxi = *max_element(arr,arr+n);
        int mini = *min_element(arr,arr+n);
        
        for(int i = 0; i < n; i++){
            if(arr[i] > mini && arr[i] < maxi){
                mini = arr[i];
            }
        }
        
        if(maxi == mini) return -1;
        return mini;
    }
};

int main() {
    int arr1[] = {11, 30, 17, 8, 40, 21};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    Solution sol;

    cout << "Solution 2: " << sol.print2largest_linear(arr1, n1) << endl;

    int arr2[] = {1, 15, 17, 15};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    cout << "Solution 2: " << sol.print2largest_linear(arr2, n2) << endl;

    return 0;
}

Code Explanation:

• The function first finds the maximum and minimum elements of the array.
• It then iterates over the array, updating the minimum element if it finds a value greater than the current minimum but less than the maximum.
• Finally, it checks if the maximum and minimum are the same. If they are, it implies all elements are the same, and returns -1; otherwise, it returns the second largest.

Time Complexity:

Finding the maximum and minimum elements takes O(N) time. The subsequent iteration over the array also takes O(N) time. Thus, the overall time complexity of this solution is O(N).

Conclusion:

With this analysis, we can conclude that while Solution 1 has a slightly higher time complexity due to sorting, Solution 2 offers a more efficient linear time complexity. However, the choice between these solutions might depend on various factors such as the size of the input array and the overhead of sorting.