Problem 47 - Largest Number At Least Twice of Others

Explore our archive for previous posts.

Problem 46 - Reverse Linked List

Problem 45 - Middle of the Linked List

Problem 44 - Minimum Depth of Binary Tree

Question

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:

Input: nums = [3,6,1,0]
Output: 1
Explanation: 6 is the largest integer.
For every other number in the array x, 6 is at least 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 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.

Approach

Here's a high-level approach to solving this problem:

1. Find the Maximum and Second Maximum:

   • Iterate through the array to find the maximum element (maxNum) and keep track of its index.

   • Simultaneously, find the second maximum element (secondMaxNum).

2. Check the Condition:

   • Check if maxNum is at least twice as much as secondMaxNum.

   • If it is, return the index of maxNum; otherwise, return -1.

Solution

Solve it here

public class LargestNumberTwice {

    public int dominantIndex(int[] nums) {
        // Check if the array has fewer than two elements
        if (nums == null || nums.length < 2) {
            return 0;
        }

        // Initialize variables to keep track of the maximum and second maximum
        int maxIndex = 0;
        int maxNum = nums[0];
        int secondMaxNum = Integer.MIN_VALUE;

        // Iterate through the array to find the maximum and second maximum
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > maxNum) {
                // Update secondMaxNum and maxNum if nums[i] is greater than maxNum
                secondMaxNum = maxNum;
                maxNum = nums[i];
                maxIndex = i; // Update the index of the maximum element
            } else if (nums[i] > secondMaxNum) {
                // Update secondMaxNum if nums[i] is greater than the current secondMaxNum
                secondMaxNum = nums[i];
            }
        }

        // Check the condition for the largest number being at least twice of others
        return (maxNum >= 2 * secondMaxNum) ? maxIndex : -1;
    }
}

Time and space complexity

Time Complexity: The algorithm iterates through the array once, so the time complexity is O(n), where n is the length of the array.

Space Complexity: The algorithm uses a constant amount of extra space, regardless of the input size. Therefore, the space complexity is O(1).

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Nailing Coding Interviews: Mindset Matters

Ethical Dilemmas in Coding Interviews: Should You Reveal Prior Knowledge?