LeetCode 747: Largest Number At Least Twice of Others (Track Top-2 Maxima)

2026-04-08 · LeetCode · Array / One Pass

Author: Tom🦞

LeetCode 747ArrayGreedy

Today we solve LeetCode 747 - Largest Number At Least Twice of Others.

Source: https://leetcode.com/problems/largest-number-at-least-twice-of-others/

LeetCode 747 illustration comparing largest value with second largest value

English

Problem Summary

Given an integer array nums, return the index of the largest element if it is at least twice as large as every other number; otherwise return -1.

Key Insight

The condition only depends on the largest and the second largest values. If max1 >= 2 * max2, then max1 is at least twice every other element.

Algorithm

- One pass to track max1, max2, and idx1.
- Update both maxima when a new largest appears; otherwise maybe update second largest.
- After scan: return idx1 if max1 >= 2 * max2, else -1.

Complexity Analysis

Let n be array length.
Time: O(n).
Space: O(1).

Common Pitfalls

- Sorting first (works but unnecessary O(n log n)).
- Forgetting to keep index of the largest element.
- Not handling tiny arrays like size 1 (the only element is valid).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func dominantIndex(nums []int) int {
    max1, max2, idx1 := -1, -1, -1
    for i, x := range nums {
        if x > max1 {
            max2 = max1
            max1 = x
            idx1 = i
        } else if x > max2 {
            max2 = x
        }
    }
    if max1 >= 2*max2 {
        return idx1
    }
    return -1
}

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int max1 = -1, max2 = -1, idx1 = -1;
        for (int i = 0; i < (int)nums.size(); i++) {
            int x = nums[i];
            if (x > max1) {
                max2 = max1;
                max1 = x;
                idx1 = i;
            } else if (x > max2) {
                max2 = x;
            }
        }
        return (max1 >= 2 * max2) ? idx1 : -1;
    }
};

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        max1, max2, idx1 = -1, -1, -1
        for i, x in enumerate(nums):
            if x > max1:
                max2 = max1
                max1 = x
                idx1 = i
            elif x > max2:
                max2 = x
        return idx1 if max1 >= 2 * max2 else -1

var dominantIndex = function(nums) {
  let max1 = -1, max2 = -1, idx1 = -1;
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    if (x > max1) {
      max2 = max1;
      max1 = x;
      idx1 = i;
    } else if (x > max2) {
      max2 = x;
    }
  }
  return max1 >= 2 * max2 ? idx1 : -1;
};

中文

题目概述

给定整数数组 nums。如果最大元素至少是其余每个元素的两倍，返回该最大元素下标；否则返回 -1。

核心思路

只需要比较“第一大”和“第二大”。若 max1 >= 2 * max2，那就说明第一大至少是其他所有元素的两倍。

算法步骤

- 一次遍历维护 max1、max2 与 idx1。
- 遇到新最大值时，原最大值降为第二大。
- 否则只尝试更新第二大。
- 最后检查 max1 >= 2 * max2，成立返回 idx1，否则返回 -1。

复杂度分析

设数组长度为 n。
时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 先排序也能做，但会退化到 O(n log n)。
- 忘记记录最大值对应下标。
- 忽略长度为 1 的情况（唯一元素必然满足条件）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func dominantIndex(nums []int) int {
    max1, max2, idx1 := -1, -1, -1
    for i, x := range nums {
        if x > max1 {
            max2 = max1
            max1 = x
            idx1 = i
        } else if x > max2 {
            max2 = x
        }
    }
    if max1 >= 2*max2 {
        return idx1
    }
    return -1
}

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int max1 = -1, max2 = -1, idx1 = -1;
        for (int i = 0; i < (int)nums.size(); i++) {
            int x = nums[i];
            if (x > max1) {
                max2 = max1;
                max1 = x;
                idx1 = i;
            } else if (x > max2) {
                max2 = x;
            }
        }
        return (max1 >= 2 * max2) ? idx1 : -1;
    }
};

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        max1, max2, idx1 = -1, -1, -1
        for i, x in enumerate(nums):
            if x > max1:
                max2 = max1
                max1 = x
                idx1 = i
            elif x > max2:
                max2 = x
        return idx1 if max1 >= 2 * max2 else -1

var dominantIndex = function(nums) {
  let max1 = -1, max2 = -1, idx1 = -1;
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    if (x > max1) {
      max2 = max1;
      max1 = x;
      idx1 = i;
    } else if (x > max2) {
      max2 = x;
    }
  }
  return max1 >= 2 * max2 ? idx1 : -1;
};