Leetcode problem: 747. Largest Number At Least Twice of Others

Description: 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.

Solution:

class Solution {
    public int dominantIndex(int[] nums) {
        int len = nums.length;
        int max = nums[0];
        int index = 0;

        for(int i=1;i<len;i++){
            if(nums[i]>max){
                max= nums[i];
                index = i;
            }
        }

        for(int i=0;i<len;i++){
            if(max != nums[i]){
            if(nums[i]*2>max) return -1;
            }
        }
        return index;
    }
}

Approach:

Identify the maximum element

To determine if one number is “dominant,” first we need to know which number is the largest.
Loop through the array, keep track of:
- max → the current largest value
- index → the index of that largest value

Check the “twice as large” condition

After finding the maximum element, we need to check all other elements to see if the max is at least twice each of them.
For every element nums[i] that is not the max:
- If nums[i] * 2 > max, then the max is not dominant, so return -1.

Return the result

If the max passes the check for all other elements, return its index.

Related posts: