# 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:

```python
-1
```

The official problem guarantees that the largest element is unique. ([leetcode.com](https://leetcode.com/problems/largest-number-at-least-twice-of-others/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Index of dominant largest element, otherwise `-1` |
| Dominant condition | Largest value `>= 2 * every other value` |
| Largest element | Guaranteed unique |

Example function shape:

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

## Examples

### Example 1

```python
nums = [3, 6, 1, 0]
```

Largest number:

```python
6
```

Check all other values:

| Value | Condition |
|---:|---|
| 3 | `6 >= 2 * 3` |
| 1 | `6 >= 2 * 1` |
| 0 | `6 >= 2 * 0` |

All conditions hold.

The index of `6` is:

```python
1
```

So the answer is:

```python
1
```

### Example 2

```python
nums = [1, 2, 3, 4]
```

Largest number:

```python
4
```

But:

```text
4 < 2 * 3
```

So the condition fails.

The answer is:

```python
-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:

```text
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:

```text
largest >= 2 * second_largest
```

We can find both values in one scan.

## Algorithm

Maintain:

```python
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:

```python
largest >= 2 * second_largest
```

return `largest_index`.

Otherwise return:

```python
-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:

```python
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | One scan through the array |
| Space | `O(1)` | Only a few variables are stored |

## Implementation

```python
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:

```python
largest = -1
second_largest = -1
largest_index = -1
```

While scanning the array:

```python
for i, num in enumerate(nums):
```

if a new maximum appears:

```python
if num > largest:
```

the old largest becomes the second largest:

```python
second_largest = largest
```

Then update the new largest:

```python
largest = num
largest_index = i
```

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

```python
elif num > second_largest:
    second_largest = num
```

After the scan, only one condition matters:

```python
largest >= 2 * second_largest
```

If true, return the index of the largest element.

Otherwise return:

```python
-1
```

## Alternative Simpler Version

Another approach:

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

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `[3, 6, 1, 0]` | Standard dominant example |
| `[1, 2, 3, 4]` | Dominant condition fails |
| `[1]` | Single element array |
| `[0, 0, 1]` | Zero values |
| `[2, 1]` | Exact twice condition |
| `[5, 2, 1]` | Largest dominates all others |
| `[10, 6]` | Largest not twice the second largest |