Largest Number At Least Twice of Others - Solution & Explanation
Problem Statement
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] <= 100- The largest element in
numsis unique.
Approach Overview
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.
Approach 1: Single Pass Approach
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.
Complexity
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.
Approach 2: Two Pass with Early Return
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.
Complexity
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Traversal
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).
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
747. Largest Number Atleast Twice Of Others Solution Explained - Java • Harshit Choudhary (The Confident Average Guy) • 2,763 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Largest Number At Least Twice of Others easy or hard?
Largest Number At Least Twice of Others Python/Java solution
How to solve Largest Number At Least Twice of Others in O(n)?
What is the best approach for Largest Number At Least Twice of Others?
Is Largest Number At Least Twice of Others asked at Google/Amazon/Meta?
What data structure is used in Largest Number At Least Twice of Others?
What is the time complexity of Largest Number At Least Twice of Others?
Ready to solve this problem?
Practice Largest Number At Least Twice of Others with our built-in code editor and test cases.
Practice on FleetCode