Largest Number At Least Twice of Others

easy array scan

Problem

Given an integer array, return the index of the largest element if it is at least twice as large as every other number, otherwise return -1.

Inputnums=[3,6,1,0]

Output1

6 is at index 1 and is at least double every other entry.

input

def dominantIndex(nums):
    best = second = -1
    best_i = -1
    for i, v in enumerate(nums):
        if v > best:
            second = best; best = v; best_i = i
        elif v > second:
            second = v
    return best_i if best >= 2 * second else -1

function dominantIndex(nums) {
  let best = -1, second = -1, bi = -1;
  for (let i = 0; i < nums.length; i++) {
    const v = nums[i];
    if (v > best) { second = best; best = v; bi = i; }
    else if (v > second) second = v;
  }
  return best >= 2 * second ? bi : -1;
}

class Solution {
  public int dominantIndex(int[] nums) {
    int best = -1, second = -1, bi = -1;
    for (int i = 0; i < nums.length; i++) {
      int v = nums[i];
      if (v > best) { second = best; best = v; bi = i; }
      else if (v > second) second = v;
    }
    return best >= 2 * second ? bi : -1;
  }
}

class Solution {
public:
  int dominantIndex(vector<int>& nums) {
    int best = -1, second = -1, bi = -1;
    for (int i = 0; i < (int)nums.size(); i++) {
      int v = nums[i];
      if (v > best) { second = best; best = v; bi = i; }
      else if (v > second) second = v;
    }
    return best >= 2 * second ? bi : -1;
  }
};

Explanation

The question really asks one thing: is the biggest number at least double every other number? The smart shortcut is that you only need to compare the biggest against the second biggest — if it beats that one by 2x, it automatically beats all the smaller ones too.

So we walk through the array once while keeping three things: best (largest value), best_i (its index), and second (the runner-up).

For each value v: if it is bigger than best, the old best becomes the new second and v takes over as best. Otherwise, if it is still bigger than second, it becomes the new second.

At the end we just check best >= 2 * second. If yes, return best_i; if not, return -1.

Example: nums = [3, 6, 1, 0]. After scanning, best = 6 at index 1 and second = 3. Since 6 >= 2 * 3, the answer is index 1.

Time: O(n) Space: O(1)