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 <= 500 <= nums[i] <= 100nums is unique.Problem Overview: You receive an integer array and must return the index of the largest element if it is at least twice as large as every other value. If the condition fails for any element, return -1. The challenge is verifying this dominance condition efficiently while scanning the array.
Approach 1: Single Pass Approach (O(n) time, O(1) space)
This method scans the array once while tracking the largest and second-largest values. During iteration, update the maximum and shift the previous maximum to second place when needed. After the loop, verify the condition max >= 2 * secondMax. If the condition holds, return the index of the maximum; otherwise return -1. The key insight is that only the second-largest element matters when validating the "twice of others" condition. If the largest element is at least twice the second-largest, it automatically satisfies the requirement for all remaining values. This approach is optimal because it performs a single linear scan and uses constant extra memory.
Arrays are the core data structure here, so understanding basic iteration patterns is essential. Problems like this commonly appear in array traversal exercises where you maintain running statistics such as maximum, minimum, or frequency counts.
Approach 2: Two Pass with Early Return (O(n) time, O(1) space)
This version separates the task into two stages. The first pass finds the maximum value and its index. The second pass verifies the condition by iterating again and checking whether any other element violates max >= 2 * nums[i]. If a violating element appears, return -1 immediately. Otherwise return the stored index. The early return avoids unnecessary comparisons once the condition fails. Although it uses two passes instead of one, the overall time complexity remains linear.
This approach is often easier to reason about during interviews because the logic is explicit: first determine the candidate maximum, then validate it. If you were allowed to reorder the array, you could also solve it using sorting by comparing the last two elements, though sorting would increase the complexity to O(n log n) and is unnecessary.
Recommended for interviews: The single-pass approach is typically the expected solution. It demonstrates strong control over array traversal and constant-space optimization. The two-pass method is still acceptable and often easier to implement quickly, but recognizing that only the top two values matter shows deeper problem insight.
This approach involves finding the largest element and its index, while also keeping track of the second largest element during a single pass over the array. If the largest element is at least twice as large as the second largest, we return its index. Otherwise, we return -1.
The C code uses a loop to first determine the largest number and stores its index. In another loop, it checks whether this largest number is at least twice as large as every other number.
Time Complexity: O(n), where n is the number of elements in the array because we pass through the list twice.
Space Complexity: O(1), since no additional data structures are used.
This approach makes two passes over the array. The first pass finds the maximum value and second largest value. If the maximum value is twice as large as the second largest value, we return the index of the maximum, otherwise return -1.
The C solution first finds the maximum and second maximum values. It then checks if the maximum value is at least twice as large as the second one.
Time Complexity: O(n).
Space Complexity: O(1).
We can traverse the array nums to find the maximum value x and the second largest value y in the array. If x \ge 2y, then return the index of x, otherwise return -1.
We can also first find the maximum value x in the array and find the index k of the maximum value x at the same time. Then traverse the array again. If we find an element y outside of k that satisfies x < 2y, then return -1. Otherwise, return k after the traversal ends.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Single Pass Approach | Time Complexity: O(n), where n is the number of elements in the array because we pass through the list twice. |
| Two Pass with Early Return | Time Complexity: O(n). |
| Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Pass Approach | O(n) | O(1) | Best general solution. Tracks largest and second largest in one scan. |
| Two Pass with Early Return | O(n) | O(1) | Simpler logic for interviews: first find max, then validate condition. |
LeetCode 747 | Largest number at least twice of others | Day 16 | 100 Days_LeetCode_Challenge • edSlash • 8,694 views views
Watch 9 more video solutions →Practice Largest Number At Least Twice of Others with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor