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
numswith a length ranging from 1 to 50. - Each element in
numsis 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
- Initialize two variables,
firstandsecond, to store the largest and second-largest numbers found so far. Set them to negative infinity initially. - Iterate through the array:
- If the current number is greater than or equal to
first, updatesecondto befirstand then updatefirstto be the current number, also updatefirst_indexto the current index. - Otherwise, if the current number is greater than
second, updatesecondto be the current number.
- If the current number is greater than or equal to
- After the iteration, check if
firstis at least twice as large assecond. If it is, return the index offirst; 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, andfirst_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,
firstandsecondwill be the same value, and the conditionfirst >= 2 * secondwill 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.