Given an integer array nums, which always contains a unique largest integer, find the largest element and check whether it is at least twice every other number in the array. If so, return the index of the largest element; otherwise, return -1.

Example 1:

**Input:** nums = [3,6,1,0]
**Output:** 1
**Explanation:** 6 is the largest integer, and it is greater than twice every other integer in the array. Its index is 1, so return 1.

Example 2:

**Input:** nums = [1,2,3,4]
**Output:** -1
**Explanation:** 4 is not at least twice as large as 3, so return -1.

Example 3:

**Input:** nums = [1]
**Output:** 0
**Explanation:** Because there are no other numbers, 1 is considered at least twice every other number.

Constraints:

• 1 <= nums.length <= 50
• 0 <= nums[i] <= 100
• The largest element in nums is unique.

Source: LeetCode Link: https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others Copyright belongs to LeetCode. For commercial use, contact the official copyright holder; for non-commercial use, cite the source as required.

Analysis

#

The idea is straightforward. First find the largest integer, then determine whether it is at least twice every other number. Once the largest number is known, it is enough to compare it with the second-largest number: if twice the second-largest number is no greater than the largest number, all remaining numbers satisfy the condition as well.

We can find the largest and second-largest values in one pass. Use two variables, first and second, to store their indices (because the final answer is an index). During the traversal:

1. Check whether the current number is greater than the number at index first. If it is, the largest number becomes the current number.
2. If it is greater than the number at index second and less than the number at index first, replace the second-largest value with the current number.
3. If neither condition holds, do nothing.

After one pass, we have the indices of both the largest and second-largest numbers. Compare the largest number with twice the second-largest number to obtain the answer.

We also need to handle special cases such as an array of length one and the initial values of the indices. Here, usize::MAX, the maximum value of usize, marks an uninitialized index. The corresponding conditions include checks such as first == usize::MAX; if first does not yet refer to a valid element, assign it first.

Rust Code

#

impl Solution {
    pub fn dominant_index(nums: Vec<i32>) -> i32 {
        let mut first = usize::MAX;
        let mut second = usize::MAX;
        for i in 0..nums.len() {
            if first == usize::MAX || nums[i] > nums[first] {
                second = first;
                first = i;
            } else if second == usize::MAX || nums[i] > nums[second] && i != first {
                second = i;
            }
        }
        if second == usize::MAX || nums[first] >= nums[second] * 2 {first as i32} else {-1}
    }
}