#747

Easy

LeetCode Problem Workspace

Largest Number At Least Twice of Others

Determine if the largest number in the array is at least twice as large as every other element, and return its index or -1.

array sorting

Problem Statement

You are given an integer array nums, where the largest integer is unique. Your task is to determine if the largest element in the array is at least twice as large as every other number. If it is, return the index of the largest element. Otherwise, return -1.

For example, if nums = [3, 6, 1, 0], the largest element is 6, and for every other element, 6 is at least twice as large. Hence, the correct output is 1, the index of 6. If the largest element isn't twice as large as the others, return -1.

Examples

Example 1

Input: nums = [3,6,1,0]

Output: 1

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

4 is less than twice the value of 3, so we return -1.

Constraints

2 <= nums.length <= 50
0 <= nums[i] <= 100
The largest element in nums is unique.

Solution Approach

Find the Largest Element

Scan through the array to find the largest element and track its index. This gives us the candidate for the answer, which we need to verify against the rest of the array.

Verify the Twice Condition

After identifying the largest element, iterate through the array again to check if it is at least twice the size of every other element. If any element violates this condition, return -1.

Return the Index

If the largest element satisfies the twice condition, return its index. Otherwise, return -1 to indicate the condition was not met.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used to identify the largest element and check the twice condition. If we scan the array twice, the time complexity is O(n), where n is the number of elements in the array. The space complexity is O(1), as we only use a few variables to store the largest element and its index.

What Interviewers Usually Probe

Ability to identify the largest element in a single scan of the array.
Understanding of how to compare array elements efficiently in two passes.
Attention to detail in ensuring that all elements are checked against the largest element.

Common Pitfalls or Variants

Common pitfalls

Not verifying that the largest element is at least twice as large as all others, leading to incorrect results.
Overcomplicating the solution with unnecessary steps or additional data structures.
Misunderstanding the problem and incorrectly handling cases where the largest element doesn’t meet the twice condition.

Follow-up variants

Consider cases where the array contains only two elements.
Handle arrays with all elements being the same, except for the largest one.
What if the array contains very large or very small numbers? Ensure that edge cases are considered.

FAQ

What is the pattern for solving 'Largest Number At Least Twice of Others'?

The pattern involves scanning the array twice: first to find the largest element and its index, and second to verify if it's at least twice as large as every other element.

How should I optimize the solution for this problem?

The solution can be optimized by scanning the array twice to find the largest element and check the twice condition, keeping the time complexity at O(n).

Can the array length affect the performance of my solution?

Yes, as the array length increases, the number of operations required to find and compare the largest element will increase linearly, making the solution's performance dependent on the array's size.

What happens if the array has duplicate values?

The problem guarantees that the largest element is unique, so duplicates won’t affect the solution. The uniqueness condition simplifies the problem.

Is sorting necessary for this problem?

Sorting is not necessary. A simple two-pass approach to find the largest element and verify its twice condition is sufficient and more efficient.

terminal

Solution

Solution 1: 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$.

1

2

3

4

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        x, y = nlargest(2, nums)
        return nums.index(x) if x >= 2 * y else -1

Continue Practicing

#757 set intersection size at least two #768 max chunks to make sorted ii #769 max chunks to make sorted