Problem overview
The function secondLargest receives a slice nums of integers and returns its second largest distinct value. The slice is guaranteed to hold at least two different values.
For [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11 and it appears three times. The second largest is 8, not 11: repeats of the maximum don't count as a runner-up. The answer is 8.
Approach: track two numbers in a single pass
The obvious solution sorts the slice and looks near the end, but then you must skip duplicates of the maximum, and sorting costs O(n log n). You can do better by walking through the slice once and remembering only two values: the largest seen so far and the largest value seen that is smaller than it.
Each number you read falls into one of three cases:
- It is bigger than the current maximum. The old maximum becomes the runner-up, and the number becomes the new maximum.
- It is smaller than the maximum but bigger than the runner-up. It is a better runner-up.
- Anything else, including a repeat of the maximum, changes nothing.
Tracing the example from the statement, the pair (maxVal, second) changes like this:
- After 2: (2, sentinel), because the sentinel is smaller than everything.
- After 7: (7, 2). After 11: (11, 7).
- After 8: (11, 8), since 8 is below the maximum and above the runner-up.
- The second 11, the second 8 and the 3 change nothing. The 11 equals the maximum, the 8 equals the runner-up, and the 3 is below it.
The final pair is (11, 8), so the function returns 8. Note that the answer is the second largest value, not the value at the second-to-last position of a sorted copy, which here would be 11.
The sentinel start value is a shortcut. It works because the problem guarantees real values above it, and a stricter version could instead start from the first element and handle the second distinct value separately.
Step by step
- Declare
maxValandsecondwith:=, both set to-2147483648, the smallest 32-bit integer. Any real value in the slice is at least that, so no special case for the first element is needed. - Range over
nums, discarding the index with_and naming the valuenum. - Test
num > maxVal. A new maximum pushes the old one down to second place. - Copy first, overwrite second. Set
second = maxValand only thenmaxVal = num. With the lines swapped, the old maximum is lost and both variables end up equal. - Add an
else iffornum < maxVal && num > second. The strict comparison withmaxValkeeps duplicates of the maximum from taking second place. - Update
secondtonumin that branch. - Return
secondafter the loop.
The solution in Go
func secondLargest(nums []int) int {
maxVal := -2147483648
second := -2147483648
for _, num := range nums {
if num > maxVal {
second = maxVal
maxVal = num
} else if num < maxVal && num > second {
second = num
}
}
return second
}
The Go details worth knowing:
for _, num := range numsyields an index and a value on each pass. Go refuses unused variables, so the unused index is replaced by the blank identifier_.:=infersintfrom the constant. In Gointis 64 bits, so the literal fits easily.else ifchains the two conditions: the second test only runs whennum > maxValwas false. Go has no ternary operator, so branching like this usesif.- Parentheses are not needed around conditions, but the braces are mandatory.
Complexity
Time is O(n), one pass with constant work per element. Space is O(1): two integers, however long the slice is.
Edge cases and common mistakes
- Duplicates of the maximum. For
[3, 3, 5]and[5, 3, 3]the answer is 3 in both. In[3, 5, 5]the answer is also 3, because the second 5 equalsmaxValand fails both tests. - Ascending and descending input.
[1, 2, 3, 4]and[4, 3, 2, 1]both give 3. The first order exercises the "new maximum" branch every time, the second the "better runner-up" branch. - Negative numbers.
[-5, -3, -9]gives -5. The sentinel is far below any ordinary negative value, so these work. - All values equal.
[7, 7, 7]never updatessecond, so the function returns the sentinel-2147483648. The guarantee of two distinct values rules this out. - Values below the sentinel. Since Go's
intis 64 bits, a value such as-3000000000is smaller than the starting value and is never picked up. The sentinel trick only suits inputs within 32-bit range. - Using
>=for the maximum test. That would let a duplicate of the maximum overwritesecondwith the maximum itself.
Testing
When you test, try the ordering extremes as well as the repeats, since the two branches of the loop behave differently depending on the order of the input.
[]int{1, 2}returns 1.[]int{2, 1}returns 1.[]int{2, 7, 11, 8, 11, 8, 3, 11}returns 8.[]int{-5, -3, -9}returns -5.