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:

1Input: nums = [3,6,1,0]
2Output: 1
3Explanation: 6 is the largest integer.
4For every other number in the array x, 6 is at least twice as big as x.
5The index of value 6 is 1, so we return 1.

Example 2:

1Input: nums = [1,2,3,4]
2Output: -1
3Explanation: 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

This can be solved using binary search or by using HashSet or HashMap to store previously seen elements.

1. Using Sorting

 1class Solution {
 2    public int dominantIndex(int[] nums) {
 3        int max = Integer.MIN_VALUE;
 4        int index = -1;
 5        for (int i = 0; i < nums.length; i++) {
 6            if (max < nums[i]) {
 7                index = i;
 8                max = nums[i];
 9            }
10        }
11        Arrays.sort(nums);
12        if (max < 2 * nums[nums.length - 2])
13            return -1;
14        else
15            return index;
16    }
17}

2. Using Single Iteration

In this case, starting from the beginning, we will have to track largest number and second largest number. At the end, if largest number is at least 2 times more than second largest number, we return the index of largest number else -1.

 1Initialize max = Integer.MIN_VALUE, secondLargest = Integer.MIN_VALUE
 2int index = -1
 3for i = 0; i < nums.length; i++
 4    if (nums[i] > max)
 5        secondLargest = max
 6        max = nums[i]
 7        index = i
 8    else if (nums[i] > secondLargest)
 9        secondLargest = nums[i]
10return max >= 2 * secondLargest ? index : -1

 1class Solution {
 2    public int dominantIndex2(int[] nums) {
 3        int max = Integer.MIN_VALUE, secondLargest = Integer.MIN_VALUE, index = -1;
 4        for (int i = 0; i < nums.length; i++) {
 5            if (nums[i] > max) {
 6                secondLargest = max;
 7                max = nums[i];
 8                index = i;
 9            } else if (nums[i] > secondLargest) {
10                secondLargest = nums[i];
11            }
12        }
13        return max < 2 * secondLargest ? -1 : index;
14    }
15}