Largest Number At Least Twice of Others

Easy
1099.

Largest Number At Least Twice of Others

Largest Number At Least Twice of Others is an easy coding problem on arrays and sorting, asked in Amazon and Google interviews.

In nums the largest value occurs exactly once. Call it dominant when it is at least twice as large as every other value in the array.

Return the index of the largest value if it is dominant, and -1 otherwise.

Example 1

Input
nums = [3,6,1,0]
Output
1
Explanation
6 is the largest value and 6 >= 2 * 3, 6 >= 2 * 1, 6 >= 2 * 0.

Example 2

Input
nums = [1,2,3,4]
Output
-1
Explanation
4 is the largest value but 4 < 2 * 3.

Example 3

Input
nums = [8,0,3]
Output
0

Constraints

  • 2 <= nums.length <= 50
  • 0 <= nums[i] <= 100
  • The largest element of nums is unique.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var dominantIndex = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Number At Least Twice of Others — Problem & Solution

Largest Number At Least Twice of Others solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Largest Number At Least Twice of Others is an easy coding problem on arrays and sorting, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In nums the largest value occurs exactly once. Call it dominant when it is at least twice as large as every other value in the array.

Return the index of the largest value if it is dominant, and -1 otherwise.

Example 1

Input: nums = [3,6,1,0]
Output: 1
Explanation: 6 is the largest value and 6 >= 2 * 3, 6 >= 2 * 1, 6 >= 2 * 0.

Example 2

Input: nums = [1,2,3,4]
Output: -1
Explanation: 4 is the largest value but 4 < 2 * 3.

Example 3

Input: nums = [8,0,3]
Output: 0

Constraints

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

Hints for Largest Number At Least Twice of Others

  1. Hint 1

    Only one other value matters: if the largest beats the runner-up by a factor of two, it beats everything else too.

  2. Hint 2

    Find the index of the maximum in one pass.

  3. Hint 3

    Then check 2 * nums[j] <= nums[best] for every other index — or track the second largest during the first pass.

How to solve Largest Number At Least Twice of Others

The maximum is dominant exactly when it is at least twice the second-largest value, since every other element is no bigger than that one.

Approach

  1. Scan once to find best, the index of the maximum.
  2. Scan again: if any other index j has 2 * nums[j] > nums[best], return -1.
  3. Otherwise return best.

Why it works

The condition is a statement about every other element, and checking each of them directly is exactly what the definition asks. Because the maximum is unique, no other element is equal to it, so the comparison never trips on a duplicate of the maximum itself.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Return the index, not the value.
  • Zeros are allowed: [0,1] returns 1, because 1 >= 2 * 0.
  • Exclude the maximum itself from the check, or it fails against itself whenever it is positive.

Reference solution

Python

from typing import List

def dominantIndex(nums: List[int]) -> int:
    best = 0
    for i in range(1, len(nums)):
        if nums[i] > nums[best]:
            best = i
    for j, x in enumerate(nums):
        if j != best and x * 2 > nums[best]:
            return -1
    return best

Java

public static int dominantIndex(int[] nums) {
    int best = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[best]) best = i;
    }
    for (int j = 0; j < nums.length; j++) {
        if (j != best && nums[j] * 2 > nums[best]) return -1;
    }
    return best;
}

C++

int dominantIndex(vector<int>& nums) {
    int n = nums.size(), best = 0;
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[best]) best = i;
    }
    for (int j = 0; j < n; j++) {
        if (j != best && nums[j] * 2 > nums[best]) return -1;
    }
    return best;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms