Problem overview
The method maxInArray receives an array of integers and returns its largest value. For Array(2, 7, 11, 8, 11, 8, 3, 11) the answer is 11. It appears three times, which makes no difference: the method returns the value, not a position or a count.
The note says not to use a built-in maximum over the whole array. You write the scan yourself. The step that compares two numbers may use scala.math.max.
Approach: remember the best value so far
Walk through the array and keep the largest number seen up to now. At each element, compare it with that remembered value. If the element is bigger, it becomes the new best. After the last element, the remembered value is the maximum of the whole array, because every element was compared to it.
The one design decision is the starting value. Starting at 0 looks natural but is wrong. In an array of only negative numbers, such as Array(-5, -2, -9), 0 is larger than every element, so nothing would ever replace it and the method would return 0, a number that is not in the array. The safe start is an element of the array itself. The first element works, because the maximum of a one-element prefix is that element.
Step by step
- Declare
var maxVal = nums(0). It is avarbecause it changes. Scala reads an array element with parentheses,nums(0), not square brackets. - Loop with
for (num <- nums). This visits every element, including the first one again. The extra comparison ofnums(0)with itself is harmless. - Update with
maxVal = scala.math.max(maxVal, num). The function returns the larger of its two arguments, somaxValnever decreases and always holds the largest value seen so far. - Return
maxValafter the loop.
The solution in Scala
class Solution {
def maxInArray(nums: Array[Int]): Int = {
var maxVal = nums(0)
for (num <- nums) {
maxVal = scala.math.max(maxVal, num)
}
return maxVal
}
}
Tracing a short input, Array(3, 9, 4):
num | maxVal afterwards |
|---|---|
| 3 | 3 |
| 9 | 9 |
| 4 | 9 |
Language details
scala.math.maxis overloaded forInt,Long,FloatandDouble. With twoIntarguments it returns anInt.- The same update can be written with an
if:if (num > maxVal) maxVal = num. Both forms give the same result.
Complexity
One pass over n elements with one comparison each gives O(n) time. The method stores only maxVal and the loop variable, so the extra space is O(1).
Edge cases and common mistakes
- All negative numbers.
Array(-5, -2, -9)returns -2. A start of 0 would return 0 instead. - A single element. The method returns that element, since the loop compares it only with itself.
- The maximum at the start or at the end.
Array(9, 3, 4)andArray(3, 4, 9)both return 9. The running maximum is correct wherever the largest value sits. - Duplicated maximum.
Array(2, 7, 11, 8, 11)returns 11, the same as with one 11. - An empty array. There is no first element, so
nums(0)throwsjava.lang.ArrayIndexOutOfBoundsException. An empty array has no maximum, and the lesson doesn't ask you to handle it. - Tracking an index instead of a value. This lesson asks for the value. Remembering the position of the largest element is a different problem.
