How to solve Largest Number At Least Twice of Others Algorithm in Java

This is my solution to problem 747 on Leet Code.

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.

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

First, we check to see if the array is empty. If so, return -1. This is the first edge case.

return -1 if the array is empty

Next, we check to see if there is only one element in the array. If so, we return 0 because the number at index zero would technically be twice as large as any other element in the array.

return 0 if the array has one element

Now, we need a for loop to traverse through the array while comparing the numbers to each other. We want to find the largest number so we need to make a variable called largestNumber. The default position of largestNumber will be at index 0 so we can compare it to the other integers in the array.

The largest number in the array starts at index 0

We want to compare largestNumber to the other numbers. We also want to make sure that it is at least twice the value of every other number. This means it has to be at least twice the value as the second largest integer in the array. We can store this number in a variable called secondLargestNumber. Let’s make its initial value the smallest number an integer can be. This will be a placeholder until we give it a real value in the for loop. Since the integer array cannot contain a value smaller than Integer.MIN_VALUE, the code works across all edge cases. The default position of secondLargestNumber is index 1 so we can compare it to largestNumber at index 0.

This number will be compared to the largest number, its current value is a placeholder

The objective is to return the index with the largest number. We can track that index in a variable called dominantIndex. The default position of dominantIndex will be index 0.

The dominant index contains the largest number in the array

Now we can start our for loop. Let’s call the variable of the loop currentIndex. The default position of currentIndex will be 1 so we can compare its value to largestNumber.

Traverse through the array starting at index 1

At the start of each loop, we want to save the value of currentIndex so we can compare it to largestNumber. We will store this value in a variable called currentNumber.

The current number is the value at the current index

If the currentNumber is greater than the largestNumber:

1. The largestNumber becomes the secondLargestNumber
2. The currentNumber becomes the largestNumber
3. The currentIndex becomes the dominantIndex

If the current number is greater than the largest number, it then becomes the largest number

If the currentNumber is less than the largestNumber but is greater than the secondLargestNumber, the currentNumber becomes the secondLargestNumber.

If the current number is greater than the second largest number, The current number becomes the second largest number

When the for loop is finished with the array, return the dominant index only if the largestNumber is twice as much as the secondLargestNumber.

Return the dominant index if the largest number is greater than or equal to twice the second largest number

Finally, just return -1 if the largest number in the array is not twice the size as the second largest number.

Otherwise, return -1

Let’s see it in action on the first array example above.

First, we ask if the array is empty. It is not empty so we move on. Then we ask if the array contains one integer. The array contains 4 integers so we move on again.

The largestNumber integer is set to the number at index 0, which is 3.

int largestNumber = nums[0];

The secondLargestNumber is set to the smallest possible integer.

int secondLargestNumber = Integer.MIN_VALUE;

The dominantIndex is set to 0 by default. Remember, this is the index that holds the largestNumber.

int dominantIndex = 0;

Now we are at the for loop. We start the loop at index 1. The currentIndex is 1.

We save the currentNumber as the value at the currentIndex. The currentIndex is 1 which makes the currentNumber 6.

int currentNumber = nums[currentIndex];

If the currentNumber is greater than the largestNumber:

The current number is greater than the largest number

1. The largestNumber becomes the secondLargestNumber

secondLargestNumber = largestNumber;

2. The currentNumber becomes the largestNumber

largestNumber = currentNumber;

3. The currentIndex becomes the dominantIndex

dominantIndex = currentIndex;

We start the for loop over again. This time, we are at index 2.

The currentNumber is set to the value at the currentIndex. The currentIndex is 2. The number at index 2 is 1.

int currentNumber = nums[currentIndex];

Next we ask if the currentNumber is greater than the largestNumber. It is not. The currentNumber is 1. The largestNumber is 6. We move on to the next if statement.

if (currentNumber > largestNumber)

If the currentNumber is greater than the secondLargestNumber, the currentNumber becomes the secondLargestNumber. It’s not. The currentNumber is 1. The secondLargestNumber is 3. We go to the beginning of the for loop.

else if (currentNumber > secondLargestNumber)

Back to the beginning of the for loop where we are now at index 3.

The currentNumber is set to the number at the currentIndex. The number at the currentIndex is 0.

int currentNumber = nums[currentIndex];

Next, we ask if the currenNumber is greater than the largestNumber. It’s not. The currentNumber is 0. The largestNumber is 6. We move on to the next if-statement.

if (currentNumber > largestNumber)

Then we ask if the currentNumber is greater than the secondLargestNumber. It’s not. We finished the for loop. Now, we move on to the final if statement.

else if (currentNumber > secondLargestNumber)

If the largestNumber is twice as much as the secondLargestNumber, return the dominantIndex. It is. The largestNumber is 6. The secondlargestNumber is 3. The dominantIndex is 1. The answer is 1.

if (largestNumber >= secondLargestNumber * 2)

Complexity Analysis

Time Complexity: O(N) where N is the number of integers

Space Complexity: O(1), the space used by the int variables

You can find the source code on my github profile.

I’m raising $7k for my college tuition. Please help me out by donating and/or sharing my gofundme.