# Largest Number At Least Twice of Others
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-number-at-least-twice-of-others)
Canonical: https://scaleengineer.com/dsa/problems/largest-number-at-least-twice-of-others
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` where the largest integer is **unique**.

Determine whether the largest element in the array is **at least twice** as much as every other number in the array. If it is, return _the **index** of the largest element, or return_ `-1` _otherwise_.

**Example 1:**

**Input:** nums = [3,6,1,0]
**Output:** 1
**Explanation:** 6 is the largest integer.
For every other number in the array x, 6 is at least twice as big as x.
The index of value 6 is 1, so we return 1.

**Example 2:**

**Input:** nums = [1,2,3,4]
**Output:** -1
**Explanation:** 4 is less than twice the value of 3, so we return -1.

**Constraints:**

* `2 <= nums.length <= 50`
* `0 <= nums[i] <= 100`
* The largest element in `nums` is unique.

# Approaches
## Sorting Approach
This approach involves sorting a copy of the array to easily identify the largest and second-largest elements. The comparison is then straightforward, but it requires finding the original index of the largest element.
**Time:** O(N log N) - Dominated by the sorting algorithm. Finding the index in the original array takes an additional O(N) time. · **Space:** O(N) - Required to store a copy of the array to preserve the original indices after sorting.
**Pros:** The logic to find the largest and second-largest elements becomes very simple after sorting.
**Cons:** Less efficient in terms of time complexity compared to linear scan approaches.; Requires extra space for the array copy.
### Explanation
The core idea is that after sorting, the largest element will be the last element in the array, and the second-largest will be the second to last. This simplifies finding these two key values. Since sorting modifies the array, we must work on a copy to preserve the original indices, which are needed for the final result.

```java
import java.util.Arrays;

class Solution {
    public int dominantIndex(int[] nums) {
        // Constraints guarantee nums.length >= 2
        int[] numsCopy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(numsCopy);
        
        int maxVal = numsCopy[nums.length - 1];
        int secondMaxVal = numsCopy[nums.length - 2];
        
        if (maxVal < 2 * secondMaxVal) {
            return -1;
        }
        
        // Find the original index of the max value
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == maxVal) {
                return i;
            }
        }
        
        return -1; // Should not be reached due to problem constraints
    }
}
```
### Algorithm
- If the array has only one element, the condition is trivially met, so we return index 0.
- Create a copy of the input array `nums` to preserve the original indices.
- Sort the copied array in ascending order.
- The largest element is `sorted_nums[n-1]` and the second largest is `sorted_nums[n-2]`.
- Check if `sorted_nums[n-1] >= 2 * sorted_nums[n-2]`. If not, the condition fails, so return -1.
- If the condition holds, we need the original index of the largest element. Iterate through the original `nums` array to find the first occurrence of `sorted_nums[n-1]` and return its index.

## Two-Pass Linear Scan
This approach iterates through the array twice. The first pass finds the largest element and its index. The second pass verifies if this largest element is at least twice as large as every other element.
**Time:** O(N) - We perform two separate linear scans of the array, which results in O(N) + O(N) = O(N) time. · **Space:** O(1) - We only use a few variables to store the maximum value and its index, requiring constant extra space.
**Pros:** Simple to implement and understand.; Efficient O(N) time complexity.; No extra space required.
**Cons:** Requires iterating through the array twice, which is less optimal than a single-pass solution.
### Explanation
This is a straightforward approach that separates the problem into two distinct steps: finding the maximum and then verifying the condition. It's more efficient than sorting as it avoids the O(N log N) overhead by using linear scans.

```java
class Solution {
    public int dominantIndex(int[] nums) {
        // Constraints guarantee nums.length >= 2
        int maxVal = -1;
        int maxIndex = -1;
        
        // First pass: find the max element and its index
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        
        // Second pass: check the condition
        for (int i = 0; i < nums.length; i++) {
            if (i != maxIndex && maxVal < 2 * nums[i]) {
                return -1;
            }
        }
        
        return maxIndex;
    }
}
```
### Algorithm
- Initialize `maxVal` to the minimum possible value and `maxIndex` to -1.
- **First Pass:** Iterate through the `nums` array to find the largest element `maxVal` and its index `maxIndex`.
- **Second Pass:** Iterate through the `nums` array again.
- For each element `num` at index `i`: If `i` is not the `maxIndex`, check if `maxVal < 2 * num`. If this condition is ever met, return -1 immediately.
- If the second loop completes without returning, it means the condition holds for all other elements. Return `maxIndex`.

## Single-Pass Linear Scan
The most efficient approach, which finds the largest and second-largest elements in a single pass through the array. After the pass, it performs a final check to see if the condition is met.
**Time:** O(N) - The array is traversed only once. · **Space:** O(1) - Only a few variables are used to track the state, requiring constant extra space.
**Pros:** Most optimal solution with linear time and constant space.; Processes the array in a single pass, making it very efficient.
**Cons:** The logic can be slightly more complex to reason about compared to a two-pass approach, as it involves updating two maximums simultaneously.
### Explanation
By keeping track of both the largest and second-largest numbers seen so far, we can solve the problem in one iteration. The key insight is that we only need to compare the largest number with the second-largest number. If the largest is at least twice the second-largest, it will also be at least twice every other number, as all other numbers are smaller than or equal to the second-largest.

```java
class Solution {
    public int dominantIndex(int[] nums) {
        // Constraints guarantee nums.length >= 2
        int maxVal = -1;
        int secondMaxVal = -1;
        int maxIndex = -1;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxVal) {
                secondMaxVal = maxVal;
                maxVal = nums[i];
                maxIndex = i;
            } else if (nums[i] > secondMaxVal) {
                secondMaxVal = nums[i];
            }
        }
        
        if (maxVal >= 2 * secondMaxVal) {
            return maxIndex;
        }
        
        return -1;
    }
}
```
### Algorithm
- Initialize `maxVal = -1`, `secondMaxVal = -1`, and `maxIndex = -1`.
- Iterate through the `nums` array once.
- For each element `num` at index `i`:
  - If `num` is greater than the current `maxVal`, it means we've found a new largest number. The old `maxVal` becomes the new `secondMaxVal`. Update `secondMaxVal = maxVal`, `maxVal = num`, and `maxIndex = i`.
  - Otherwise, if `num` is greater than the current `secondMaxVal` (but not `maxVal`), it's the new second-largest number. Update `secondMaxVal = num`.
- After the loop, we have the largest and second-largest values.
- Check if `maxVal >= 2 * secondMaxVal`. If it is, return `maxIndex`. Otherwise, return -1.

# Solutions
### Java

```java
class Solution {
public
  int dominantIndex(int[] nums) {
    int n = nums.length;
    int k = 0;
    for (int i = 0; i < n; ++i) {
      if (nums[k] < nums[i]) {
        k = i;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (k != i && nums[k] < nums[i] * 2) {
        return -1;
      }
    }
    return k;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var dominantIndex =
  function (nums) {
    let k = 0;
    for (let i = 0; i < nums.length; ++i) {
      if (nums[i] > nums[k]) {
        k = i;
      }
    }
    for (let i = 0; i < nums.length; ++i) {
      if (i !== k && nums[k] < nums[i] * 2) {
        return -1;
      }
    }
    return k;
  };

```

### CPP

```cpp
class Solution {
public:
  int dominantIndex(vector<int> &nums) {
    int n = nums.size();
    int k = 0;
    for (int i = 0; i < n; ++i) {
      if (nums[k] < nums[i]) {
        k = i;
      }
    }
    for (int i = 0; i < n; ++i) {
      if (k != i && nums[k] < nums[i] * 2) {
        return -1;
      }
    }
    return k;
  }
};

```

### Python

```python
class Solution:
    def dominantIndex(self, nums: List[int]) -> int: x, y = nlargest(2, nums) return nums . index(x) if x >= 2 * y else - 1

```