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 <= 500 <= nums[i] <= 100The largest element of nums is unique.
Hints for Largest Number At Least Twice of Others
Hint 1
Only one other value matters: if the largest beats the runner-up by a factor of two, it beats everything else too.
Hint 2
Find the index of the maximum in one pass.
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
- Scan once to find
best, the index of the maximum. - Scan again: if any other index
jhas2 * nums[j] > nums[best], return-1. - 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 bestJava
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