747. Largest Number At Least Twice of Others


Problem Description

In this problem, you are given an array of integers, nums, with the assurance that the largest integer is unique, which means it does not appear more than once in the array. The task is to check whether this largest number is at least twice as large as every other number present in the array. If such a condition is met, your function should return the index of this largest number. However, if there's no number in the array that is twice as large as every other number, or the largest number itself is not twice as big as at least one other number in the array, then the function should return -1.

Intuition

The intuition for solving this problem stems from the requirement that we must find the largest number and then compare it to all others. We can do this efficiently by tracking two numbers as we iterate through the array: the largest number so far, and the second-largest number so far. We don't actually need to check the largest number against all other numbers if we maintain the second-largest; it's enough to check if it's at least twice the second-largest.

The solution works as follows:

  • Initialize two variables, mx and mid, to track the largest and second-largest values, respectively, and another variable, ans, to store the index of the largest number. Start all of them at 0, with ans initialized to -1.
  • Iterate through the array with their index and value (i, v).
  • For each number v, check if it is greater than the current largest number mx. If it is, update mid to mx (since the largest will now become the second-largest), update mx to v, and store the current index i in ans.
  • If v is not greater than mx but is greater than the second-largest number mid, then update mid to v.
  • After iterating through the entire array, we need to check if our found largest number mx is at least twice as big as the second-largest mid. If it is, we return the stored index ans; otherwise, we return -1.

This approach ensures that we only need a single pass through the array, achieving the goal using O(n) time complexity without any extra space complexity.

Learn more about Sorting patterns.

Solution Approach

The solution approach employs a linear scan algorithm, which is a simple yet powerful technique used in problems that require comparison or finding elements with certain properties in an array or list. Specifically, the algorithm keeps track of the maximum (mx) and the second maximum (mid) values while scanning through the array once.

Let's take a more detailed look at the data structures and patterns used in the implementation:

  • Variables for Tracking: We use two variables mx and mid to keep track of the largest and the second-largest values as we iterate over the array. An additional variable ans is used to note the index of the largest number.
  • Iteration: We use a for loop to iterate through the array elements enumerated with their indices using the built-in enumerate function in Python. The enumerate function provides a tuple for each element in the list, containing the index (i) and the value (v).
  • Conditional Logic: Inside the loop, we use conditional statements (if/elif) to compare the current element v with our tracked maximum (mx) and second maximum (mid). This helps us in updating these variables without having to compare mx with every other number in the array.
  • Updating Values: If we find a new maximum value, we update mid to the old mx before updating mx to the new maximum. If the current value is not larger than mx but is larger than mid, we simply update mid.
  • Final Check and Return: After completing the iteration, the final check outside the loop determines whether mx is at least twice as large as mid. If the condition is satisfied, the index stored in ans is returned, and if not, -1 is returned as specified by the problem statement.

Here is how the implementation translates the solution approach:

  1. Initialization: We set mx = mid = 0 and ans = -1. These are our starting conditions.
  2. Iteration over nums: Using enumerate(nums), we loop over each i, v pair in the array.
  3. New Maximum Condition: If v > mx, we first set mid = mx, then mx = v, followed by ans = i.
    • mid = mx ensures we remember the previous largest value.
    • mx = v sets the new largest value.
    • ans = i captures the index of the new largest value.
  4. New Second Maximum Condition: If v is not the new maximum but is greater than the current mid, we set mid = v. It's important because we only care about the second-largest value for the comparison with the largest value.
  5. Return Condition: Perform the final comparison using return ans if mx >= 2 * mid else -1. If mx is twice as large or larger than mid, we return ans since mx meets the criteria; otherwise, we return -1.

The simplicity of this algorithm lies in avoiding unnecessary operations and comparisons, making efficient use of a single-pass scan to acquire our solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have the following array of integers:

1nums = [3, 6, 1, 0]

We want to find out if the largest number in nums is twice as large as all the other numbers, and if so, return its index.

Following the linear scan algorithm described in the solution approach:

  1. Initialization: We start with mx = mid = 0 and ans = -1. This means currently, our largest and second-largest numbers are both set to the first element of the array, and we have no valid answer yet.

  2. Iteration over nums:

    • First iteration (i=0, v=3): Since this is the first element, mx and mid are already set to 3, and ans is set to 0.
    • Second iteration (i=1, v=6): Now v is greater than mx, we update mid to the current mx (3), update mx to 6, and set ans to 1.
    • Third iteration (i=2, v=1): Here, v is neither greater than mx (6) nor greater than mid (3), so no changes are made.
    • Fourth iteration (i=3, v=0): Similarly, v is not greater than mx (6) or mid (3), so no changes are made here as well.
  3. New Maximum and Second Maximum Conditions: Have been applied during the iteration. After the loop, our current maximum mx is 6, our second maximum mid is 3, and ans indicating the largest number's index is 1.

  4. Return Condition: We finally check if mx (6) is at least twice as large as mid (3). Since it is not (6 is not ≥ 2*3), we return -1.

We conclude the iteration, and since the largest number (6) is not at least twice as large as the second-largest number in the array, the function would return -1. Our implementation correctly follows the solution approach and therefore, validates its effectiveness.

Solution Implementation

1from typing import List
2
3class Solution:
4    def dominantIndex(self, nums: List[int]) -> int:
5        # Initialize maximum and second maximum values and the index of the maximum value
6        max_value = second_max = -1
7        max_index = -1
8
9        # Iterate through the numbers with their indices
10        for index, value in enumerate(nums):
11            # If the current value is greater than the maximum value found so far
12            if value > max_value:
13                # Assign the old max_value to second_max before updating max_value
14                second_max, max_value = max_value, value
15                # Record the index of the new maximum value
16                max_index = index
17            # Else if the value is not greater than max_value but is greater than second_max
18            elif value > second_max:
19                # Update the second maximum value
20                second_max = value
21
22        # Check if the maximum value is at least twice as much as the second maximum
23        # If so, return the index of the maximum value. Otherwise, return -1.
24        return max_index if max_value >= 2 * second_max else -1
25
1class Solution {
2    public int dominantIndex(int[] nums) {
3        // Initialize two variables to store the largest and second largest numbers
4        int max = Integer.MIN_VALUE;
5        int secondMax = Integer.MIN_VALUE;
6      
7        // The index of the largest number will be stored in this variable
8        int indexOfMax = -1;
9      
10        // Iterate through the array to find the largest and second largest numbers
11        for (int i = 0; i < nums.length; i++) {
12            if (nums[i] > max) {
13                // If the current number is greater than the largest found so far,
14                // update secondMax to max, and max to the current number
15                secondMax = max;
16                max = nums[i];
17              
18                // Update the index of the largest number
19                indexOfMax = i;
20            } else if (nums[i] > secondMax) {
21                // If the current number is only greater than secondMax,
22                // update the secondMax to the current number
23                secondMax = nums[i];
24            }
25        }
26      
27        // Check if the largest number is at least twice as much as the second largest number
28        // If so, return the index of the largest number, otherwise return -1
29        return max >= secondMax * 2 ? indexOfMax : -1;
30    }
31}
32
1#include <vector> // Required for using the vector container.
2
3class Solution {
4public:
5    // Function to find whether there exists a dominant index.
6    // The dominant index is an index where the element is at least twice as
7    // large as every other element in the array. If such an element exists, return its index.
8    // Otherwise, return -1.
9    int dominantIndex(vector<int>& nums) {
10        int maxElement = 0; // Holds the value of the largest element.
11        int secondMaxElement = 0; // Holds the value of the second largest element.
12        int dominantIndex = 0;  // Initialize the dominant index to 0.
13      
14        // Iterate over the array to find the largest and second largest elements.
15        for (int i = 0; i < nums.size(); ++i) {
16            // If current element is greater than the largest element found so far
17            if (nums[i] > maxElement) {
18                secondMaxElement = maxElement; // Update the second max to be the previous max
19                maxElement = nums[i]; // Update the max to be the current element
20                dominantIndex = i; // Update the index of the largest element
21            } 
22            // If current element is not greater than max but is greater than the second max
23            else if (nums[i] > secondMaxElement) {
24                secondMaxElement = nums[i]; // Update the second max to be the current element
25            }
26        }
27      
28        // If the largest element is at least twice as big as the second largest element,
29        // return the index of the largest element, otherwise return -1.
30        return maxElement >= secondMaxElement * 2 ? dominantIndex : -1;
31    }
32};
33
1/**
2 * This TypeScript function finds the index of the dominant element in the array.
3 * An element is dominant if it is greater than twice all other elements.
4 * @param {number[]} nums - An array of numbers.
5 * @returns {number} - The index of the dominant element or -1 if no such element exists.
6 */
7const dominantIndex = (nums: number[]): number => {
8    let largest: number = 0;
9    let secondLargest: number = 0;
10    let dominantIndex: number = 0;
11
12    // Loop through all elements in the nums array
13    for (let i = 0; i < nums.length; ++i) {
14        if (nums[i] > largest) { // If current element is larger than the largest element found so far
15            secondLargest = largest; // Update the second largest element
16            largest = nums[i]; // Update the largest element
17            dominantIndex = i; // Update the index of the dominant element
18        } else if (nums[i] > secondLargest) { // If current element is larger than the second largest element
19            secondLargest = nums[i]; // Update the second largest element
20        }
21    }
22
23    // If the largest element is at least twice as large as the second largest element, return its index.
24    // Otherwise, return -1 indicating there is no dominant element.
25    return largest >= secondLargest * 2 ? dominantIndex : -1;
26};
27
28// Example usage of the function
29const testArray: number[] = [3, 6, 1, 0];
30const index: number = dominantIndex(testArray);
31console.log('The dominant index is:', index); // Outputs the index or -1 if no dominant element is found
32

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the number of elements in the input list nums. This is because the code consists of a single for loop that iterates through all the elements of the list exactly once to find the largest and the second largest elements.

During each iteration, the code performs a constant-time operation to compare the current value v to the current maximum mx and the second maximum mid. Assignments and comparisons are basic operations that take constant time. Thus, the for loop constitutes the major time-consuming part of the algorithm.

Space Complexity

The space complexity of the code is O(1), which means it uses constant additional space. The only extra variables used in the function are mx, mid, and ans, and these do not depend on the size of the input list. All other operations are done in-place and do not require allocation of additional storage that scales with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄