We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Number At Least Twice of Others

Number: 748

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an integer array where the largest integer is unique, determine whether this largest element is at least twice as much as every other number in the array. If it is, return the index of the largest element; otherwise, return -1.

Key Insights

  • Identify the maximum element and its unique index in the array.
  • Verify that for every other element, twice its value does not exceed the maximum element.
  • A simple two-pass solution is sufficient: one to find the maximum and another to check the condition.
  • Edge cases are minimal due to given constraints and uniqueness of the maximum element.

Space and Time Complexity

Time Complexity: O(n) - We traverse the array a constant number of times. Space Complexity: O(1) - We use a constant amount of additional space.

Solution

The solution involves two main steps. First, traverse the array to find the maximum value and its corresponding index. Then, iterate through the array again to ensure that the maximum element is at least twice as large as every other element. We use basic iteration and conditional checks without extra data structures, providing an efficient and straightforward approach.

Code Solutions

# Python solution to determine the dominant index
def dominantIndex(nums):
    # Step 1: Identify the maximum value and its index
    max_val = max(nums)
    max_index = nums.index(max_val)
    
    # Step 2: Verify that the maximum is at least twice every other element
    for num in nums:
        if num != max_val and max_val < 2 * num:
            return -1
    return max_index

# Example usage:
print(dominantIndex([3, 6, 1, 0]))  # Expected output: 1
← Back to All Questions