Find the Second Largest Element in an Array

Find and return the second largest element in an array of integers

Language Selection

Choose your preferred programming language

Showing: Python

Find the Second Largest Element in an Array

Problem Statement

Given an array of integers, find and return the second largest element in the array. If the second largest element doesn’t exist (e.g., all elements are the same or array has less than 2 elements), return an appropriate value.

Input/Output Specifications

  • Input: An array of integers nums where 1 <= nums.length <= 10^5 and -10^9 <= nums[i] <= 10^9
  • Output: An integer representing the second largest element, or -1 if it doesn’t exist

Constraints

  • The array contains at least one element
  • Array elements can be negative, positive, or zero
  • Array is not guaranteed to be sorted
  • All elements might be the same (no second largest exists)

Examples

Example 1:

Input: nums = [3, 1, 4, 1, 5, 9, 2, 6]
Output: 6
Explanation: The largest element is 9, second largest is 6.

Example 2:

Input: nums = [5, 5, 5, 5]
Output: -1
Explanation: All elements are the same, no second largest exists.

Example 3:

Input: nums = [10, 5]
Output: 5
Explanation: Largest is 10, second largest is 5.

Example 4:

Input: nums = [7]
Output: -1
Explanation: Only one element, no second largest exists.

Solution Approaches

Approach 1: Single Pass with Two Variables (Optimal)

Algorithm Explanation:

  1. Initialize two variables to track the largest and second largest elements
  2. Iterate through the array once
  3. For each element:
    • If it’s larger than the current largest, update both largest and second largest
    • If it’s between largest and second largest (and different from largest), update second largest
  4. Return the second largest if it was updated, otherwise return -1

Implementation:

Python:

def find_second_largest(nums):
    """
    Find second largest element using single pass
    Time: O(n)
    Space: O(1)
    """
    if not nums or 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 second_largest if second_largest != float('-inf') else -1

# Alternative approach using set and sorting
def find_second_largest_sort(nums):
    """
    Find second largest using sorting approach
    Time: O(n log n)
    Space: O(n) for the set
    """
    if not nums or len(nums) < 2:
        return -1
    
    unique_nums = list(set(nums))
    if len(unique_nums) < 2:
        return -1
    
    unique_nums.sort(reverse=True)
    return unique_nums[1]

Java:

class Solution {
    /**
     * Find second largest element using single pass
     * Time: O(n)
     * Space: O(1)
     */
    public int findSecondLargest(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        
        long largest = Long.MIN_VALUE;
        long secondLargest = Long.MIN_VALUE;
        
        for (int num : nums) {
            if (num > largest) {
                secondLargest = largest;
                largest = num;
            } else if (num > secondLargest && num != largest) {
                secondLargest = num;
            }
        }
        
        return secondLargest == Long.MIN_VALUE ? -1 : (int) secondLargest;
    }
    
    // Alternative using streams
    public int findSecondLargestStream(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        
        List<Integer> distinctSorted = Arrays.stream(nums)
            .boxed()
            .distinct()
            .sorted(Collections.reverseOrder())
            .collect(Collectors.toList());
            
        return distinctSorted.size() < 2 ? -1 : distinctSorted.get(1);
    }
}

Go:

// findSecondLargest - Find second largest element using single pass
// Time: O(n)
// Space: O(1)
func findSecondLargest(nums []int) int {
    if len(nums) < 2 {
        return -1
    }
    
    largest := math.MinInt64
    secondLargest := math.MinInt64
    
    for _, num := range nums {
        if num > largest {
            secondLargest = largest
            largest = num
        } else if num > secondLargest && num != largest {
            secondLargest = num
        }
    }
    
    if secondLargest == math.MinInt64 {
        return -1
    }
    return secondLargest
}

// Alternative using map for uniqueness
func findSecondLargestMap(nums []int) int {
    if len(nums) < 2 {
        return -1
    }
    
    uniqueMap := make(map[int]bool)
    for _, num := range nums {
        uniqueMap[num] = true
    }
    
    if len(uniqueMap) < 2 {
        return -1
    }
    
    unique := make([]int, 0, len(uniqueMap))
    for num := range uniqueMap {
        unique = append(unique, num)
    }
    
    sort.Sort(sort.Reverse(sort.IntSlice(unique)))
    return unique[1]
}

JavaScript:

/**
 * Find second largest element using single pass
 * Time: O(n)
 * Space: O(1)
 */
function findSecondLargest(nums) {
    if (!nums || nums.length < 2) {
        return -1;
    }
    
    let largest = -Infinity;
    let secondLargest = -Infinity;
    
    for (const num of nums) {
        if (num > largest) {
            secondLargest = largest;
            largest = num;
        } else if (num > secondLargest && num !== largest) {
            secondLargest = num;
        }
    }
    
    return secondLargest === -Infinity ? -1 : secondLargest;
}

// Alternative using Set and sort
function findSecondLargestSort(nums) {
    if (!nums || nums.length < 2) {
        return -1;
    }
    
    const uniqueNums = [...new Set(nums)].sort((a, b) => b - a);
    return uniqueNums.length < 2 ? -1 : uniqueNums[1];
}

// Alternative using reduce
function findSecondLargestReduce(nums) {
    if (!nums || nums.length < 2) {
        return -1;
    }
    
    const result = nums.reduce((acc, num) => {
        if (num > acc.largest) {
            acc.secondLargest = acc.largest;
            acc.largest = num;
        } else if (num > acc.secondLargest && num !== acc.largest) {
            acc.secondLargest = num;
        }
        return acc;
    }, { largest: -Infinity, secondLargest: -Infinity });
    
    return result.secondLargest === -Infinity ? -1 : result.secondLargest;
}

C#:

public class Solution {
    /// <summary>
    /// Find second largest element using single pass
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int FindSecondLargest(int[] nums) {
        if (nums == null || nums.Length < 2) {
            return -1;
        }
        
        long largest = long.MinValue;
        long secondLargest = long.MinValue;
        
        foreach (int num in nums) {
            if (num > largest) {
                secondLargest = largest;
                largest = num;
            } else if (num > secondLargest && num != largest) {
                secondLargest = num;
            }
        }
        
        return secondLargest == long.MinValue ? -1 : (int)secondLargest;
    }
    
    // Alternative using LINQ
    public int FindSecondLargestLinq(int[] nums) {
        if (nums == null || nums.Length < 2) {
            return -1;
        }
        
        var distinctSorted = nums.Distinct().OrderByDescending(x => x).ToList();
        return distinctSorted.Count < 2 ? -1 : distinctSorted[1];
    }
}

Complexity Analysis:

  • Time Complexity: O(n) - We examine each element exactly once
  • Space Complexity: O(1) - Only using a constant amount of extra space

Trade-offs:

  • Single pass through the array for optimal efficiency
  • Handles duplicates correctly
  • Minimal memory usage
  • Clear and intuitive logic

Approach 2: Sort and Remove Duplicates

Algorithm Explanation:

  1. Remove duplicates from the array
  2. Sort the unique elements in descending order
  3. Return the second element if it exists
  4. Return -1 if there are fewer than 2 unique elements

Implementation:

Python:

def find_second_largest_sort(nums):
    """
    Find second largest using sorting approach
    Time: O(n log n)
    Space: O(n)
    """
    if not nums or len(nums) < 2:
        return -1
    
    # Remove duplicates and sort
    unique_nums = sorted(set(nums), reverse=True)
    
    return unique_nums[1] if len(unique_nums) >= 2 else -1

Java:

class Solution {
    /**
     * Find second largest using sorting approach
     * Time: O(n log n)
     * Space: O(n)
     */
    public int findSecondLargestSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        
        // Convert to set to remove duplicates, then sort
        Integer[] uniqueNums = Arrays.stream(nums)
            .boxed()
            .distinct()
            .sorted(Collections.reverseOrder())
            .toArray(Integer[]::new);
            
        return uniqueNums.length < 2 ? -1 : uniqueNums[1];
    }
}

Go:

// findSecondLargestSort - Find second largest using sorting
// Time: O(n log n)
// Space: O(n)
func findSecondLargestSort(nums []int) int {
    if len(nums) < 2 {
        return -1
    }
    
    // Remove duplicates
    uniqueMap := make(map[int]bool)
    for _, num := range nums {
        uniqueMap[num] = true
    }
    
    if len(uniqueMap) < 2 {
        return -1
    }
    
    // Convert to slice and sort
    unique := make([]int, 0, len(uniqueMap))
    for num := range uniqueMap {
        unique = append(unique, num)
    }
    
    sort.Sort(sort.Reverse(sort.IntSlice(unique)))
    return unique[1]
}

JavaScript:

/**
 * Find second largest using sorting approach
 * Time: O(n log n)
 * Space: O(n)
 */
function findSecondLargestSort(nums) {
    if (!nums || nums.length < 2) {
        return -1;
    }
    
    const uniqueSorted = [...new Set(nums)].sort((a, b) => b - a);
    return uniqueSorted.length < 2 ? -1 : uniqueSorted[1];
}

C#:

public class Solution {
    /// <summary>
    /// Find second largest using sorting approach
    /// Time: O(n log n)
    /// Space: O(n)
    /// </summary>
    public int FindSecondLargestSort(int[] nums) {
        if (nums == null || nums.Length < 2) {
            return -1;
        }
        
        var uniqueSorted = nums.Distinct().OrderByDescending(x => x).ToArray();
        return uniqueSorted.Length < 2 ? -1 : uniqueSorted[1];
    }
}

Complexity Analysis:

  • Time Complexity: O(n log n) - Due to sorting
  • Space Complexity: O(n) - For storing unique elements

Trade-offs:

  • Simpler logic but less efficient
  • Uses more memory
  • Good for when array is already partially sorted
  • Easier to understand and implement

Key Insights

  • Single Pass Optimization: The optimal solution requires only one pass through the array
  • Duplicate Handling: Must distinguish between largest element appearing multiple times vs actual second largest
  • Edge Case Importance: Many edge cases need careful handling (empty array, single element, all same elements)
  • Initialization Strategy: Using appropriate initial values (negative infinity) handles negative numbers correctly

Edge Cases

  1. Empty Array: [] → Returns -1
  2. Single Element: [5] → Returns -1
  3. Two Different Elements: [3, 7] → Returns 3
  4. All Same Elements: [4, 4, 4] → Returns -1
  5. Two Same Largest: [5, 3, 5, 1] → Returns 3
  6. All Negative: [-1, -5, -3] → Returns -3

How Solutions Handle Edge Cases:

  • Length check prevents accessing invalid indices
  • Proper initialization handles negative numbers
  • Duplicate checking ensures we find truly different values
  • Clear return conditions for invalid cases

Test Cases

def test_second_largest():
    # Basic case
    assert find_second_largest([3, 1, 4, 1, 5, 9, 2, 6]) == 6
    
    # All same elements
    assert find_second_largest([5, 5, 5, 5]) == -1
    
    # Two different elements
    assert find_second_largest([10, 5]) == 5
    
    # Single element
    assert find_second_largest([7]) == -1
    
    # Empty array
    assert find_second_largest([]) == -1
    
    # All negative
    assert find_second_largest([-1, -5, -3]) == -3
    
    # Mixed with duplicates
    assert find_second_largest([1, 2, 2, 3, 3, 3]) == 2
    
    # Two identical max values
    assert find_second_largest([5, 3, 5, 1]) == 3
    
    # Large array
    large_array = [i for i in range(1000)] + [999, 998]  # duplicates
    assert find_second_largest(large_array) == 998
    
    print("All tests passed!")

test_second_largest()

Follow-up Questions

  1. Kth Largest Element: How would you find the kth largest element?
  2. Second Smallest: How would you modify this to find the second smallest?
  3. Multiple Arrays: How would you find second largest across multiple arrays?
  4. Stream of Data: How would you handle this for a continuous stream?
  5. Custom Comparator: How would you handle custom sorting criteria?

Common Mistakes

  1. Not Handling Duplicates: Treating duplicate max as second largest

    • Problem: Returning max value when all elements are the same
    • Solution: Check that num != largest before updating second largest

  2. Wrong Initialization: Using 0 or small positive numbers as initial values

    • Problem: Fails with all negative numbers
    • Solution: Use negative infinity or appropriate minimum values

  3. Index Out of Bounds: Not checking array length

    • Problem: Accessing elements when array is too small
    • Solution: Early validation of array size

  4. Missing Edge Cases: Not handling single element or empty arrays

    • Problem: Runtime errors or incorrect results
    • Solution: Explicit checks for edge cases

Interview Tips

  1. Start with Examples: Work through examples to understand the problem
  2. Handle Edge Cases Early: Discuss and implement edge case handling first
  3. Optimize Gradually: Start with sorting approach, then optimize to single pass
  4. Discuss Trade-offs: Mention time vs space complexity trade-offs
  5. Test Thoroughly: Walk through edge cases in your testing

Concept Explanations

Linear Search with State Tracking: This problem demonstrates how to maintain multiple pieces of state (largest and second largest) while traversing an array once, which is a fundamental technique in array processing.

Duplicate Handling: Understanding how to handle duplicates correctly is crucial for many array problems, especially those involving ranking or finding specific positioned elements.

When to Apply: Use this pattern when you need to find the nth largest/smallest element efficiently, or when tracking multiple extremes during a single traversal.