Leetcode – Largest Number At Least Twice of Others Solution in Python

Spread the love

This article focuses on the problem titled “Largest Number At Least Twice of Others” (problem number 747) and discusses a Python-based solution to it.

Problem Statement

The “Largest Number At Least Twice of Others” problem is described as follows:

In a given integer array nums, there is always exactly one largest element. Find whether the largest element in the array is at least twice as large as every other number in the array. If it is, return the index of the largest element, otherwise return -1.

The problem constraints are:

  • nums will have a length in the range [1, 50].
  • Every nums[i] will be an integer in the range [0, 99].

For example, given the array nums = [3, 6, 1, 0], the largest number is 6. It is twice as large as the other numbers (3 and 1), so we return its index 1.

Approach to Solve the Problem

One of the simplest ways to solve this problem is by identifying the maximum number and the second maximum number in the array. If the maximum number is at least twice as large as the second maximum number and every other number, we return the index of the maximum number; otherwise, we return -1.

To achieve this, we can do a single pass over the array, maintaining two variables, one for the maximum number and one for the second maximum number. We also need to track the index of the maximum number.

Here is the Python code that implements the solution:

class Solution:
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_index = 0
        for i in range(len(nums)):
            if nums[i] > nums[max_index]:
                max_index = i
        for i in range(len(nums)):
            if max_index != i and nums[max_index] < 2 * nums[i]:
                return -1
        return max_index

In this solution, we first find the index of the maximum number. Then we iterate through the array again, and if we find any number that is not the maximum number itself and the maximum number is less than twice this number, we return -1. If no such number is found, we return the index of the maximum number.

Time Complexity

The time complexity of the solution is O(N), where N is the number of elements in the array. This is because we perform two separate passes through the array. The space complexity is O(1), as we are using only a constant amount of space.

Testing the Solution

Let’s test our solution with the example case from Leetcode:

s = Solution()
print(s.dominantIndex([3, 6, 1, 0]))  # Expected output: 1
print(s.dominantIndex([1, 2, 3, 4]))  # Expected output: -1

In the first case, 6 is the largest number and it is at least twice as large as every other number in the array. So we return its index 1. In the second case, 4 is the largest number, but it is not twice as large as the second largest number 3. So we return -1.

Conclusion

The “Largest Number At Least Twice of Others” problem is a simple yet interesting problem that requires careful observation and understanding of the problem statement. With a clear understanding of the problem, we can solve it efficiently using a simple approach.

Remember, complex data structures or algorithms are not always needed to solve problems. Sometimes, a simple for-loop and a few variables are enough. Keep practicing problems of various difficulty levels and types to sharpen your problem-solving skills.

Leave a Reply