Largest Number At Least Twice of Others | LeetCode Problem #1 |Python

In the coming series, I will be sharing solutions of some of the leetCode questions in Python. Today we are going to solve Problem #1.

Finding the largest number at least twice of others

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.

Example 3:

Input: nums = [1]
Output: 0
Explanation: 1 is trivially at least twice the value as any other number because there are no other numbers.

Constraints:

1 <= nums.length <= 50

0 <= nums[i] <= 100

The largest element in nums is unique.

Approach for solving this problem:

At first we need to find the largest number in the array. Then we need to check whether that largest number is twice of each number (except largest number itself) in array. If its not twice then we will return -1.

So in order to check whether its twice of other numbers , we need to traverse through the entire array, calculate the twice of each number and compare it with largest number. If at any index the twice of number is not less than largest number (i.e. largest number is not at least the twice of that number) then we will return -1. If we continue through loop and the largest number was at least twice of every other number in array then we will return that largest number.

Solution:

solution

Time Complexity:

Time complexity for this Algorithm is O(n).

References:

LeetCode Problem:

Largest Number At Least Twice of Others - LeetCode

Python Documentation:

3.10.5 Documentation