{x}
blog image

Largest Number At Least Twice of Others

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

 

Example 1:

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:

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 Explanation: Finding the Dominant Index

The problem asks to find the index of the largest element in an array, but only if that largest element is at least twice as large as every other element. The solution involves comparing the largest element to the second largest element. If the largest is at least twice the second largest, then it's dominant.

Approach:

The most efficient approach involves these steps:

  1. Find the Largest Element: Iterate through the array once to find the largest element and store its index.

  2. Find the Second Largest (Optional): While you could iterate again to find the second largest, it's more efficient in Python to leverage the nlargest function from the heapq module which efficiently finds the k largest elements. For other languages, a single loop can achieve this with a simple comparison.

  3. Check the Dominance Condition: Check if the largest element is at least twice the second largest. If it is, return the index of the largest element; otherwise, return -1.

Time and Space Complexity Analysis

  • Time Complexity: O(n) - The algorithm iterates through the array at most twice (once to find the largest, potentially once more to find the second largest or verify the dominance condition). Using nlargest in Python is also O(n) on average.

  • Space Complexity: O(1) - The algorithm uses only a constant amount of extra space to store variables (the largest element, its index, and potentially the second largest element).

Code Implementation in Multiple Languages

The following code demonstrates the solution in various programming languages, highlighting the differences in implementation based on available libraries and syntax.

Python:

from heapq import nlargest
 
class Solution:
    def dominantIndex(self, nums: list[int]) -> int:
        if not nums:  #Handle empty input
            return -1
        largest_two = nlargest(2, nums)
        largest = largest_two[0]
        second_largest = largest_two[1]
        
        if largest >= 2 * second_largest:
            return nums.index(largest)
        else:
            return -1

Java:

class Solution {
    public int dominantIndex(int[] nums) {
        int largest = Integer.MIN_VALUE;
        int largestIndex = -1;
        int secondLargest = Integer.MIN_VALUE;
 
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > largest) {
                secondLargest = largest;
                largest = nums[i];
                largestIndex = i;
            } else if (nums[i] > secondLargest) {
                secondLargest = nums[i];
            }
        }
 
        if (largest >= 2 * secondLargest) {
            return largestIndex;
        } else {
            return -1;
        }
    }
}

C++:

#include <vector>
#include <algorithm>
 
class Solution {
public:
    int dominantIndex(std::vector<int>& nums) {
        if(nums.empty()) return -1;
        int largest = *std::max_element(nums.begin(), nums.end());
        int largestIndex = std::distance(nums.begin(), std::max_element(nums.begin(), nums.end()));
        int secondLargest = INT_MIN;
 
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] != largest && nums[i] > secondLargest){
                secondLargest = nums[i];
            }
        }
        
        if(largest >= 2 * secondLargest) return largestIndex;
        else return -1;
    }
};

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var dominantIndex = function(nums) {
    if(nums.length === 0) return -1;
    let largest = Math.max(...nums);
    let largestIndex = nums.indexOf(largest);
    let secondLargest = Number.MIN_SAFE_INTEGER;
 
    for(let i = 0; i < nums.length; i++){
        if(nums[i] !== largest && nums[i] > secondLargest){
            secondLargest = nums[i];
        }
    }
 
    if(largest >= 2 * secondLargest) return largestIndex;
    else return -1;
};

These examples all achieve the same goal with slightly differing implementation details due to language-specific features. The core logic remains consistent across all languages.