Problem overview
The function secondLargest receives a slice of integers, nums, and returns the second largest value. Duplicates of the maximum don't count as the second largest: it is the largest value that is strictly smaller than the maximum. The slice is guaranteed to hold at least two distinct values.
For nums = [2, 7, 11, 8, 11, 8, 3, 11], the maximum is 11, which appears three times. The next smaller value is 8, so the answer is 8, not 11.
This lesson sorts the slice, which takes O(n log n) time. A single pass that tracks the two largest values seen so far reaches O(n), and the statement mentions it as a follow-up. Sorting is shorter to write and easier to reason about.
Approach: sort descending, skip the maximum
If the slice is sorted from largest to smallest, the maximum sits at index 0 and all copies of it come first. Scanning from the left, the first value that differs from nums[0] is the second largest. Checking by value rather than by index is what handles the duplicates. Just returning nums[1] would give 11 on the example.
After the descending sort, the example becomes [11, 11, 11, 8, 8, 7, 3, 2]. The scan skips three 11s and stops at the first 8.
Step by step
- Sort descending with
sort.Slice.sort.Intsonly sorts ascending, so this lesson usessort.Slice, which takes the slice and a comparison function. The function receives two indices,iandj, and returnstruewhen the element atimust come before the element atj. Returningnums[i] > nums[j]puts larger values first. - Loop over the values.
for _, num := range numsyields the index and the value on each pass. The blank identifier_discards the index, because Go refuses unused variables. - Compare with the maximum. Inside the loop, test
num != nums[0]. Values equal to the maximum are duplicates of the largest, so they are skipped. - Return the first different value. Since the slice is in descending order, it is the second largest.
- Add the fallback
return -1. Go requires every path through a function with a result to end in a return. The compiler can't know the guarantee about two distinct values, so it demands a line after the loop. For valid input, it is never reached.
The solution in Go
func secondLargest(nums []int) int {
sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] })
for _, num := range nums {
if num != nums[0] {
return num
}
}
return -1
}
Go details:
- The comparison function is a closure. It refers to
numsfrom the enclosing function, and the argumentsiandjare indices, not values. Writingfunc(a, b int) bool { return a > b }would compile but compare the indices, giving the wrong order. sort.Slicesorts in place. After the call on the example, the caller's slice reads[11 11 11 8 8 7 3 2].- The comparison must be a strict "less than" style test (
>here, not>=), becausesort.Sliceexpects a consistent ordering. - The file needs
import "sort".
Complexity
Time: O(n log n). The sort costs O(n log n). The scan stops at the first smaller value and never exceeds O(n).
Space: O(1) extra. The sort works in place, and the function stores only the loop variables. The input slice is reordered.
Edge cases and common mistakes
- Duplicates of the maximum. Returning
nums[1]is wrong for[2, 7, 11, 8, 11, 8, 3, 11]. Compare withnums[0]by value. - Exactly two values.
[1, 2]gives 1, and[4, 4, 1]gives 1. - Negative numbers.
[-5, -1, -1]returns -5. The answer can be negative, so the sentinel-1at the end can't be told apart from a real answer of -1 (for example in[-1, -2]). That's harmless only because the fallback is unreachable for valid input. - All values equal.
[4, 4]breaks the guarantee, and the function returns the fallback -1. An empty slice also returns -1, since the loop never runs. - Sorting ascending by mistake. With
sort.Ints, the maximum is at the end, and the scan from the left would return the smallest value different fromnums[0].
Try in the editor above: the example should give 8, [1, 2] should give 1 and [-5, -1, -1] should give -5.