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

• Find Pivot Index
• Triplets with sum between given range
• Rotate Array
• Median of two sorted arrays
• Longest common prefix

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