Finding the second largest element in an array can be approached in multiple ways. Here, we'll discuss three methods: using sorting, a better approach with two linear traversals and an optimal single-pass approach.

Solution 1: Sorting

One straightforward method to find the second largest element in an array is by sorting the array in ascending order and then traversing the sorted array from the end to find the second largest unique element.

Implementation:

// Solution-1: Sorting
// Time Complexity: O(n log n)
// Space Complexity: O(1)
int secondLargestElement(vector<int> &arr)
{
    sort(arr.begin(), arr.end());

    int large = arr[arr.size() - 1];
    int secondLarge = large;

    for (int i = arr.size() - 2; i >= 0; i--)
    {
        if (arr[i] != large)
        {
            secondLarge = arr[i];
            break;
        }
    }
    return secondLarge;
}

Logic:

1. Sort the array: Use the sort function to sort the array in ascending order.

2. Find the second largest element: Traverse the sorted array from the end to find the first element that is not equal to the largest element.

Time Complexity: O(n log n)

• Explanation: The time complexity is dominated by the sorting algorithm.

Space Complexity: O(1)

• Explanation: Sorting is done in place, so no additional space is used.

Example:

• Input: arr = [10, 20, 5, 3, 100]

• Output: 20

• Explanation: The sorted array is [3, 5, 10, 20, 100]. The second largest element is 20.

Solution 2: Better Approach

A more efficient method is to use two linear traversals of the array. First, find the largest element and then find the second largest element excluding the largest one.

Implementation:

// Solution-2: Better Approach
// Time Complexity: O(n), We do two linear traversals in our array
// Space Complexity: O(1)
int secondLargestElement(vector<int> &arr, int n)
{
    // Find the largest element in the array
    int large = arr[0];
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > large)
        {
            large = arr[i];
        }
    }

    // Find the second largest element excluding the largest one
    int secondLarge = INT_MIN;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > secondLarge && arr[i] != large)
        {
            secondLarge = arr[i];
        }
    }
    return secondLarge;
}

Logic:

1. Find the largest element: Traverse the array to find the largest element.

2. Find the second largest element: Traverse the array again to find the largest element excluding the previously found largest element.

Time Complexity: O(n)

• Explanation: Two separate linear traversals of the array.

Space Complexity: O(1)

• Explanation: Only a constant amount of extra space is used.

Example:

• Input: arr = [10, 20, 5, 3, 100]

• Output: 20

• Explanation: The largest element is 100. The second largest element found during the second traversal is 20.

Solution 3: Optimal Approach

The most efficient method is a single-pass solution where we keep track of both the largest and second largest elements during one traversal of the array.

Implementation:

// Solution-3: Optimal Approach
// Time Complexity: O(n), Single-pass solution
// Space Complexity: O(1)
int secondLargestElement(vector<int> &arr, int n)
{
    int large = INT_MIN;
    int secondLarge = INT_MIN;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] > large)
        {
            secondLarge = large;
            large = arr[i];
        }
        else if (arr[i] > secondLarge && arr[i] != large)
        {
            secondLarge = arr[i];
        }
    }
    return secondLarge;
}

Logic:

1. Initialize large and secondLarge: Set them to the smallest possible integer values INT_MIN.

2. Single-pass traversal: During one traversal of the array, update large and secondLarge accordingly.

3. Update logic: If the current element is greater than large, update secondLarge to be large and then update large. Otherwise, if the current element is greater than secondLarge and not equal to large, update secondLarge.

Time Complexity: O(n)

• Explanation: Single linear traversal of the array.

Space Complexity: O(1)

• Explanation: Only a constant amount of extra space is used.

Example:

• Input: arr = [10, 20, 5, 3, 100]

• Output: 20

• Explanation: The traversal updates large to 100 and secondLarge to 20.

Comparison

• Sorting Method:

  • Pros: Simple and easy to implement.
  • Cons: Less efficient due to the O(n log n) time complexity.
  • Use Case: Suitable when sorting the array is required for other purposes.

• Better Approach:

  • Pros: More efficient with O(n) time complexity using two passes.
  • Cons: Requires two traversals of the array.
  • Use Case: Useful when you want a more efficient solution than sorting but don’t mind two passes.

• Optimal Approach:

  • Pros: Most efficient with O(n) time complexity using a single pass.
  • Cons: Slightly more complex logic.
  • Use Case: Ideal for finding the second largest element in large datasets efficiently.

Edge Cases

• Empty Array: If the array is empty, the function should handle it by returning an appropriate value or throwing an exception.

• Single Element Array: If the array contains only one element, there is no second largest element, so the function should handle this case appropriately.

• All Elements Same: If all elements in the array are the same, there is no distinct second largest element, so the function should handle this case appropriately.

Additional Notes

• Stability: Since we are only finding the second largest element, stability (preserving the order of equal elements) is not relevant.

• Efficiency: The optimal approach is the most efficient for large datasets due to its single-pass solution.

• Use Cases: The optimal method is generally preferred for its O(n) time complexity and O(1) space complexity, making it suitable for large datasets.

Conclusion

Finding the second largest element in an array can be done efficiently using various methods. The sorting approach is simple but less efficient, while the better and optimal approaches provide more efficient solutions with linear time complexity. Understanding these approaches provides valuable insights into different problem-solving strategies and their trade-offs.