Largest Number At Least Twice of Others

• LeetCode: 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.

• 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].

• Examples:

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.

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.

• Analysis:

Check the maximal is divided by the second maximal > 1.

• Code - Java:

class Solution {
    public int dominantIndex(int[] nums) {
        int len = nums.length;
        int max_value = Integer.MIN_VALUE;
        int sec_max_value = Integer.MIN_VALUE;
        int pos = -1;
        for (int i = 0; i < len; i++) {
            if (max_value < nums[i]) {
                sec_max_value = max_value;
                max_value = nums[i];
                pos = i;
            } else if (sec_max_value < nums[i]) {
                sec_max_value = nums[i];
            }
        }
        if (max_value == Integer.MIN_VALUE) {
            return -1;
        }
        if (sec_max_value == Integer.MIN_VALUE) {
            return 0;
        }
        if (sec_max_value == 0) {
            return pos;
        }
        if (max_value / sec_max_value > 1) {
            return pos;
        }
        return -1;
    }
}

• Code - C++:

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int size = nums.size();
        int max_value = INT_MIN;
        int sec_max_value = INT_MIN;
        int pos = -1;
        for (int i = 0; i < size; i++) {
            if (max_value < nums[i]) {
                sec_max_value = max_value;
                max_value = nums[i];
                pos = i;
            } else if (sec_max_value < nums[i]) {
                sec_max_value = nums[i];
            }
        }
        if (max_value == INT_MIN) {
            return -1;
        }
        if (sec_max_value == INT_MIN) {
            return 0;
        }
        if (sec_max_value == 0) {
            return pos;
        }
        if (max_value / sec_max_value > 1) {
            return pos;
        }
        return -1;
    }
};

• Code - Python:

class Solution(object):
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        numLen = len(nums)
        minInt = (-1) * (2 ** 31)
        max_value = minInt
        sec_max_value = minInt
        pos = -1
        for i in range(numLen):
            if max_value < nums[i]:
                sec_max_value = max_value
                max_value = nums[i]
                pos = i
            elif sec_max_value < nums[i]:
                sec_max_value = nums[i]
        if max_value == minInt:
            return -1
        if sec_max_value == minInt:
            return 0
        if sec_max_value == 0:
            return pos
        if max_value / sec_max_value > 1:
            return pos
        return -1

• Time Complexity: O(N), N is the length of array nums

• Space Complexity: O(1)