DSA problem - Second Largest

Explanation of Code: Finding the Second-Largest Element in an Array

Git Repo

The code provides a solution to determine the second-largest element in an array. This is achieved through a single traversal while maintaining two variables to track the largest and second-largest values.

Code Walkthrough

class Solution {
    public int second_largest(int[] arr) {
        // Code Here
        int n = arr.length;

        // Special case: If the array has exactly 2 elements, return the smaller one
        if (n == 2) {
            int secmax = Math.min(arr[0], arr[1]);
            return secmax;
        }

        // Initialize variables to track the largest and second largest values
        int max = -1, secmax = -1;

        // Traverse the array
        for (int i = 0; i < n; i++) {
            // If the current element is greater than the current largest
            if (arr[i] > max) {
                secmax = max; // Update second largest
                max = arr[i]; // Update largest
            }
            // If the current element is less than the largest but greater than the current second largest
            else if (arr[i] < max) {
                secmax = Math.max(arr[i], secmax);
            }
        }

        // Return the second largest value
        return secmax;
    }
}

Step-by-Step Explanation

1. Handle Edge Cases

• If the array contains exactly two elements:
  • The second-largest element is simply the smaller of the two values.
  • Example: For [3, 5], the second largest is 3.

2. Variables Initialization

• max: Tracks the largest element in the array.
• secmax: Tracks the second-largest element.
• Both are initialized to -1 as a default value.

3. Traverse the Array

The loop iterates through the array elements to update the largest and second-largest values:

1. When the current element is greater than max:
   • Update secmax to the previous value of max.
   • Update max to the current element.
2. When the current element is smaller than max but greater than secmax:
   • Update secmax to the current element.

4. Return the Result

• After the loop, secmax holds the second-largest value.

Complexity Analysis

1. Time Complexity:

   • The array is traversed once.
   • Total time complexity: O(n), where n is the length of the array.

2. Space Complexity:

   • The algorithm uses constant space for max and secmax.
   • Space complexity: O(1).

Example Walkthrough

Example 1:

Input:

arr = [1, 4, 3, 2]

Execution:

• Initialize max = -1, secmax = -1.
• Traverse the array:
  • 1: max = 1, secmax = -1.
  • 4: max = 4, secmax = 1.
  • 3: secmax = 3 (since 3 > secmax).
  • 2: No update (since 2 < secmax).
• Final values: max = 4, secmax = 3.

Output:

3

Example 2:

Input:

arr = [7, 7, 7, 7]

Execution:

• All elements are equal, so no second largest exists.
• secmax remains -1.

Output:

-1

Advantages

• The algorithm efficiently finds the second-largest element in a single traversal.
• It is memory-efficient as it uses constant space.