DEV Community

loading...

Day-12 Largest number at least twice of others

mridubhatnagar profile image Mridu Bhatnagar ・1 min read

This problem statement is a part of Leetcode's card Arrays and Strings under the sub-heading Introduction to Arrays.

Problem Statement

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 much as every other number in the array.

If it is, return the index of the largest element, otherwise, return -1.

Example 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 is more than 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 isn't at least as big as twice the value of 3, so we return -1.

Note:

  1. nums will have a length in the range [1, 50].
  2. Every nums[i] will be an integer in the range [0, 99].
Solution Approach
  1. Find the largest element and index of the largest element from the array.
  2. Iterate over the array and check if twice the value of all other elements is less than the largest_element. If this condition is False return -1 else return the index of the largest element.
class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        largest_element = max(nums)
        result = nums.index(largest_element)
        for index, value in enumerate(nums):
            if (value != largest_element) and (largest_element < 2*value):
                result = -1

        return result
Learnings
  1. Time complexity of the solution is 0(n)
  2. Space complexity is 0(1)

Discussion

pic
Editor guide