algoadvance

You are given an integer array nums where the largest integer is at least twice as much as every other number in the array. If the largest integer is at least twice as much as every other number in the array, return the index of the largest integer, otherwise, return -1.

Examples

  1. Input: nums = [3, 6, 1, 0] Output: 1 Explanation: 6 is the largest integer and for every other number in the array x, 6 >= 2 * x.

  2. Input: nums = [1, 2, 3, 4] Output: -1 Explanation: 4 is the largest number, but 4 is not at least twice as much as every other number in the array.

  3. Input: nums = [1] Output: 0 Explanation: The largest number is 1, and since there is no other number in the array, it meets the condition of being at least twice as much as every other number.

Clarifying Questions

  1. What should we return if the list is empty?
    • We can assume the input array will have at least one element.
  2. Is the input list always guaranteed to be composed of integers?
    • Yes.
  3. Will the input array nums always contain at least one element?
    • Yes, by the problem definition.

Strategy

  1. Find the largest number in the array and its index.
  2. Iterate through the array to check if this largest number is at least twice as much as every other number.
  3. If any number violates the condition, return -1.
  4. If the condition holds for all numbers, return the index of the largest number.

Code

def dominantIndex(nums):
    if not nums:  # Check if the input array is empty
        return -1
    
    max_index = 0
    max_value = nums[0]
    
    # Find the largest number and its index
    for i in range(1, len(nums)):
        if nums[i] > max_value:
            max_value = nums[i]
            max_index = i
    
    # Check if the largest number is at least twice as much as other numbers
    for i in range(len(nums)):
        if i != max_index and max_value < 2 * nums[i]:
            return -1
    
    return max_index

# Test cases to validate the solution
print(dominantIndex([3, 6, 1, 0]))  # Output: 1
print(dominantIndex([1, 2, 3, 4]))  # Output: -1
print(dominantIndex([1]))           # Output: 0
print(dominantIndex([0, 0, 3, 2]))  # Output: 2

Time Complexity

Overall, the time complexity of the solution is O(n).

Try our interview co-pilot at AlgoAdvance.com