Problem overview
The function maxInArray receives an IntArray named nums and returns its largest value. The array can contain repeated values and negative numbers.
In the example, nums = [2, 7, 11, 8, 11, 8, 3, 11]. The largest value is 11, which appears three times, and the function returns 11 once, as a value rather than a count or a position.
Approach: keep the best value seen so far
To find the biggest element, you have to look at every element at least once, because any unseen one could be larger. The usual technique is a running maximum. Hold the largest value seen so far, then walk through the array and replace it whenever something bigger shows up. After the last element, the variable holds the answer.
The one decision is where the running maximum starts. A tempting choice is 0, but it breaks for arrays that contain only negative numbers: for [-5, -2, -9] a start of 0 would never be beaten, and the function would return 0, which isn't even in the array. Starting with the first element is always safe, because the maximum of the whole array is at least as large as its first element.
Step by step
- Initialize the maximum with
var maxVal = nums[0]. It is avarbecause it can be replaced during the loop. - Loop over the values with
for (num in nums). No index is needed, because only the values matter. - Update the maximum with
maxVal = maxOf(maxVal, num). The standard functionmaxOf(a, b)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 Kotlin
class Solution {
fun maxInArray(nums: IntArray): Int {
var maxVal = nums[0]
for (num in nums) {
maxVal = maxOf(maxVal, num)
}
return maxVal
}
}
The Kotlin details behind it:
maxOfcompares two values. It is a top-level function in the standard library and needs no import. It is not the same as taking the maximum of a whole array:nums.max()does that, and it is the kind of built-in the lesson's note asks you to avoid when writing the search by hand. HeremaxOfis used only as the comparison inside your own loop. Anif (num > maxVal) { maxVal = num }does the same job.- The first element is compared with itself. The loop starts at index 0, so the first pass computes
maxOf(nums[0], nums[0]). That is harmless. You could skip it withfor (i in 1 until nums.size), but the simpler loop is fine. - An empty array fails.
nums[0]on an emptyIntArraythrows anArrayIndexOutOfBoundsExceptionwith the messageIndex 0 out of bounds for length 0. A maximum of nothing has no sensible value, so the solution assumes the array has at least one element. - The type is
Int. The smallest value anIntcan hold is -2147483648. An array of nothing but that value correctly returns it, which would not work with a start value of 0 or with a made-up "minus infinity" constant that is too small.
Complexity
Let n be the length of nums.
Time: O(n). The loop visits each element once and does a constant amount of work per element.
Space: O(1). The function stores maxVal and the loop variable only.
Edge cases and common mistakes
- All negative numbers.
[-5, -2, -9]returns -2. InitializingmaxValwith 0 would return 0 instead. - A single element.
[4]returns 4. - Repeated maxima. The maximum 11 in the example appears three times. The result is the same however many times it appears.
- Returning inside the loop. The function would give up after the first element.
- Declaring the maximum inside the loop. It would be reset on every pass, and the result would depend only on the last element.
- Empty input. It throws, as described above.
Testing
[2, 7, 11, 8, 11, 8, 3, 11]gives11.[-5, -2, -9]gives-2.[4]gives4.[1, 2, 3, 4, 5]gives5, with the maximum last.[9, 3, 1]gives9, with the maximum first.