Problem overview
minAndMax gets an ArrayBuffer[Int] called nums with at least one number. It returns the smallest and the largest number together as a tuple (Int, Int), smallest first. For [4, -2, 9, 0] the answer is (-2,9). For [7] it is (7,7), because the only number is both the smallest and the largest. For [-5, -1, -8] it is (-8,-1).
The rule is to find both in one loop, without the built-in min and max.
Approach
Keep two variables: low, the smallest number seen so far, and high, the largest. Look at each number once. If it is below low, it becomes the new low. If it is above high, it becomes the new high. When the loop ends, both variables hold the answer.
Both must start at the first number, nums(0). Starting low at 0 breaks when every number is above 0, because 0 would win and it isn't in the list. Starting high at 0 breaks the same way when every number is negative. The first number is always a real candidate for both.
This is a single pass, so the work grows in step with the length of the buffer, and the extra memory is just two integers. Every number is between -1,000,000 and 1,000,000, which fits easily in an Int, so there is no overflow to worry about.
Step by step
- Declare
lowandhighwithvar, each set tonums(0). They change during the loop, sovalwould not work. - Write a
forloop with the generatornum <- nums. - Inside, if
num < low, setlow = num. - Still inside, in a separate
if, ifnum > high, sethigh = num. - After the loop, return the two values in parentheses.
The two checks are separate if statements, not if and else. With one number in the list, the same number must be able to set both variables, and the first number, which equals both variables, sets neither.
The solution in Scala
class Solution {
def minAndMax(nums: ArrayBuffer[Int]): (Int, Int) = {
var low = nums(0)
var high = nums(0)
for (num <- nums) {
if (num < low) {
low = num
}
if (num > high) {
high = num
}
}
return (low, high)
}
}
(low, high) builds the tuple, and the return type (Int, Int) says what it holds. The caller can unpack it with val (lo, hi) = minAndMax(nums). Printing the result shows the values without a space, like (-2,9).
Tracing the first example
Printing low and high after each number of [4, -2, 9, 0] shows how the two variables move:
num=4 low=4 high=4
num=-2 low=-2 high=4
num=9 low=-2 high=9
num=0 low=-2 high=9
The first number matches both variables, so nothing changes. Then -2 lowers low, 9 raises high, and 0 is between them and changes nothing.
Another way
Once you may use built-ins, (nums.min, nums.max) builds the same tuple and prints (-2,9) for this input. It reads the buffer twice, once for each call. The loop reads it once, which is what this lesson practices.
Testing
The lesson's examples give these results:
[4, -2, 9, 0] (-2,9)
[7] (7,7)
[-5, -1, -8] (-8,-1)
Edge cases and common mistakes
- Starting at 0. With
[4, 7]andlowstarting at 0, the loop never finds anything below 0 and returns 0, a number that isn't in the list. - Returning
(high, low). The smallest comes first. - Using
else if. It works for most lists, but separate checks are simpler to reason about. - An empty buffer. The lesson promises at least one number, so
nums(0)is safe. On an empty buffer it would throw an exception.
