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 can do better, because any element you never read could be the largest. Sorting first costs O(n log n) , which is slower for no gain.

Q: Why should the running maximum start at the first element and not at 0?

If every value is negative, none of them is bigger than 0 , so a maximum that starts at 0 never changes and the function returns 0 . The first element is always a real candidate, so starting there is correct for any list. The smallest integer of your language also works, as long as the list is never empty.

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, so the answer is 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 its position.

+13 hidden tests on Submit

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 at least once. The one real decision is where the running maximum starts. Start it at the first element, never at 0, because every value in the list may be negative.

Sort a copy and take the last value

Intuition

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

The answer is right, but sorting does far more than you need. It puts every value in order, which takes about n log n comparisons, roughly 60,000 for n = 5000, when you only want the top one. The copy also costs O(n) memory.

In JavaScript and TypeScript, pass a comparator to sort. Without one it compares the numbers as text, which puts 12 and 17 before 3.

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 one variable, largest, for the biggest value seen so far. Start it at nums[0], compare it with every value, and replace it whenever a value is bigger. When the loop ends, largest has been compared with every element, so nothing in the list beats it.

For [3, 17, 4, 12, 9], largest starts at 3, becomes 17, and stays 17 through 4, 12 and 9. That is n-1 useful comparisons and one extra variable.

Starting at nums[0] is what makes negative lists work. Start at 0 instead and [-8, -3, -11, -3] never beats it, so you return 0, a value that is not even 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

The loop is short, so the mistakes are in where it starts and what it reads.

Starting largest at 0 or -1. Any list whose values are all below that start returns a number that is not in the list.
Starting at a made-up small number such as -1000000. The values here go down to -10^9, so the start still wins. nums[0] needs no guess.
Reading nums[0] in Lua or R, where the first element is nums[1]. Lua returns nil and R returns an empty vector.
Looping with i ≤ n in a language with 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 instead of 17.

Frequently asked questions4

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 can do better, because any element you never read could be the largest. Sorting first costs O(n log n), which is slower for no gain.

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 than the variable, store that element instead. When the loop ends, the variable holds the largest value.

Why should the running maximum start at the first element and not at 0?

If every value is negative, none of them is bigger than 0, so a maximum that starts at 0 never changes and the function returns 0. The first element is always a real candidate, so starting there is correct for any list. The smallest integer of your language also works, as long as the list is never empty.

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

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

Python

def findMax(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

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

Expected