Second Largest Element

Intuition

To find the second largest element in an array, one simple way is to use sorting. By sorting the array in ascending order, the largest element will be surely at the last index, and the second largest element will be at the second-to-last index.

What if there are fewer than 2 elements in an array ?

There would not be any second largest element for this case, so returned value will be -1.

What if last and second last element turn out as same ?

If the second-to-last element is equal to the last element, continue checking the preceding elements until a different value is found. This approach guarantees that correct identification of the second largest element is made.

Approach

Initialize 2 variables largest, and secondLargest. Initialize secondLargest to -1 as initially there shall be no second largest element.

Sort the array and update largest with last element of array.

Now iterate the array from second to last index and if the element is not equal to the largest , update secondLargest to that element and break out once secondLargest is updated. Return the value stored in secondLargest

Solution

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

class Solution {
public:

    // Function to find the second largest element
    int secondLargestElement(vector<int>& nums) {
        int n = nums.size();
        
        // Check if the array has less than 2 elements
        if (n < 2) {
            // Indicating no second largest element is possible
            return -1; 
        }
        
        // Sort the vector in ascending order
        sort(nums.begin(), nums.end());

        // Largest element will be at last index
        int largest = nums.back();

        int secondLargest = -1;

        // Traverse the sorted vector from right to left
        for (int i = n-2; i >= 0; i--) {

            /* If the current element is not
            equal to the largest element*/
            if (nums[i] != largest) {

                /* Assign the current element 
                as the second largest and break*/
                secondLargest = nums[i];
                break;

            }
        }

        // Return the second largest element
        return secondLargest ;
    }
};

int main() {
    vector nums = {1, 2, 4, 6, 7, 5};

    //Create an instance of the Solution class
    Solution sol;

    /* Function call to find 
    the second largest element*/
    int ans = sol.secondLargestElement(nums);

    cout << "The second largest element is: " << ans << endl;
    return 0;
}
import java.util.*;

class Solution {
    
    // Function to find the second largest element
    public int secondLargestElement(int[] nums) {
        int n = nums.length;
        
        // Check if the array has less than 2 elements
        if (n < 2) {
            // Indicating no second largest element is possible
            return -1; 
        }
        
        // Sort the array in ascending order
        Arrays.sort(nums);

        // Largest element will be at last index
        int largest = nums[n - 1];

        int secondLargest = -1;

        // Traverse the sorted array from right to left
        for (int i = n - 2; i >= 0; i--) {

            /* If the current element is not
            equal to the largest element*/
            if (nums[i] != largest) {

                /* Assign the current element 
                as the second largest and break*/
                secondLargest = nums[i];
                break;
            }
        }

        // Return the second largest element
        return secondLargest;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 6, 7, 5};

        // Create an instance of the Solution class
        Solution sol = new Solution();

        /* Call the method to find 
        the second largest element */
        int ans = sol.secondLargestElement(nums);

        System.out.println("The second largest element is: " + ans);
    }
}
class Solution:
    
    # Function to find the second largest element
    def secondLargestElement(self, nums):
        n = len(nums)
        
        # Check if the array has less than 2 elements
        if n < 2:
            # Indicating no second largest element is possible
            return -1
        
        # Sort the list in ascending order
        nums.sort()

        # Largest element will be at last index
        largest = nums[-1]

        secondLargest = -1

        # Traverse the sorted list from right to left
        for i in range(n-2, -1, -1):

            ''' If the current element is not
            equal to the largest element'''
            if nums[i] != largest:

                ''' Assign the current element 
                as the second largest and break'''
                secondLargest = nums[i]
                break

        # Return the second largest element
        return secondLargest


# Example usage
nums = [1, 2, 4, 6, 7, 5]

# Create an instance of the Solution class
sol = Solution()

''' Call the method to find 
the second largest element'''
ans = sol.secondLargestElement(nums)

print("The second largest element is:", ans)
class Solution {
    
    // Function to find the second largest element
    secondLargestElement(nums) {
        let n = nums.length;
        
        // Check if the array has less than 2 elements
        if (n < 2) {
            // Indicating no second largest element is possible
            return -1;
        }
        
        // Sort the array in ascending order
        nums.sort((a, b) => a - b);

        // Largest element will be at last index
        let largest = nums[n - 1];

        let secondLargest = -1;

        // Traverse the sorted array from right to left
        for (let i = n - 2; i >= 0; i--) {

            /* If the current element is not
            equal to the largest element */
            if (nums[i] != largest) {

                /* Assign the current element 
                as the second largest and break */
                secondLargest = nums[i];
                break;
            }
        }

        // Return the second largest element
        return secondLargest;
    }
}

// Example usage
let nums = [1, 2, 4, 6, 7, 5];

// Create an instance of the Solution class
let sol = new Solution();

/* Call the method to find 
the second largest element */
let ans = sol.secondLargestElement(nums);

console.log("Second largest element is:", ans);

Complexity Analysis

Time Complexity: O(N * log N) for sorting the array, where N is the length of the array. Space Complexity: O(1) as no additional space is used.

Intuition

To optimise the solution further the idea is to eliminate sorting. Traverse the array once to find the largest element. Perform a second traversal to find the largest element that is smaller than the largest element found.

What if there are fewer than 2 elements?

When there are fewer than 2 elements in an array, there would not be any second largest element, so return -1.

Approach

Initialize two variables largest, and secondLargest to INT_MIN.

Iterate the array and find the largest element.

In the second iteration check if the element is greater than secondLargestand also not equal to largest then update the secondLargest. Return secondLargest

Solution

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

class Solution {
public:
    // Method for the second largest element in the vector
    int secondLargestElement(vector<int>& nums) {
        int n = nums.size();

        // Check if the vector has less than 2 elements
        if (n < 2) {

            /* If true, return -1 indicating there 
            is no second largest element*/
            return -1; 

        }
        /* Initialize variables to store the 
        largest and second largest elements*/
        int largest = INT_MIN, secondLargest = INT_MIN;

        // First traversal to find the largest element
        for (int i = 0; i < n; i++) {
            largest = max(largest, nums[i]);
        }

        // Second traversal to find second largest element
        for (int i = 0; i < n; i++) {
            if (nums[i] > secondLargest && nums[i] != largest) {
                secondLargest = nums[i];
            }

        }
        // Return the second largest element
        return secondLargest == INT_MIN ? -1 : secondLargest;
    }
};

int main() {
    vector nums = {1, 2, 4, 6, 7, 5};

    //Create an instance of Solution class
    Solution sol;

    // Call the method to find second largest element
    int result = sol.getSecondLargest(nums, n);

    cout << "Second largest is " << result << endl;
    return 0;
}
import java.util.*;

class Solution {
    public int secondLargestElement(int[] nums) {
        int n = nums.length;

        // Check if the array has less than 2 elements
        if (n < 2) {
            // If true, return -1 
             // Exit the method
            return -1;
        }

        /*Initialize variables to store the
       largest and second largest elements*/
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;

        // First traversal to find the largest element
        for (int i = 0; i < n; i++) {
            largest = Math.max(largest, nums[i]);
        }

        // Second traversal to find second largest element
        for (int i = 0; i < n; i++) {
            if (nums[i] > secondLargest  && nums[i] != largest) {
                secondLargest = nums[i];
            }
        }

        // Return the second largest element
        return secondLargest == Integer.MIN_VALUE ? -1 : secondLargest; 
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 6, 7, 5};

        //Create Instance of Solution Class
        Solution sol = new Solution();

        /* Call the method to find the second
        largest element and store the result*/
        int result = sol.getSecondLargest(nums);

        System.out.println("Second largest is " + result);
    }
}

class Solution:

    def secondLargestElement(self, nums):
        # Get the length of the array
        n = len(nums)

        # Check if the array has less than 2 elements
        if n < 2:
            # If true, return -1 indicating there is no second largest element
            return -1 

        # Initialize variables to store the largest and second largest elements
        largest = float('-inf')
        secondLargest = float('-inf')

        # First traversal to find the largest element
        for i in range(n):
            largest = max(largest, nums[i])

        # Second traversal to find second largest element
        for i in range(n):
            if nums[i] > secondLargest and nums[i] != largest:
                secondLargest = nums[i]

        # Return the second largest element
        return -1 if secondLargest == float('-inf') else secondLargest


nums = [1, 2, 4, 6, 7, 5]

# Create an instance of the Solution class
sol = Solution()

"""Call the method to find the second 
largest element and store the result"""
result = sol.getSecondLargest(nums)

print("Second largest is", result)
class Solution {

    secondLargestElement(nums) {
        // Get the length of the array
        let n = nums.length;

        // Check if the array has less than 2 elements
        if (n < 2) {
            /*If true, return -1 indicating there
            is no second largest element*/
            return -1; 
        }

        /*Initialize variables to store the 
        largest and second largest elements*/
        let largest = Number.MIN_VALUE;
        let secondLargest = Number.MIN_VALUE;
        
        // First traversal to find the largest element
        for (let i = 0; i < n; i++) {
            largest = Math.max(largest, nums[i]);
        }
        
        // Second traversal to find second largest element
        for (let i = 0; i < n; i++) {
            if (nums[i] > secondLargest && nums[i] != largest) {
                secondLargest = nums[i];
            }
        }

        // Return the second largest element
        return secondLargest ==  Number.MIN_VALUE ? -1 : secondLargest;
    }
}

let nums = [1, 2, 4, 6, 7, 5];

// Create an instance of the Solution class
let sol = new Solution();

/*Call the method to find the second
 largest element and store the result*/
let result = sol.getSecondLargest(nums);

console.log("Second largest is " + result);

Complexity Analysis

Time Complexity: O(N) + O(N) = O(2N), due to two linear traversals, where N is the length of the array. Space Complexity: O(1), as no additional space is required.

Intuition

To find the second-largest element in an array more efficiently, the idea is to perform the operation in a single traversal by making smart comparisons. This approach uses two variables to keep track of the largest and the second-largest elements while iterating through the array. This will help to find the second-largest element with just one pass throughout the array.

What if there are fewer than 2 elements?

When there are fewer than 2 elements in an array, there would not be any second largest element, so return -1.

Approach

Initialize two variables: largest, and secondLargest. Initialize largest and secondLargest to INT_MIN as initially none of them should be holding any values.

If the current element is larger than largest, update secondLargest and largest.

Else if the current element is larger than secondLargest and not equal to largest, update secondLargest.

Traverse the entire array to update the second largest element in declared variable i.e, secondLargest.

Dry Run

Solution

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

class Solution {
public:
    // Method for second largest element in the vector
    int secondLargestElement(vector<int>& nums) {
        // Check if the vector has less than 2 elements
        if (nums.size() < 2) {

            /* If true, return -1 indicating there
            is no second largest element*/
            return -1;

        }

        /*Initialize variables to store the
        largest and second largest elements*/
        int large = INT_MIN;
        int second_large = INT_MIN;

        /* Single traversal to find the
        largest and second largest elements*/
        for (int i = 0; i < nums.size(); i++) {

            if (nums[i] > large) {
                second_large = large;
                large = nums[i];
            } 
            else if (nums[i] > second_large && nums[i] != large) {
                second_large = nums[i];
            }

        }

        // Return the second largest element
        return second_large == INT_MIN ?  -1 : second_large;
    }
};

int main() {
    vector nums = {1, 2, 4, 7, 7, 5};

    //Create an instance of the Solution class
    Solution sol;

    /Call the method to find
    the second largest element*/
    int sL = sol.secondLargestElement(nums);

    cout << "Second largest is " << sL << endl;
    return 0;
}
import java.io.*;

class Solution {
    // Method for second largest element in the array
    public int secondLargestElement(int[] nums) {

        // Check if the array has less than 2 elements
        if (nums.length < 2) {
            // If true, return -1 there is no second largest element
            return -1;
        }

        /* Initialize variables to store the 
        largest and second largest elements */
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;

        /*Single traversal to find thelargest 
       and second largest elements*/
        for (int i = 0; i < nums.length; i++) {

            if (nums[i] > largest) {
                secondLargest = largest;
                largest = nums[i];
            } 
            else if (nums[i] > secondLargest && nums[i] != largest) {
                secondLargest = nums[i];
            }

        }

        // Return the second largest element
        return secondLargest == Integer.MIN_VALUE ?  -1 : secondLargest;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 7, 7, 5};

       //Creating the instance of the Solution class
        Solution sol=new Solution();

        int n = nums.length;

        /* Call the method to find
        the second largest element*/
        int sL = sol.secondLargestElement(nums);

        System.out.println("Second largest is " + sL);
    }
}
from typing import List

class Solution:
    def secondLargestElement(self, nums: List[int]) -> int:

        if len(nums) < 2:
            return -1

        largest =  float('-inf')
        second_largest =  float('-inf')

        for num in nums:

            if num > largest:
                second_largest = largest
                largest = num

            elif num > second_largest and num != largest:
                second_largest = num

        return -1 if second_largest == float('-inf') else second_largest

# Main function
if __name__ == "__main__":
    nums = [1, 2, 4, 6, 7, 5]

   #Creating an instance of the Solution class
    sol = Solution()

    result = sol.secondLargestElement(nums)
    print("Second largest is:", result)
class Solution {

    secondLargestElement(nums) {
        // Get the length of the array
        let n = nums.length;

        // Check if the array has less than 2 elements
        if (n < 2) {
            /*If true, return -1 indicating there
            is no second largest element*/
            return -1;
        }

        /* Initialize variables to store the 
        largest and second largest elements*/
        let largest = Number.MIN_VALUE;
        let secondLargest = Number.MIN_VALUE;

        /*Single traversal to find the largest 
        and second largest elements*/
        for (let i = 0; i < n; i++) {

            if (nums[i] > largest) {
                secondLargest = largest;
                largest = nums[i];
            }
            else if (nums[i] > secondLargest && nums[i] != largest) {
                secondLargest = nums[i];
            }

        }
        // Return the second largest element
        return secondLargest == Number.MIN_VALUE ? -1 : secondLargest;
    }
}

let nums = [1, 2, 4, 7, 7, 5];

// Create an instance of the Solution class
let sol = new Solution();

// Call the method to find second largest element
let sL = sol.secondLargestElement(nums);

console.log("Second largest is " + sL);

Complexity Analysis

Time Complexity: O(N), because the solution involves a single traversal, where N is the length of the array, Space Complexity: O(1) as no additional space is required.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

What if there are fewer than 2 elements in an array ?

What if last and second last element turn out as same ?

Approach

Solution

Complexity Analysis

Intuition

What if there are fewer than 2 elements?

Approach

Solution

Complexity Analysis

Intuition

What if there are fewer than 2 elements?

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code