Problem overview
The method SecondLargest receives an int[] and returns its second largest value. Duplicates of the maximum don't count as the second largest. For [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times, and the second largest value is 8, not 11.
The statement promises at least two distinct values, so a second largest always exists. It also poses a follow-up: can it be done in one pass without sorting? This lesson takes the sorting route, which is simpler to get right.
Approach: sort, then skip the maximum
Once the array is sorted ascending, the maximum is the last element. Every copy of the maximum sits at the end, in a block. The second largest value is the first element, scanning backwards, that differs from the maximum.
The sorted example is [2, 3, 7, 8, 8, 11, 11, 11]. Starting at the second-to-last index and walking down: 11 equals the maximum, so skip it; 11 again, skip it; 8 differs from the maximum, so return 8.
The sort costs O(n log n). The backward scan is at most one pass. A one-pass solution can reach O(n) by tracking the largest and second largest values while reading the array, but it has more cases to get right.
Step by step
- Sort the array with
Array.Sort(nums), ascending and in place, so the largest values are at the end. - Loop backwards with
istarting atnums.Length - 2, the index just before the maximum, and counting down to 0. - Compare with the maximum. Inside the loop, check whether
nums[i]differs fromnums[nums.Length - 1]. Elements equal to the maximum are duplicates and must be skipped. - Return the first different value. The first element from the back that differs from the maximum is the second largest.
- Add a fallback
return -1. The compiler requires a return on every path through the method. The guarantee of two distinct values means this line is never reached on valid input.
The solution in C#
class Solution {
public int SecondLargest(int[] nums) {
Array.Sort(nums);
for (int i = nums.Length - 2; i >= 0; i--) {
if (nums[i] != nums[nums.Length - 1]) {
return nums[i];
}
}
return -1;
}
}
The C# details to notice:
- Every path must return. C# rejects a method with a non-void return type if the compiler can see a way to reach the closing brace without a
return. Aforloop with a conditionalreturninside doesn't satisfy that, so the trailingreturn -1;is required even though valid input never reaches it. - Counting down. The loop uses
i--and the conditioni >= 0. With anintindex, going below 0 ends the loop cleanly. Using the conditioni > 0would skip index 0, which breaks inputs such as[1, 2]. - The last element is the maximum.
nums[nums.Length - 1]is read again on each iteration. C# has the shorthandnums[^1]for the same element, but the longer form shows the arithmetic. - The input array is sorted in place. The caller's array is reordered by the call.
Complexity
Time: O(n log n). The sort dominates. The backward loop runs at most n - 1 times, which is O(n).
Space: O(1) extra. The array is sorted in place and the method keeps only the loop index.
Edge cases and common mistakes
- Repeated maximum. Returning
nums[nums.Length - 2]directly is wrong for[5, 9, 9], where the answer is 5, not 9. The scan skips every copy of the maximum. - Exactly two values.
[1, 2]sorts to[1, 2]. The loop starts at index 0, finds that 1 differs from 2, and returns 1. - Negative numbers.
[-5, -5, -9]sorts to[-9, -5, -5]and gives -9, since -5 is the maximum. Starting a "largest so far" variable at 0 is a common mistake in the one-pass version, because it breaks for negative arrays. - Using the first element. Reading
nums[1]after an ascending sort gives the second smallest, not the second largest. - All values equal. The statement rules this out. If it happened, the loop would find no different value and return the fallback -1, which is also a valid array element, so it is not a safe signal.
Testing
[2, 7, 11, 8, 11, 8, 3, 11]gives 8.[1, 2]gives 1.[-5, -5, -9]gives -9.[5, 9, 9]gives 5.