Largest Number At Least Twice of Others - Problem

Array Sorting Easy

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.

Input & Output

Example 1 — Valid Case

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

› Output: 1

💡 Note: The largest element is 6 at index 1. It's at least twice every other element: 6 ≥ 2×3, 6 ≥ 2×1, 6 ≥ 2×0. So return index 1.

Example 2 — Invalid Case

$ Input: nums = [1,2,3,4]

› Output: -1

💡 Note: The largest element is 4 at index 3. However, 4 < 2×3 = 6, so it's not at least twice the element 3. Return -1.

Example 3 — Edge Case

$ Input: nums = [1]

› Output: 0

💡 Note: Single element array - the largest (and only) element is trivially at least twice every other element (there are none). Return index 0.

Constraints

1 ≤ nums.length ≤ 50
0 ≤ nums[i] ≤ 100
The largest element in nums is unique

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we only need to compare the largest element with the second largest - if the max is at least twice the second max, it's at least twice every other element. Best approach finds both values in one pass. Time: O(n), Space: O(1)

Common Approaches

✓ Brute Force - Find Max Then Check All

⏱️ Time: O(n) Space: O(1)

First pass finds the maximum value and its index. Second pass iterates through all other elements to verify the maximum is at least twice each one.

One Pass - Track Max and Second Max

⏱️ Time: O(n) Space: O(1)

Instead of checking against every element, we only need to find the two largest elements. If the largest is at least twice the second largest, it's at least twice every other element.

Brute Force - Find Max Then Check All — Algorithm Steps

Step 1: Find maximum element and its index
Step 2: Check if max ≥ 2 × every other element

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Maximum

Scan array to find max value and index

Check All Elements

Verify max ≥ 2 × each other element

Result

Return index if valid, -1 otherwise

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    // Find maximum element and its index
    int maxVal = nums[0];
    int maxIdx = 0;
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
            maxIdx = i;
        }
    }
    
    // Check if max is at least twice every other element
    for (int i = 0; i < numsSize; i++) {
        if (i != maxIdx && maxVal < 2 * nums[i]) {
            return -1;
        }
    }
    
    return maxIdx;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array manually
    int nums[1000];
    int count = 0;
    char* ptr = line + 1; // Skip opening bracket
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through array: O(n) to find max + O(n) to check all elements

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables to track max value and index

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Largest Number At Least Twice of Others - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Find Max Then Check All — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler