algoadvance

Leetcode 747. Largest Number At Least Twice of Others

Problem Statement

You are given an integer array nums where the largest integer is at least twice as large as every other number in the array. If this condition is true, return the index of the largest number, otherwise, return -1.

Example

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 at least twice as large as x. The index of value 6 is 1.

Example 2:

Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least twice as large as 3, so we return -1.

Clarifying Questions

1. Q: Can the array be empty or contain only one element? A: The problem statement does not specify these cases but we can assume that if the array has only one element, that element is trivially twice as large as itself.

2. Q: Can the array contain negative numbers? A: Yes, but since the problem specifies “twice as large,” negative numbers would make that check straightforward based on their absolute values for logical comparisons.

3. Q: What is the range of the numbers in the array? A: Typically, LeetCode problems assume that the numbers fit within the constraints of a 32-bit signed integer.

Code

public class Solution {
    public int dominantIndex(int[] nums) {
        if (nums.length == 0) return -1;
        if (nums.length == 1) return 0;
        
        int maxIndex = 0;
        int secondMax = Integer.MIN_VALUE;

        // Find the largest element and its index
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[maxIndex]) {
                secondMax = nums[maxIndex];
                maxIndex = i;
            } else if (nums[i] > secondMax) {
                secondMax = nums[i];
            }
        }

        // Check if the largest number is at least twice as large as the second largest
        if (nums[maxIndex] >= 2 * secondMax) {
            return maxIndex;
        } else {
            return -1;
        }
    }
}

Strategy

1. Initialization:
   • We handle edge cases where the array is empty or has only one element.
2. Finding the Largest Element:
   • We initialize maxIndex to 0 and secondMax to the smallest possible value.
   • Traverse through the array to find the maximum element’s index and track the second largest element.
3. Checking the Condition:
   • After identifying the largest element and the second largest element, check if the largest element is at least twice as large as the second largest element.
   • If it is, return the index of the largest element; otherwise, return -1.

Time Complexity

• Time Complexity: O(n) where n is the length of the array. We iterate through the array once to find the largest and second largest elements.
• Space Complexity: O(1) because we use a constant amount of additional space regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?