747. Largest Number At Least Twice of Others - Solution

Q: Is Largest Number At Least Twice of Others easy or hard?

Largest Number At Least Twice of Others is classified as an Easy problem. It mainly tests basic array traversal, tracking maximum values, and understanding how to reduce comparisons to constant space.

Q: Largest Number At Least Twice of Others Python/Java solution

In Python or Java, iterate through the array while keeping variables for the largest value, second-largest value, and the index of the largest element. After processing all numbers, verify that the largest value is at least twice the second-largest before returning the index.

Q: How to solve Largest Number At Least Twice of Others in O(n)?

Iterate through the array and maintain two values: the largest element and the second-largest element. Update them as you scan each number. After the loop, check if max >= 2 * secondMax. If true, return the index of the maximum; otherwise return -1.

The problem

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 <= 50
0 <= nums[i] <= 100
The largest element in nums is 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.

Python

def dominantIndex(nums):
    max_index = 0
    for i in range(1, len(nums)):
        if nums[i] > nums[max_index]:
            max_index = i

    for i in range(len(nums)):
        if i != max_index and nums[max_index] < 2 * nums[i]:
            return -1

    return max_index

print(dominantIndex([3, 6, 1, 0])) # Output: 1

Java

class Solution {
    public int dominantIndex(int[] nums) {
        int maxIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (i != maxIndex && nums[maxIndex] < 2 * nums[i]) {
                return -1;
            }
        }
        return maxIndex;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 6, 1, 0};
        System.out.println(sol.dominantIndex(nums)); // Output: 1
    }
}

C++

#include <vector>
#include <iostream>
using namespace std;

int dominantIndex(vector<int>& nums) {
    int maxIndex = 0;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[maxIndex]) {
            maxIndex = i;
        }
    }

    for (int i = 0; i < nums.size(); i++) {
        if (i != maxIndex && nums[maxIndex] < 2 * nums[i]) {
            return -1;
        }
    }

    return maxIndex;
}

int main() {
    vector<int> nums = {3, 6, 1, 0};
    cout << dominantIndex(nums) << endl; // Output: 1
    return 0;
}

JavaScript

function dominantIndex(nums) {
    let maxIndex = 0;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[maxIndex]) {
            maxIndex = i;
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (i !== maxIndex && nums[maxIndex] < 2 * nums[i]) {
            return -1;
        }
    }

    return maxIndex;
}

console.log(dominantIndex([3, 6, 1, 0])); // Output: 1

#include <stdio.h>

int dominantIndex(int* nums, int numsSize) {
    int maxIndex = 0;
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > nums[maxIndex]) {
            maxIndex = i;
        }
    }

    for (int i = 0; i < numsSize; i++) {
        if (i != maxIndex && nums[maxIndex] < 2 * nums[i]) {
            return -1;
        }
    }

    return maxIndex;
}

int main() {
    int nums[] = {3, 6, 1, 0};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", dominantIndex(nums, size)); // Output: 1
    return 0;
}

using System;

public class Solution {
    public int DominantIndex(int[] nums) {
        int maxIndex = 0;
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

        for (int i = 0; i < nums.Length; i++) {
            if (i != maxIndex && nums[maxIndex] < 2 * nums[i]) {
                return -1;
            }
        }

        return maxIndex;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 6, 1, 0};
        Console.WriteLine(sol.DominantIndex(nums)); // Output: 1
    }
}

The Python function determines the largest number's index, then checks if it is at least twice the size of each other number through two separate loops.

Complexity

Time Complexity: O(n).
Space Complexity: O(1), since we are not using any extra space.

Try this approach in the editor

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.

Python

def dominantIndex(nums):
    max_val = max(nums)
    max_index = nums.index(max_val)
    nums.sort(reverse=True)
    if len(nums) > 1 and max_val >= 2 * nums[1]:
        return max_index
    return -1

print(dominantIndex([3, 6, 1, 0])) # Output: 1

Java

class Solution {
    public int dominantIndex(int[] nums) {
        int maxVal = -1, secondMaxVal = -1, maxIndex = -1;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > maxVal) {
                secondMaxVal = maxVal;
                maxVal = nums[i];
                maxIndex = i;
            } else if (nums[i] > secondMaxVal) {
                secondMaxVal = nums[i];
            }
        }
        return maxVal >= 2 * secondMaxVal ? maxIndex : -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 6, 1, 0};
        System.out.println(sol.dominantIndex(nums)); // Output: 1
    }
}

C++

#include <vector>
#include <iostream>
using namespace std;

int dominantIndex(vector<int>& nums) {
    int maxVal = -1, secondMaxVal = -1, maxIndex = -1;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] > maxVal) {
            secondMaxVal = maxVal;
            maxVal = nums[i];
            maxIndex = i;
        } else if (nums[i] > secondMaxVal) {
            secondMaxVal = nums[i];
        }
    }
    return maxVal >= 2 * secondMaxVal ? maxIndex : -1;
}

int main() {
    vector<int> nums = {3, 6, 1, 0};
    cout << dominantIndex(nums) << endl; // Output: 1
    return 0;
}

JavaScript

function dominantIndex(nums) {
    let maxVal = -1, secondMaxVal = -1, maxIndex = -1;
    for (let i = 0; i < nums.length; ++i) {
        if (nums[i] > maxVal) {
            secondMaxVal = maxVal;
            maxVal = nums[i];
            maxIndex = i;
        } else if (nums[i] > secondMaxVal) {
            secondMaxVal = nums[i];
        }
    }
    return maxVal >= 2 * secondMaxVal ? maxIndex : -1;
}

console.log(dominantIndex([3, 6, 1, 0])); // Output: 1

#include <stdio.h>

int dominantIndex(int* nums, int numsSize) {
    int maxVal = -1, secondMaxVal = -1, maxIndex = -1;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] > maxVal) {
            secondMaxVal = maxVal;
            maxVal = nums[i];
            maxIndex = i;
        } else if (nums[i] > secondMaxVal) {
            secondMaxVal = nums[i];
        }
    }
    return maxVal >= 2 * secondMaxVal ? maxIndex : -1;
}

int main() {
    int nums[] = {3, 6, 1, 0};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", dominantIndex(nums, size)); // Output: 1
    return 0;
}

using System;

public class Solution {
    public int DominantIndex(int[] nums) {
        int maxVal = -1, secondMaxVal = -1, maxIndex = -1;
        for (int i = 0; i < nums.Length; ++i) {
            if (nums[i] > maxVal) {
                secondMaxVal = maxVal;
                maxVal = nums[i];
                maxIndex = i;
            } else if (nums[i] > secondMaxVal) {
                secondMaxVal = nums[i];
            }
        }
        return maxVal >= 2 * secondMaxVal ? maxIndex : -1;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 6, 1, 0};
        Console.WriteLine(sol.DominantIndex(nums)); // Output: 1
    }
}

Python utilizes the 'max' and 'sort' functions to locate and evaluate if the maximum value is at least twice the second maximum within the list, returning the index accordingly.

Complexity

Time Complexity: O(n log n) because of the sorting step.
Space Complexity: O(n), to create an additional sorted copy of the list.

Try this approach in the editor

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).

TypeScript

function dominantIndex(nums: number[]): number {
    let k = 0;
    for (let i = 0; i < nums.length; ++i) {
        if (nums[i] > nums[k]) {
            k = i;
        }
    }
    for (let i = 0; i < nums.length; ++i) {
        if (i !== k && nums[k] < nums[i] * 2) {
            return -1;
        }
    }
    return k;
}

func dominantIndex(nums []int) int {
	k := 0
	for i, x := range nums {
		if nums[k] < x {
			k = i
		}
	}
	for i, x := range nums {
		if k != i && nums[k] < x*2 {
			return -1
		}
	}
	return k
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Single Pass Approach	Time Complexity: O(n). Space Complexity: O(1), since we are not using any extra space.
Two Pass with Early Return	Time Complexity: O(n log n) because of the sorting step. Space Complexity: O(n), to create an additional sorted copy of the list.
Traversal	–

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.

Frequently asked questions

Is Largest Number At Least Twice of Others easy or hard?

Largest Number At Least Twice of Others is classified as an Easy problem. It mainly tests basic array traversal, tracking maximum values, and understanding how to reduce comparisons to constant space.

Largest Number At Least Twice of Others Python/Java solution

In Python or Java, iterate through the array while keeping variables for the largest value, second-largest value, and the index of the largest element. After processing all numbers, verify that the largest value is at least twice the second-largest before returning the index.

How to solve Largest Number At Least Twice of Others in O(n)?

Iterate through the array and maintain two values: the largest element and the second-largest element. Update them as you scan each number. After the loop, check if max >= 2 * secondMax. If true, return the index of the maximum; otherwise return -1.

What is the best approach for Largest Number At Least Twice of Others?

The best approach is a single-pass scan that tracks the largest and second-largest values in the array. After the traversal, check whether the maximum value is at least twice the second maximum. This works in O(n) time and O(1) space and avoids unnecessary additional passes or sorting.

Is Largest Number At Least Twice of Others asked at Google/Amazon/Meta?

This problem is categorized as an easy array problem and commonly appears in coding screens or practice sets used by companies like Amazon and Google. Variants of maximum tracking and dominance checks frequently appear in early interview rounds.

What data structure is used in Largest Number At Least Twice of Others?

The problem uses a simple array traversal. No advanced data structures are required; the algorithm only maintains a few variables to track the maximum and second maximum values while iterating through the array.

What is the time complexity of Largest Number At Least Twice of Others?

The optimal solution runs in O(n) time because the array is scanned once while maintaining the largest and second-largest values. Space complexity is O(1) since only a few variables are used regardless of input size.

Largest Number At Least Twice of Others solution and explanation

The problem

Approach overview

Approach 1: Single Pass Approach

Approach 2: Two Pass with Early Return

Approach 3: Traversal

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Largest Number At Least Twice of Others solution and explanation

The problem

Approach overview

Approach 1: Single Pass Approach

Approach 2: Two Pass with Early Return

Approach 3: Traversal

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems