Second Largest

Given an array of integers, find the second largest element. For example, given [10, 5, 20, 8], the output is 10. If all elements are the same (e.g., [10, 10, 10]) or the array has fewer than 2 elements, return -1 or None.

Finding the second largest requires tracking two values simultaneously: the largest and the second largest. As you traverse, each element either becomes the new largest (pushing the old largest down to second), becomes the new second largest, or is irrelevant. This single-pass approach avoids sorting the entire array.

1. If the array has fewer than 2 elements, return None. 2. Initialize largest = arr[0] and second_largest = None. 3. Traverse the array starting from index 1. 4. If arr[i] > largest: update second_largest = largest, then largest = arr[i]. 5. Else if arr[i] < largest and (second_largest is None or arr[i] > second_largest): update second_largest = arr[i]. 6. Skip duplicates of the largest to handle arrays like [10, 10, 5]. 7. Return second_largest, or -1 if no valid second largest exists.

- Sorting the array first (O(N log N)) when a single O(N) pass suffices - Not handling duplicates: [20, 20, 10] should return 10, not 20 - Initializing second_largest to a value like 0 or -infinity without considering that all elements might be negative - Missing the edge case where all elements are identical

This problem teaches you to track multiple states during a single traversal, a pattern that appears frequently in DSA. The key insight is that you don't need to sort — one careful pass with well-maintained variables is enough. This single-pass thinking is essential for optimizing many array problems.