Second Largest Number

PHOTO EMBED

Thu Dec 07 2023 12:36:50 GMT+0000 (Coordinated Universal Time)

Saved by @nistha_jnn #c++

in two traversal-
  
vector<int> getSecondOrderElements(int n, vector<int> a)
{
    int mini=INT_MAX;
    int maxi=INT_MIN;
    for(int i=0  ; i<n ; i++)
    {
        if(a[i]>maxi)
        {
            maxi=a[i];
        }
        if(a[i]<mini)
        {
            mini=a[i];
        }
    }
    vector<int>ans;
    int mi=INT_MAX;
    int ma=INT_MIN;
    for(int i=0 ; i<n ; i++)
    {
        if(a[i]>ma and a[i]!=maxi)
        {
              ma=a[i];
            
        }
        if(a[i]<mi and a[i]!=mini)
        {
            mi=a[i];
        }
    }
    ans.push_back(ma);
    ans.push_back(mi);
    return ans;
}

in single traversal-
  
int findSecondLargest(int n, vector<int> &arr)
{
    int largest=INT_MIN;
    int secondlargest=INT_MIN;
    for(int i=0 ; i<n ; i++)
    {
        if(arr[i]>largest)
        {
            secondlargest=largest;
            largest=arr[i];
        }
        if(arr[i]<largest and arr[i]>secondlargest)
        {
            secondlargest=arr[i];
        }
    }
    if(secondlargest==INT_MIN)
    {
        return -1;
    }
    return secondlargest;
}
content_copyCOPY

Even though we want to have just the second smallest and largest elements, we are still sorting the entire array for that and thus increasing the time complexity. Can we somehow try to not sort the array and still get our answer? Approach: Find the smallest and largest element in the array in a single traversal After this, we once again traverse the array and find an element that is just greater than the smallest element we just found. Similarly, we would find the largest element which is just smaller than the largest element we just found Indeed, this is our second smallest and second largest element.

https://codingninjas.com/studio/problems/ninja-and-the-second-order-elements_6581960?utm_source=youtube&utm_medium=affiliate&utm_campaign=striver_Arrayproblems&leftPanelTabValue=PROBLEM