Largest Number At Least Twice of Others: Single Pass Array Scan

LeetCode Largest Number At Least Twice of Others (problem 747) gives you an array of distinct integers and asks: is the largest element at least twice as large as every other element in the array? If yes, return the index of the largest element. If not, return -1.

At first glance you might think you need to compare the largest value against every single element. But there is a shortcut. You only need to compare it against the second largest. If the max is >= twice the runner-up, it automatically dominates everything else.

Why this problem matters

This problem teaches a fundamental pattern: reducing a "compare against all" question to a "compare against the most relevant competitor" question. Instead of checking every pair, you identify the one element that could possibly violate the condition (the second largest) and check only that.

You will see this same reduction in problems like finding the third maximum, checking if an element is a majority, and validating dominance conditions in sorted or partially sorted data. The core idea is that extreme values (max, min, second max) often hold all the information you need.

The approach

Track two things as you scan the array once: the maximum value (and its index) and the second maximum value. At the end, check whether the max is >= twice the second max. If yes, return the index. Otherwise, return -1.

You do not need to sort the array, build a heap, or make multiple passes. A single loop with two tracking variables is enough.

def dominant_index(nums: list[int]) -> int:
    max_val = -1
    second_max = -1
    max_idx = 0
    for i, num in enumerate(nums):
        if num > max_val:
            second_max = max_val
            max_val = num
            max_idx = i
        elif num > second_max:
            second_max = num
    return max_idx if max_val >= 2 * second_max else -1

Walk through the array once. For each element, if it is bigger than the current max, demote the old max to second place and install the new max. If it is between the max and second max, just update the second max. After the loop, one comparison tells you the answer.

Step-by-step walkthrough

Let's trace through nums = [3, 6, 1, 0] to see how the two tracking variables evolve.

The key observation is that we never need to compare 6 against 1 or 0 individually. If 6 dominates the second largest (3), it automatically dominates everything smaller than 3 as well.

Complexity analysis

All three approaches use constant space, but the single-pass solution is the cleanest. You touch each element exactly once and avoid the overhead of sorting. In an interview, start by explaining the two-pass idea (find the max first, then loop again to verify), then optimize to the single-pass version.

The building blocks

This problem relies on one core reusable pattern: tracking running extremes.

You maintain a small set of variables representing the "best so far" values and update them as new data arrives. The simplest version tracks a single maximum:

best = -1
for num in nums:
    if num > best:
        best = num

Largest Number At Least Twice extends that to two tracked values (max and second max) with a cascading update rule. The same extension works for three values (as in Third Maximum Number) or K values (as in Kth Largest Element, where a heap generalizes the idea).

The "track two extremes" brick shows up in many places:

• Buy and Sell Stock: track the minimum price seen so far and the maximum profit
• Third Maximum Number: extend to three tracked values with cascading updates
• Majority Element: track a candidate and a count (a different kind of "running extreme")

Edge cases to watch for

• Single element: An array like [5] has no second element. The largest trivially dominates everything else (there is nothing else). Return index 0.
• Two elements: [0, 3] works normally. Check if 3 >= 2 * 0, which is true. Return index 1.
• Dominance fails: [1, 2, 3, 4] has max = 4, second max = 3. Since 4 < 2 * 3 = 6, the largest is not dominant. Return -1.
• Large gap at the end: [0, 0, 0, 1] has max = 1, second max = 0. Since 1 >= 2 * 0 = 0, return index 3. Be careful with zeros.
• Negative numbers: The problem guarantees non-negative integers, so you do not need to worry about negative values. But if it did allow negatives, the comparison logic would still work as long as you initialize your tracking variables correctly.

From understanding to recall

You can read through this solution and understand every line in a few minutes. But understanding is not the same as recall. Two weeks from now, when you see a problem that requires comparing a maximum against the rest of the array, will you immediately think "I only need the second max"? Will you remember the cascading update pattern for tracking two extremes in one pass?

That is where spaced repetition makes the difference. By drilling the "track K extremes" pattern at increasing intervals, you move it from short-term comprehension into long-term muscle memory. The next time a variation appears, the solution structure fires automatically instead of requiring you to re-derive it from scratch.

Related posts

• Third Maximum Number - Extends the same "track running extremes" pattern from two values to three
• Majority Element - Another single-pass array problem where one element must dominate the rest
• Kth Largest Element - Generalizes extreme tracking using heaps and quickselect for arbitrary K