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.