LeetCode 747 - Largest Number At Least Twice of Others

The problem gives us an integer array nums in which the largest value is guaranteed to be unique. Our task is to determine whether this largest number is at least twice as large as every other number in the array.

leetcodeeasyarraysorting

LeetCode Problem 747

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem gives us an integer array nums in which the largest value is guaranteed to be unique. Our task is to determine whether this largest number is at least twice as large as every other number in the array. If that condition is satisfied, we return the index of the largest element. Otherwise, we return -1.

In simpler terms, we need to identify the maximum value and verify that all remaining values are no greater than half of it. Since the maximum value is unique, we never need to worry about ties for the largest element.

The input is an array of integers with length between 2 and 50. Each value is between 0 and 100. These constraints are very small, which means even less efficient solutions would still run comfortably within limits. However, the goal is still to design a clean and optimal solution.

The output is an integer representing either:

  • the index of the dominant element, meaning the largest element that is at least twice every other element
  • or -1 if no such element exists

Several edge cases are important to recognize immediately.

An array with only two elements is the smallest valid input size, so the algorithm must correctly compare just one pair. Arrays containing zeros can also be tricky because any positive number is at least twice zero. Another important case occurs when the second-largest number is very close to the maximum. For example, in [1,2,3,4], the maximum value 4 is not at least twice 3, so the answer is -1.

The guarantee that the largest element is unique simplifies the logic significantly because we only need to compare the maximum against the second-largest value. If the maximum is at least twice the second-largest value, then it is automatically at least twice every smaller value as well.

Approaches

Brute Force Approach

A straightforward solution is to examine every element and check whether it satisfies the condition against all other elements.

First, we identify the largest element and its index. Then, for every other number in the array, we verify whether:

largest >= 2 * current_number

If any comparison fails, we immediately return -1. Otherwise, after checking all elements, we return the index of the largest number.

This approach is correct because it explicitly validates the required condition for every element in the array. However, it performs unnecessary repeated comparisons. For each candidate maximum, we potentially compare against every other element.

Although the constraints are small enough that this works efficiently in practice, we can do better conceptually.

Optimal Approach

The key observation is that we only need to compare the largest element with the second-largest element.

If the largest value is at least twice the second-largest value, then it must also be at least twice every smaller number. Therefore, instead of comparing against all elements repeatedly, we can solve the problem in a single pass while tracking:

  • the largest number
  • the index of the largest number
  • the second-largest number

Once the traversal is complete, we simply check whether:

largest >= 2 * second_largest

This reduces the solution to linear time with constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compare the maximum against every other element repeatedly
Optimal O(n) O(1) Track the largest and second-largest values in one pass

Algorithm Walkthrough

  1. Initialize variables to track the largest value, the second-largest value, and the index of the largest value.

We need these three pieces of information because the final decision depends only on the relationship between the largest and second-largest elements. 2. Traverse the array once.

During traversal, compare each number with the current largest value. 3. If the current number is greater than the largest value, update both tracking variables.

The old largest value becomes the second-largest value, and the current number becomes the new largest value. We also store its index. 4. Otherwise, if the current number is greater than the current second-largest value, update the second-largest value.

This ensures that we always maintain the two largest numbers seen so far. 5. After processing all elements, check whether the largest value is at least twice the second-largest value.

If:

largest >= 2 * second_largest

then return the stored index of the largest value. 6. Otherwise, return -1.

Why it works

The algorithm maintains the invariant that after each iteration:

  • largest stores the maximum value seen so far
  • second_largest stores the second-highest value seen so far

At the end of traversal, these values are correct for the entire array. Since every other number is less than or equal to the second-largest number, verifying the condition against only the second-largest number is sufficient to guarantee the condition for all elements.

Python Solution

from typing import List

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

        for index, value in enumerate(nums):
            if value > largest:
                second_largest = largest
                largest = value
                largest_index = index
            elif value > second_largest:
                second_largest = value

        if largest >= 2 * second_largest:
            return largest_index

        return -1

The implementation begins by initializing three tracking variables. largest stores the maximum value encountered so far, second_largest stores the second-highest value, and largest_index remembers the position of the maximum value.

The loop iterates through the array once using enumerate, which provides both the index and value together.

Whenever a new maximum value is found, the previous maximum becomes the second-largest value. Then the current value becomes the new maximum, and its index is recorded.

If the current value is not the largest but is still larger than the current second-largest value, we update only second_largest.

After the loop finishes, the code checks whether the dominant condition holds. If the largest number is at least twice the second-largest number, the stored index is returned. Otherwise, the function returns -1.

Go Solution

func dominantIndex(nums []int) int {
    largest := -1
    secondLargest := -1
    largestIndex := -1

    for index, value := range nums {
        if value > largest {
            secondLargest = largest
            largest = value
            largestIndex = index
        } else if value > secondLargest {
            secondLargest = value
        }
    }

    if largest >= 2*secondLargest {
        return largestIndex
    }

    return -1
}

The Go implementation follows the same logic as the Python version. Go uses range to iterate through the slice while retrieving both index and value.

Since the problem constraints guarantee non-negative integers, initializing largest and secondLargest to -1 is safe.

Unlike Python, Go does not require explicit type hints because variable types are inferred automatically. Integer overflow is not a concern here because values are limited to at most 100.

Worked Examples

Example 1

Input:

nums = [3,6,1,0]

We track the variables throughout the traversal.

Iteration Value Largest Second Largest Largest Index
Start - -1 -1 -1
0 3 3 -1 0
1 6 6 3 1
2 1 6 3 1
3 0 6 3 1

After traversal:

largest = 6
second_largest = 3

Check the condition:

6 >= 2 * 3
6 >= 6

The condition is true, so we return index 1.

Example 2

Input:

nums = [1,2,3,4]
Iteration Value Largest Second Largest Largest Index
Start - -1 -1 -1
0 1 1 -1 0
1 2 2 1 1
2 3 3 2 2
3 4 4 3 3

After traversal:

largest = 4
second_largest = 3

Check the condition:

4 >= 2 * 3
4 >= 6

The condition is false, so we return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) The array is traversed exactly once
Space O(1) Only a few variables are used regardless of input size

The algorithm performs a single linear scan through the array. Each element is processed once with constant-time comparisons and assignments. No additional data structures proportional to the input size are used, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.dominantIndex([3, 6, 1, 0]) == 1  # standard valid dominant case
assert solution.dominantIndex([1, 2, 3, 4]) == -1  # largest is not twice second largest

assert solution.dominantIndex([1, 0]) == 0  # smallest valid input size
assert solution.dominantIndex([0, 1]) == 1  # dominant value at the end
assert solution.dominantIndex([0, 0, 1]) == 2  # zeros with one positive dominant value

assert solution.dominantIndex([2, 1]) == 0  # exactly twice
assert solution.dominantIndex([5, 2]) == 0  # clearly dominant
assert solution.dominantIndex([5, 3]) == -1  # close but not enough

assert solution.dominantIndex([10, 1, 2, 3]) == 0  # dominant at beginning
assert solution.dominantIndex([1, 2, 3, 8]) == 3  # dominant at end

assert solution.dominantIndex([0, 0, 0, 1]) == 3  # many zeros
assert solution.dominantIndex([100, 49, 20]) == 0  # maximum constraint values

assert solution.dominantIndex([4, 1, 2]) == 0  # dominant with mixed values
assert solution.dominantIndex([8, 4, 2, 1]) == 0  # equality boundary condition
assert solution.dominantIndex([7, 4, 1]) == -1  # fails due to second-largest
Test Why
[3,6,1,0] Standard successful example
[1,2,3,4] Standard failure example
[1,0] Minimum array length
[0,1] Dominant value at last index
[0,0,1] Handling zeros correctly
[2,1] Exact equality boundary
[5,2] Clear dominant condition
[5,3] Largest not large enough
[10,1,2,3] Dominant value at beginning
[1,2,3,8] Dominant value at end
[0,0,0,1] Multiple zeros
[100,49,20] Upper constraint values
[4,1,2] Mixed ordering
[8,4,2,1] Equality condition still valid
[7,4,1] Failure caused by second-largest value

Edge Cases

One important edge case occurs when the largest value is exactly twice the second-largest value. For example, in [2,1] or [8,4,2,1], the condition should still succeed because the problem says "at least twice," not "strictly greater than twice." A common mistake is using > instead of >=. The implementation handles this correctly with the condition:

largest >= 2 * second_largest

Another important case involves arrays containing many zeros. For example, [0,0,0,1] should return the index of 1 because any positive number is at least twice zero. Algorithms that incorrectly initialize tracking variables or mishandle zero comparisons may fail here. Initializing with -1 avoids this issue because all array values are non-negative.

A third edge case occurs when the second-largest value is very close to the maximum value. For example, [5,3] or [1,2,3,4] should return -1. Some incorrect implementations only compare the maximum against a subset of elements or fail to properly track the second-largest value. This solution explicitly maintains the correct second-largest value throughout traversal, ensuring accurate final validation.