Largest Number At Least Twice of Others - Video Solutions

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.