Finding the Second Largest Element in an Array: Detailed Guide

The task of finding the second largest element in an array is a common problem that tests understanding of loops, conditions, and edge case handling. In this blog, we will dissect a function that solves this problem efficiently and also explore alternative approaches to achieve the same result.

---

Problem Statement

Given an integer array, find the second largest distinct element in the array. If the array doesn’t contain enough distinct elements (e.g., it has only one unique element), return -1.

Example:
Input: [10, 20, 20, 4, 50, 35]
Output: 35

---

Solution 1: Efficient One-Pass Approach (Code Explanation)

Here’s a Java function to solve the problem in one pass:

int getSecondLargest(int[] arr) {
    int largestInteger = -1, SecondLargest = -1;

    for (int i = 0; i < arr.length; i++) {
        if (largestInteger < arr[i]) {
            SecondLargest = largestInteger;  // Update second largest
            largestInteger = arr[i];         // Update largest
        } else if (arr[i] < largestInteger && arr[i] > SecondLargest) {
            SecondLargest = arr[i];          // Update second largest
        }
    }

    return SecondLargest;
}

---

Explanation of the Code

1. Initialization:

   • largestInteger and SecondLargest are initialized to -1 (or any other sentinel value that indicates invalid results if no valid second largest is found).

2. Iterate Through the Array:

   • For each element, compare it with the current largestInteger:

     • If the element is greater, update SecondLargest to the value of largestInteger, then update largestInteger to the new maximum.

     • If the element is smaller than largestInteger but larger than SecondLargest, update SecondLargest.

3. Edge Cases Handled:

   • Arrays with fewer than two distinct elements return -1 since SecondLargest is never updated.

---

Time and Space Complexity

• Time Complexity:
  O(n) — The array is traversed once.

• Space Complexity:
  O(1) — No extra space is used beyond a few variables.

---

Alternative Approaches

1. Sorting-Based Approach

Sort the array in descending order, then find the first element that is smaller than the largest element.

Steps:

1. Sort the array in descending order.

2. Traverse the sorted array to find the first distinct element smaller than the maximum.

Code:

int getSecondLargestBySorting(int[] arr) {
    Arrays.sort(arr);  // Sorts in ascending order
    int largest = arr[arr.length - 1];

    for (int i = arr.length - 2; i >= 0; i--) {
        if (arr[i] < largest) {
            return arr[i];
        }
    }
    return -1;  // If no second largest exists
}

Time Complexity:

• Sorting: O(n log n)

• Traversal: O(n)
  Overall: O(n log n)

Space Complexity:

• Sorting might require extra memory depending on the implementation, so O(n) in the worst case.

---

2. Set-Based Approach

Use a TreeSet to automatically maintain the largest and second largest elements.

Steps:

1. Add all elements to a TreeSet, which keeps elements sorted and removes duplicates.

2. Retrieve the two largest elements using the set's properties.

Code:

int getSecondLargestWithSet(int[] arr) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int num : arr) {
        set.add(num);
    }

    // If there are fewer than two elements in the set
    if (set.size() < 2) {
        return -1;
    }

    // Get the largest and second largest
    set.pollLast();  // Remove the largest
    return set.last();  // Second largest
}

Time Complexity:

• Insertion in TreeSet: O(log n) per element.

• Overall: O(n log n)

Space Complexity:

• O(n) for the TreeSet.

---

3. Two-Pass Approach

First pass to find the largest, second pass to find the second largest.

Steps:

1. Traverse the array to find the largest element.

2. Traverse the array again to find the largest element smaller than the maximum.

Code:

int getSecondLargestTwoPass(int[] arr) {
    int largest = Integer.MIN_VALUE;
    for (int num : arr) {
        largest = Math.max(largest, num);
    }

    int secondLargest = Integer.MIN_VALUE;
    for (int num : arr) {
        if (num < largest) {
            secondLargest = Math.max(secondLargest, num);
        }
    }

    return (secondLargest == Integer.MIN_VALUE) ? -1 : secondLargest;
}

Time Complexity:

• Two traversals: O(n + n) = O(n)

Space Complexity:

• O(1) — No additional space used.

---

Comparing the Approaches

---

Conclusion

The one-pass approach is the most efficient in terms of both time and space, making it ideal for competitive programming and large datasets. However, other approaches like sorting and sets can be useful depending on the problem constraints and requirements (e.g., handling duplicates or simplifying the logic).

Understanding multiple solutions not only makes you a better problem solver but also equips you with the ability to choose the best approach for a given situation.

What’s your favorite way of solving this problem? Share your thoughts in the comments! 🚀