747. Largest Number At Least Twice of Others

• python3

Problem

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.

Pseudocode

First solution

1. Find the maximum value and its index.
2. Sort the array.
3. If the last eleement int the array is at least twice as large as the second to last element, return the index of the maximum value. Otherwise, return -1.

Second Solution

1. Set three variables: one for the largest value, one for the second largest value and one for the index of the largest value.
2. Compare the elements to determine these values.
3. Return the index of the largest value or -1 if the condition is not met.

Code

First solution

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        
        index = nums.index(max(nums))
        nums = sorted(nums)
        if nums[-1] >= 2*nums[-2]:
            return index
        
        return -1

Second Solution

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        
        first = -1
        second = -1
        index = -1

        for i in range(len(nums)):
            if nums[i] > first:
                first, second = nums[i], first
                index = i
            elif first> nums[i] > second:
                second = nums[i]
        
        if first >= 2* second:
            return index
        return -1

Result

First solution

• Time Complexity : O(nlogn) because we sort the array by builtin method
• Space Complextiy : O(n) because we use one additional array.

Second Solution

• Time Complexity : O(n) because we traverse the array only once.
• Space Complextiy : O(1) because we don't use any additional array.

Review

• I solved the problem with these solutions on my own! haha