Domain 1EasyCORE

Largest Number At Least Twice of Others

The problem requires us to determine if the largest number in an array is at least twice as large as every other number. If it is, we return the index of that largest number; otherwise, we return -1.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

747. Largest Number At Least Twice of Others

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 43.2%


Problem Breakdown

The problem requires us to determine if the largest number in an array is at least twice as large as every other number. If it is, we return the index of that largest number; otherwise, we return -1.

Inputs:

  • An integer array nums with a length ranging from 1 to 50.
  • Each element in nums is an integer ranging from 0 to 99.

Outputs:

  • An integer representing the index of the largest number if it meets the condition, or -1 if no such number exists.

Implicit Constraints/Edge Cases:

  • The array will always have at least one element.
  • All elements are non-negative integers.
  • There is exactly one largest element in the array.

Intuition

A brute-force approach would involve sorting the array to find the largest and second-largest elements, then checking if the largest element is at least twice as large as the second-largest. However, this approach has a time complexity of O(n log n) due to sorting, which is inefficient given the constraints.

The key insight is that we only need to track the two largest numbers in the array during a single pass. This reduces the time complexity to O(n), making it more efficient for larger arrays.

Approach

  1. Initialize two variables, first and second, to store the largest and second-largest numbers found so far. Set them to negative infinity initially.
  2. Iterate through the array:
    • If the current number is greater than or equal to first, update second to be first and then update first to be the current number, also update first_index to the current index.
    • Otherwise, if the current number is greater than second, update second to be the current number.
  3. After the iteration, check if first is at least twice as large as second. If it is, return the index of first; otherwise, return -1.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We make a single pass through the array to find the two largest numbers.
  • Space Complexity: O(1), as we only use a constant amount of extra space for storing first, second, and first_index.

Solution

def dominantIndex(nums):
    if len(nums) == 1:
        return 0
    
    first = second = -float('inf')
    first_index = -1
    
    for i, num in enumerate(nums):
        if num > first:
            second = first
            first = num
            first_index = i
        elif num > second:
            second = num
    
    if first >= 2 * second:
        return first_index
    else:
        return -1

Edge Cases Handled

  • Single Element Array: If the array has only one element, it is trivially the largest and at least twice as large as any other number (none exist), so we return its index 0.
  • All Elements Equal: If all elements are equal, first and second will be the same value, and the condition first >= 2 * second will fail, returning -1.
  • Largest Element is Zero: If the largest element is zero, it cannot be at least twice as large as any other number (since all numbers are non-negative), so we return -1.