Largest Number At Least Twice of Others Java Solution - The Coding Shala

Home >> Interview Questions >> Largest Number at least twice of others

Largest Number At Least Twice of Others

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

Largest Number At Least Twice of Others Java Solution

Approach: 

In this problem, we just need to find out the largest and 2nd largest numbers present in the array. Now if the largest element is more than twice of 2nd largest number then it will return its index. 

This can be done in O(N) time and O(1) Space.

Java Code:: 

class Solution {
    public int dominantIndex(int[] nums) {
        int len = nums.length;
        int max = -1, index = -1, second = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                second = max;
                max = nums[i];
                index = i;
            } else if (nums[i] > second)
                second = nums[i];
        }
        if(max >= second*2) return index;
        return -1;
    }
}



Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Anti Diagonals - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala

LeetCode - Bulb Switcher Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Sorting the Sentence LeetCode Solution - The Coding Shala