Largest Number At Least Twice of Others

Difficulty: Easy | Acceptance: 52.40% | Paid: No Topics: Array, Sorting

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.

• Examples
• Constraints
• Approach 1: Sorting
• Approach 2: Linear Scan (Two Pass)
• Approach 3: Linear Scan (One Pass)

Examples

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

1 <= nums.length <= 50
0 <= nums[i] <= 100
It is guaranteed that there is a unique largest element in nums.

Approach 1: Sorting

Intuition Sort the array to easily access the largest and second largest elements. If the largest is at least twice the second largest, it is automatically at least twice as large as all others.

Steps

• Create a list of pairs containing the value and original index.
• Sort this list based on the values.
• Compare the largest value (last element) with the second largest value (second to last element).
• If the condition is met, return the original index of the largest value; otherwise, return -1.

class Solution:
    def dominantIndex(self, nums: list[int]) -> int:
        indexed = [(val, i) for i, val in enumerate(nums)]
        indexed.sort(key=lambda x: x[0])
        if len(indexed) == 1:
            return 0
        if indexed[-1][0] >= 2 * indexed[-2][0]:
            return indexed[-1][1]
        return -1

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Sorting takes O(n log n) time. We use O(n) space to store indices.

Approach 2: Linear Scan (Two Pass)

Intuition Find the maximum value and its index in the first pass. Then, iterate through the array again to verify if this maximum is at least twice every other number.

Steps

• Iterate through the array to find the maximum value and its index.
• Iterate through the array a second time.
• For each number that is not the maximum, check if the maximum is less than twice that number.
• If any such number exists, return -1. Otherwise, return the index of the maximum.

class Solution:
    def dominantIndex(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return 0
        max_val = max(nums)
        max_idx = nums.index(max_val)
        for x in nums:
            if x != max_val and max_val < 2 * x:
                return -1
        return max_idx

Complexity

• Time: O(n)
• Space: O(1)
• Notes: We traverse the array twice, which is still linear time. Uses constant extra space.

Approach 3: Linear Scan (One Pass)

Intuition We can find the largest and second largest numbers in a single pass. If the largest is at least twice the second largest, the condition is satisfied for all other numbers (since they are smaller than or equal to the second largest).

Steps

• Initialize variables to track the maximum value, its index, and the second maximum value.
• Iterate through the array.
• Update the maximum and second maximum values accordingly when a new maximum is found.
• After the loop, check if the maximum is at least twice the second maximum.
• Return the index of the maximum if true, otherwise -1.

class Solution:
    def dominantIndex(self, nums: list[int]) -> int:
        max_val = -1
        second_max = -1
        max_idx = -1
        for i, x in enumerate(nums):
            if x > max_val:
                second_max = max_val
                max_val = x
                max_idx = i
            elif x > second_max:
                second_max = x
        if max_val >= 2 * second_max:
            return max_idx
        return -1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the most optimal approach, solving the problem in a single pass with constant space.