Problem 1.1 · Big-O and ComplexityEasy

Find the Maximum Element

What it teaches: The simplest O(n) algorithm: one pass with one variable. Also why sorting first (O(n log n)) is wasted work.

The problem

Given a non-empty integer array nums, return its largest value.

Example 1

Input: nums = [3, 7, 2, 9, 4]
Output: 9

Example 2

Input: nums = [-5, -2, -9]
Output: -2

Works with negatives: don't start the maximum at 0.

Constraints

1 ≤ nums.length ≤ 10⁶
−10⁹ ≤ nums[i] ≤ 10⁹

Pattern clues in the wording

→ A single summary value of the whole array
→ n up to 10⁶ means O(n) is the target

These clues point to Running State in One Pass: Walk the input once and keep a few variables (best so far, minimum so far, a count) that summarise everything seen.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int findMax(int[] nums) {
        int max = nums[0];
        // compare every other element with max
        return max;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [3,7,2,9,4]	9
2	nums = [-5,-2,-9]	-2
3	nums = [42]	42

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Sort and take the last · O(n log n)2. Optimal: one pass · O(n)

Sort and take the last

Time O(n log n) Space O(1) extra

Sort the array and return the last element. Correct, but sorting does O(n log n) work to answer a question that only needs one look at each element.

Approach 1

import java.util.Arrays;

class Solution {
    public int findMax(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length - 1];
    }
}

Verdict: Correct but slower than necessary, and it reorders the input.

Optimal: one pass

Time O(n) Space O(1)

Keep max, starting with nums[0]. For every other element, if it's bigger, it becomes the new max.

▶ Dry run: Scanning for the maximumnums = [3, 7, 2, 9, 4]

↑i

State(vars)

max = 3

Step 1/5Start with max = nums[0] = 3.

Approach 2

class Solution {
    public int findMax(int[] nums) {
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) max = nums[i];
        }
        return max;
    }
}

Verdict: Every element must be looked at at least once (any unseen element could be the max), so O(n) is the best possible.

Before you submit

Edge cases and common mistakes

Test these inputs

One element
All negative numbers
Maximum at the first or last index
Duplicates of the maximum

Mistakes people make

Starting max at 0, which returns 0 for an all-negative array.
Starting the loop at index 0 and comparing nums[0] with itself (harmless, but sloppy).

Interview

Follow-up questions

Why is O(n) the best possible here?

How would you return the index of the maximum instead?

Command Palette