Second largest

We are asked to find the second largest number from the given vector/array.

There are 3 approaches:

1. sort the array then find the second largest by iterating from last index.

    class Solution {
      public:
        int getSecondLargest(vector<int> &arr) {
            if(arr.size() < 2 )
            return -1;  //we exit early if the array has less than 2 elements
           sort(arr.begin(), arr.end());
           int n = arr.size();
           for(int i = n - 2; i >= 0; i--)
           {
               if(arr[i] < arr[n-1])
               return arr[i];
   
           }
           return -1;
        }
    };
   

   time complexity: for soritng, 0(n log(n)) and for traversing 0(n) in worst case(total : 0(n*log(n) + n ) n can be negligible. So, 0(n * log(n)).

   space complexity : 0(1)

2. Two-pass approach:

   we take two iterations: one for finding the largest and other for finding the number less than largest.

    class Solution {
      public:
        int getSecondLargest(vector<int> &arr) {
            if(arr.size() < 2 )
            return -1;
            int largest = -1, secondLargest = -1;
            // 1st pass to find the largest element
           for(int i = 0; i < arr.size(); i++)
           {
               if(arr[i] > largest)
               largest = arr[i];
           }
           // 2nd pass
           for(int i = 0; i < arr.size(); i++)
           {
               if(arr[i] < largest ){
               secondLargest = max( secondLargest, arr[i]);
               }
           }
   
            return secondLargest;
        }
    };
   

   3. one-pass approach(optimal):

      Here we take two variables : largest and secondLargest.

      working: we iterate and compare each element with largest , if the element is greater than largest then we update secondLargest with largest and largest with the element.

      Else we compare the element with secondLargest, if the element is greater than secondLargest then update secondLargest with the element.

       class Solution {
         public:
           int getSecondLargest(vector<int> &arr) {
               if(arr.size() < 2 )
               return -1;
               int largest = -1, secondLargest = -1;
              for(int i = 0; i < arr.size(); i++){
                  if(arr[i] > largest){
                  secondLargest = largest;
                  largest = arr[i];
                  }
                  else if(arr[i] < largest && arr[i] > secondLargest )
                  secondLargest = arr[i];
              }
              return secondLargest;
           }
       };