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: largest and 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 $O(N)$ approach avoids the $O(N \log N)$ cost of sorting.

1. If the array has fewer than 2 elements, return None.
2. Initialize largest = arr[0] and second_largest = None.
3. Traverse from index 1. For each element:
   • If arr[i] > largest: set second_largest = largest, then largest = arr[i].
   • Else if arr[i] < largest and (second_largest is None or arr[i] > second_largest): update second_largest.
4. Skip duplicates of the largest to handle arrays like [10, 10, 5].
5. 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 0 or $-\infty$ without considering that all elements might be negative

This problem teaches you to track multiple states during a single traversal. The key insight: you don't need to sort. One careful $O(N)$ pass with well-maintained variables is enough.