Find the Largest Number

Q: What is the time complexity of finding the maximum in an array?

One pass takes O(n) time and O(1) extra space. No method on an unsorted array does better, because any element you never read could be the largest. Sorting first costs O(n log n) .

BeginnerArrays and strings

+10

You get a non-empty list of integers nums. Return the largest value in it. The values can be negative, so the answer can be negative too. Find it with your own comparisons, without a built-in maximum function such as max.

Function

findMax(nums: integer-array) → integer

numsinteger-array: the list of integers to search
Returnsinteger: the largest value in nums

Constraints

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Examples

Input: nums = [3, 17, 4, 12, 9]
Output: 17
Explanation: Reading from the left, the largest value so far is 3, then 17. None of 4, 12 or 9 beats 17.

Input: nums = [-8, -3, -11, -3]
Output: -3
Explanation: Every value is negative and -3 is the closest to zero, so it is the largest. It appears twice, but you return the value, not a position.

Follow-up

Can you return both the largest and the smallest value with about 3n/2 comparisons instead of 2n, by comparing the values in pairs first?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Any value you skip could be the largest, so every solution reads every element. One pass with a running maximum does that and nothing more. Start the maximum at the first element, never at 0, because every value may be negative.

Sort a copy and take the last value

Intuition

Copy nums so the caller's list stays as it was, sort the copy from smallest to largest, and return its last element. For [3, 17, 4, 12, 9] the sorted copy is [3, 4, 9, 12, 17].

Sorting puts every value in order when you want only the top one. That is about n log n comparisons, roughly 60,000 for n = 5000, plus O(n) memory for the copy.

Algorithm

Copy nums.
Sort the copy from smallest to largest, comparing numbers as numbers.
Return the last element of the sorted copy.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

One pass with a running maximum

Intuition

Keep largest, the biggest value seen so far, and replace it whenever a value is bigger. After the loop it has been compared with every element, so nothing in the list beats it. For [3, 17, 4, 12, 9] it starts at 3, becomes 17 and stays there: n-1 comparisons and one extra variable.

Starting at nums[0] is what makes negative lists work. Start at 0 and nothing in [-8, -3, -11, -3] beats it, so you return 0, a value that is not in the list.

Algorithm

Set largest to nums[0].
Loop over every value x in nums.
If x > largest, set largest to x.
After the loop, return largest.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

Pitfalls and edge cases

Starting at a guessed small number such as -1000000. Values go down to -10^9, so [-2000000] returns the guess. nums[0] needs no guess.
Reading nums[0] in Lua or R, where the first element is nums[1]. Lua returns nil and R an empty vector.
Looping with i ≤ n on 0-based indexes, which reads one element past the end.
Sorting without a numeric comparator in JavaScript or TypeScript. The text order of [3, 17, 4, 12, 9] ends with 9, so you return 9.

Frequently asked questions3

What is the time complexity of finding the maximum in an array?

One pass takes O(n) time and O(1) extra space. No method on an unsorted array does better, because any element you never read could be the largest. Sorting first costs O(n log n).

How do you find the largest number in an array without using max?

Store the first element in a variable. Loop over the rest and, whenever an element is bigger, store it instead. When the loop ends, the variable holds the largest value.

When is sorting a good way to find the largest value?

When you need more than the top value, such as the three largest or the median, and will ask many such questions about the same list. For a single maximum, one pass is faster and leaves the list untouched.

def findMax(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [3, 17, 4, 12, 9]

Expected Output