Scale Engineer

Largest Number At Least Twice of Others

Easy
#0701Time: O(N log N) - Dominated by the sorting algorithm. Finding the index in the original array takes an additional O(N) time.Space: O(N) - Required to store a copy of the array to preserve the original indices after sorting.
Algorithms
Sorting
Data structures
Array

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves sorting a copy of the array to easily identify the largest and second-largest elements. The comparison is then straightforward, but it requires finding the original index of the largest element.

Algorithm

  • If the array has only one element, the condition is trivially met, so we return index 0.
  • Create a copy of the input array nums to preserve the original indices.
  • Sort the copied array in ascending order.
  • The largest element is sorted_nums[n-1] and the second largest is sorted_nums[n-2].
  • Check if sorted_nums[n-1] >= 2 * sorted_nums[n-2]. If not, the condition fails, so return -1.
  • If the condition holds, we need the original index of the largest element. Iterate through the original nums array to find the first occurrence of sorted_nums[n-1] and return its index.

Walkthrough

The core idea is that after sorting, the largest element will be the last element in the array, and the second-largest will be the second to last. This simplifies finding these two key values. Since sorting modifies the array, we must work on a copy to preserve the original indices, which are needed for the final result.

import java.util.Arrays; class Solution {    public int dominantIndex(int[] nums) {        // Constraints guarantee nums.length >= 2        int[] numsCopy = Arrays.copyOf(nums, nums.length);        Arrays.sort(numsCopy);                int maxVal = numsCopy[nums.length - 1];        int secondMaxVal = numsCopy[nums.length - 2];                if (maxVal < 2 * secondMaxVal) {            return -1;        }                // Find the original index of the max value        for (int i = 0; i < nums.length; i++) {            if (nums[i] == maxVal) {                return i;            }        }                return -1; // Should not be reached due to problem constraints    }}

Complexity

Time

O(N log N) - Dominated by the sorting algorithm. Finding the index in the original array takes an additional O(N) time.

Space

O(N) - Required to store a copy of the array to preserve the original indices after sorting.

Trade-offs

Pros

  • The logic to find the largest and second-largest elements becomes very simple after sorting.

Cons

  • Less efficient in terms of time complexity compared to linear scan approaches.

  • Requires extra space for the array copy.

Solutions

class Solution {public  int dominantIndex(int[] nums) {    int n = nums.length;    int k = 0;    for (int i = 0; i < n; ++i) {      if (nums[k] < nums[i]) {        k = i;      }    }    for (int i = 0; i < n; ++i) {      if (k != i && nums[k] < nums[i] * 2) {        return -1;      }    }    return k;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem