Largest Number At Least Twice Of Others - Leetcode Solution

Problem:

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, and 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 isn't at least as big as twice the value of 3, so we return -1.

Solution:

We need to find the largest integer in the array and check if it is at least twice the value of every other number in the array. We can do this in the following steps:

1. Find the index of the largest integer in the array.

2. Iterate over the array again and check if any number is greater than half of the largest number. If we find any such number, we can return -1.

3. If we don't find any such number, we return the index of the largest integer.

Here is the code to implement the above steps:

class Solution: def dominantIndex(self, nums: List[int]) -> int: max_index = 0 max_num = nums[0]

    for i in range(1, len(nums)):
        if nums[i] > max_num:
            max_num = nums[i]
            max_index = i
            
    for i in range(len(nums)):
        if i != max_index and nums[i] * 2 > max_num:
            return -1
    
    return max_index

We start by initializing the max_index as 0 and max_num as the first element of the array. We then iterate over the array starting from the second element and check if any number is greater than the current max_num. If we find any such number, we update the max_num and max_index accordingly.

We then iterate over the array again and check if any number is greater than half of the largest integer. If we find any such number, we return -1.

Finally, if we don't find any such number, we return the index of the largest integer.

This solution has a time complexity of O(n), where n is the length of the array.

1