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 _theindex of the largest element, or return _-1 otherwise.

Examples

Example 1

1
2
3
4
5

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

1
2
3

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.

Solution

Method 1 – Find Max and Second Max

Intuition

To check if the largest number is at least twice every other, find the largest and second largest numbers. If the largest is at least twice the second largest, return its index; otherwise, return -1.

Approach

  1. Iterate through the array to find the largest and second largest values and the index of the largest.
  2. Check if the largest is at least twice the second largest.
  3. Return the index if true, else -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int mx = -1, smx = -1, idx = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > mx) { smx = mx; mx = nums[i]; idx = i; }
            else if (nums[i] > smx) smx = nums[i];
        }
        return mx >= 2 * smx ? idx : -1;
    }
};
1
2
3
4
5
6
7
8

func dominantIndex(nums []int) int {
    mx, smx, idx := -1, -1, -1
    for i, v := range nums {
        if v > mx { smx, mx, idx = mx, v, i } else if v > smx { smx = v }
    }
    if mx >= 2*smx { return idx }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int dominantIndex(int[] nums) {
        int mx = -1, smx = -1, idx = -1;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > mx) { smx = mx; mx = nums[i]; idx = i; }
            else if (nums[i] > smx) smx = nums[i];
        }
        return mx >= 2 * smx ? idx : -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun dominantIndex(nums: IntArray): Int {
        var mx = -1
        var smx = -1
        var idx = -1
        for (i in nums.indices) {
            if (nums[i] > mx) { smx = mx; mx = nums[i]; idx = i }
            else if (nums[i] > smx) smx = nums[i]
        }
        return if (mx >= 2 * smx) idx else -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def dominantIndex(self, nums: list[int]) -> int:
        mx = smx = -1
        idx = -1
        for i, v in enumerate(nums):
            if v > mx:
                smx, mx, idx = mx, v, i
            elif v > smx:
                smx = v
        return idx if mx >= 2 * smx else -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn dominant_index(nums: Vec<i32>) -> i32 {
        let (mut mx, mut smx, mut idx) = (-1, -1, -1);
        for (i, &v) in nums.iter().enumerate() {
            if v > mx { smx = mx; mx = v; idx = i as i32; }
            else if v > smx { smx = v; }
        }
        if mx >= 2 * smx { idx } else { -1 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    dominantIndex(nums: number[]): number {
        let mx = -1, smx = -1, idx = -1
        for (let i = 0; i < nums.length; ++i) {
            if (nums[i] > mx) { smx = mx; mx = nums[i]; idx = i }
            else if (nums[i] > smx) smx = nums[i]
        }
        return mx >= 2 * smx ? idx : -1
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is visited once.
  • 🧺 Space complexity: O(1), only a few variables are used.