Problem overview
The method trimmedTotal gets a list of integers and returns their sum without one smallest and one largest value. Some contests score this way: the lowest and highest judge scores are dropped, so one very strict or very kind judge can't decide alone.
Only one copy of each extreme is dropped. For [7, 9, 6, 8, 10] the smallest is 6 and the largest is 10, so the result is 7 + 9 + 8 = 24. For [5, 1, 5, 9, 1] the value 1 appears twice, but only one 1 is dropped, with the 9: 5 + 5 + 1 = 11. For [-4, 3, -2] only -2 is left, so the result is -2. The list has 3 to 100 numbers.
Approach
Sorting the list and slicing off the ends would work, but there is an easier route. Add everything first, then subtract the smallest value once and the largest value once. Subtracting each exactly one time removes exactly one copy of each, even when the values repeat.
Step by step
- Store the sum of all numbers in an
intnamedtotal: make a stream ofnums, turn each value into anintwithmapToInt(x -> x), and callsum(). - Store the smallest number in
smallestwithCollections.min(nums). You get one value, even if it appears twice. - Store the largest number in
largestwithCollections.max(nums). - Return
total - smallest - largest.
The solution in Java
class Solution {
public int trimmedTotal(List<Integer> nums) {
int total = nums.stream().mapToInt(x -> x).sum();
int smallest = Collections.min(nums);
int largest = Collections.max(nums);
return total - smallest - largest;
}
}
Run on the three examples, this returns 24, 11 and -2. The method never reads an empty list, because the statement guarantees at least 3 numbers, so Collections.min and Collections.max are safe here. With values up to 1000 in magnitude and at most 100 of them, the total fits easily in an int.
Edge cases and common mistakes
- Repeated extremes. In
[5, 1, 5, 9, 1]the result is 11, not 10. Removing every 1 would take away too much. Subtracting the minimum a single time drops one copy only. - Negative numbers. In
[-4, 3, -2], subtracting -4 adds 4 back to the total. The formula still works: -3 - (-4) - 3 = -2. - Exactly three numbers. One number remains: the middle one in sorted order.
- All numbers equal. With
[5, 5, 5]the total is 15, the smallest and largest are both 5, and the result is 5: one 5 is dropped from each end.
Complexity
The sum, the minimum and the maximum each scan the list once, so the time is O(n) with O(1) extra space. Sorting would take O(n log n).
Testing
Try these inputs:
[7, 9, 6, 8, 10]gives24.[5, 1, 5, 9, 1]gives11.[-4, 3, -2]gives-2.
The whole method is three reads of the list and one subtraction. The order of the lines matters little, but computing total first keeps the idea clear: add everything, then take the two extremes off.
Another way to think about it is that the answer is the sum of all the numbers except two positions. The subtraction removes the values of those positions without having to know where they are in the list, which also means there is no need to sort or to copy the list.
