Code Implementation

class Solution:
    def dominantIndex(self, nums):
        if not nums:
            return -1
        max_num = max(nums)
        max_index = nums.index(max_num)
        for i, n in enumerate(nums):
            if i != max_index and max_num < 2 * n:
                return -1
        return max_index
      

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

class Solution {
    public int dominantIndex(int[] nums) {
        if (nums.length == 0) return -1;
        int maxNum = -1, maxIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxNum) {
                maxNum = nums[i];
                maxIndex = i;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (i != maxIndex && maxNum < 2 * nums[i]) {
                return -1;
            }
        }
        return maxIndex;
    }
}
      

var dominantIndex = function(nums) {
    if (nums.length === 0) return -1;
    let maxNum = -1, maxIndex = -1;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > maxNum) {
            maxNum = nums[i];
            maxIndex = i;
        }
    }
    for (let i = 0; i < nums.length; i++) {
        if (i !== maxIndex && maxNum < 2 * nums[i]) {
            return -1;
        }
    }
    return maxIndex;
};
      

Problem Description

You are given an array of integers called nums. Your task is to find whether the largest number in the array is at least twice as large as every other number in the array. If it is, return the index of the largest number. If it is not, return -1.

• There is always exactly one largest element, so no need to handle ties.
• Elements must not be reused; comparisons are always between the largest and every other element.
• Return the index of the largest element if the condition is satisfied, otherwise return -1.

Thought Process

At first glance, the problem seems to require comparing the largest number to all other numbers in the array. A brute-force approach would be to check, for each element, if it is the largest and then see if it is at least twice every other number. However, since there is always a unique largest element, we can optimize by first finding the largest, and then verifying the "at least twice" condition against the rest.

This means we don't need to check each element as a candidate for "largest"—we only need to find the largest, and then check if it is at least twice as large as all others. This speeds up our process and avoids unnecessary comparisons.

Solution Approach

• Step 1: Traverse the array to find the largest number and its index.
• Step 2: Traverse the array again. For each element (except the largest), check if the largest number is at least twice as large as that element.
• Step 3: If you find any number where the largest is less than twice that number, return -1.
• Step 4: If all checks pass, return the index of the largest number.

We use two passes over the array: one to find the largest, and one to check the condition. This is more efficient than nested loops and ensures clarity in logic.

Example Walkthrough

Let's use the sample input nums = [3, 6, 1, 0]:

1. First, find the largest number. Here, 6 at index 1 is the largest.
2. Now, check for every other number:
   • Is 6 >= 2*3? Yes, 6 >= 6.
   • Is 6 >= 2*1? Yes, 6 >= 2.
   • Is 6 >= 2*0? Yes, 6 >= 0.
3. Since all conditions are satisfied, return the index 1.

If we try nums = [1, 2, 3, 4]:

• Largest is 4 at index 3.
• Check: 4 >= 2*3? 4 < 6 — fails!
• Return -1.

Time and Space Complexity

• Brute-force approach: For each element, compare it to all others. This is O(n^2) time.
• Optimized approach (used here): Two passes over the array. Each pass is O(n), so total time is O(n).
• Space complexity is O(1), since we only use a few variables regardless of input size.

The optimized approach is much faster and more scalable for large arrays.

Summary

This problem is elegantly solved by first identifying the largest element, then validating its dominance by comparing it to every other element. The two-pass method is efficient and easy to understand, avoiding unnecessary complexity. The key insight is realizing that only the largest element needs to be checked, thanks to the problem's constraints.