LeetCode 747: Largest Number At Least Twice of Others

Problem Restatement

We are given an integer array nums.

We need to determine whether the largest element is at least twice as large as every other number in the array.

If this condition is true, return the index of the largest element.

Otherwise, return:

-1

The official problem guarantees that the largest element is unique. (leetcode.com)

Input and Output

Example function shape:

def dominantIndex(nums: list[int]) -> int:
    ...

Examples

Example 1

nums = [3, 6, 1, 0]

Largest number:

6

Check all other values:

All conditions hold.

The index of 6 is:

1

So the answer is:

1

Example 2

nums = [1, 2, 3, 4]

Largest number:

4

But:

4 < 2 * 3

So the condition fails.

The answer is:

-1

First Thought: Compare Largest Against Everyone

The problem directly asks whether the largest value dominates every other value.

So the simplest idea is:

1. Find the largest element.
2. Compare it against all other elements.

This already gives an efficient linear solution.

We only need to avoid unnecessary repeated work.

Key Insight

To verify the condition:

largest >= 2 * every other value

we only need:

• the largest value,
• the second largest value.

Why?

If the condition holds for the second largest value, it automatically holds for every smaller value.

So the problem reduces to:

largest >= 2 * second_largest

We can find both values in one scan.

Algorithm

Maintain:

largest
second_largest
largest_index

Scan through the array.

For each number:

1. If it becomes the new largest:
   • move the old largest into second_largest
   • update largest
   • update largest_index
2. Otherwise, update second_largest if needed.

After the scan:

• If:

largest >= 2 * second_largest

return largest_index.

Otherwise return:

-1

Correctness

The scan maintains the largest and second largest values seen so far.

After processing the entire array:

• largest is the maximum value in the array.
• second_largest is the largest value among all remaining elements.

If:

largest >= 2 * second_largest

then the largest value is at least twice as large as the second largest value. Since every other element is less than or equal to the second largest value, the condition also holds for all remaining elements.

Therefore the largest value is dominant, and returning its index is correct.

If the inequality fails for the second largest value, then the dominant condition already fails for at least one array element. So returning -1 is correct.

Thus the algorithm always returns the required answer.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def dominantIndex(self, nums: list[int]) -> int:
        largest = -1
        second_largest = -1
        largest_index = -1

        for i, num in enumerate(nums):
            if num > largest:
                second_largest = largest
                largest = num
                largest_index = i
            elif num > second_largest:
                second_largest = num

        if largest >= 2 * second_largest:
            return largest_index

        return -1

Code Explanation

We initialize tracking variables:

largest = -1
second_largest = -1
largest_index = -1

While scanning the array:

for i, num in enumerate(nums):

if a new maximum appears:

if num > largest:

the old largest becomes the second largest:

second_largest = largest

Then update the new largest:

largest = num
largest_index = i

Otherwise, we may still need to update the second largest:

elif num > second_largest:
    second_largest = num

After the scan, only one condition matters:

largest >= 2 * second_largest

If true, return the index of the largest element.

Otherwise return:

-1

Alternative Simpler Version

Another approach:

1. Find the maximum value and its index.
2. Scan again and verify the condition.

class Solution:
    def dominantIndex(self, nums: list[int]) -> int:
        largest = max(nums)
        index = nums.index(largest)

        for i, num in enumerate(nums):
            if i != index and largest < 2 * num:
                return -1

        return index

This also runs in linear time.

Testing

def run_tests():
    s = Solution()

    assert s.dominantIndex([3, 6, 1, 0]) == 1
    assert s.dominantIndex([1, 2, 3, 4]) == -1
    assert s.dominantIndex([1]) == 0
    assert s.dominantIndex([0, 0, 1]) == 2
    assert s.dominantIndex([2, 1]) == 0
    assert s.dominantIndex([5, 2, 1]) == 0
    assert s.dominantIndex([10, 6]) == -1

    print("all tests passed")

run_tests()