Largest Number At Least Twice of Others - Practice Coding Problems

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

Understanding the Visualization

Input

Array [3,6,1,0] with unique largest element

Process

Check if max element ≥ 2 × every other element

Output

Return index of max if valid, -1 otherwise

Key Takeaway

🎯 Key Insight: Only need to compare largest with second largest - if max ≥ 2×second_max, then max ≥ 2×everything else

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

Approach	Time	Space	Notes
✓ One Pass - Track Max and Second Max	O(n)	O(1)	Find the largest and second largest elements in one pass, then compare
Brute Force - Find Max Then Check All	O(n)	O(1)	Find the maximum element and its index, then check if it's at least twice every other element

One Pass - Track Max and Second Max — Algorithm Steps

Step 1: Scan array once to find max and second max
Step 2: Check if max ≥ 2 × second_max

Visualization

Tap to expand

Step-by-Step Walkthrough

One Pass Scan

Track max=6 (index 1) and second_max=3

Single Comparison

Check if 6 ≥ 2×3 = 6

Result

Return index 1 since condition is satisfied

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int maxVal = -1, secondMax = -1;
    int maxIdx = 0;
    
    // Find max and second max in one pass
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > maxVal) {
            secondMax = maxVal;
            maxVal = nums[i];
            maxIdx = i;
        } else if (nums[i] > secondMax) {
            secondMax = nums[i];
        }
    }
    
    // Check if max is at least twice the second max
    return maxVal >= 2 * secondMax ? maxIdx : -1;
}

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)

Single pass through array to find max and second max

✓ Linear Growth

Space Complexity

O(1)

Only uses variables to track max, second max, and their indices

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

One Pass - Track Max and Second Max — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler