Largest Number At Least Twice of Others in Java

12 May 2025 | 3 min read

Given an integer array with unique values for the largest integer. Check to see if the greatest number in the array is at least twice as large as all the other numbers. If it is, return the greatest element's index; if not, return -1.

Example 1:

Input:

int arr = [10,5,2,1]

Output:

Explanation:

The greatest integer is 10. It is at least twice as large as all the other numbers in the array. We return zero because the index of 10 is 0.

Example 2:

Input:

int arr = [8,3,1,0]

Output:

Explanation:

The largest integer is eight, which is at least twice as large as every other number. We return zero since the index of 8 is 0.

Example 3:

Input:

int arr = [0,0,3,2]

Output:

-1

Explanation:

Since three is not at least twice as large as 2, we return -1 even if it is the largest integer.

Approach: Naïve Approach

Using a single pass, the code effectively determines the greatest number in an array and determines if it is at least twice as large as each other number (O(n) time complexity). To ensure that there are as few comparisons as possible, it keeps track of the largest and second-largest items using two variables. The logic is kept straightforward while correctness is guaranteed by the conditional check maximum >= secondMax * 2. Performance is improved by the program's avoidance of pointless sorting and nested loops. Because no additional data structures have been implemented, memory utilization stays constant (O(1) space complexity). Because of its efficient architecture, the program can handle big datasets.

Algorithm:

Step 1: Set MaxIndex, maximum, and secondMax to their initial values.

Step 2: Go through the array in iterations.

Step 2.1: Update secondMax to maximum if the current element exceeds it.

Step 2.1.1: Change the current element's maximum.

Step 2.1.2: Change MaxIndex to the most recent index.

Step 2.2: If, on the other hand, the current element exceeds secondMax.

Step 2.2.1: The current element should be updated in secondMax.

Step 3: Check the condition: Return MaxIndex if the maximum is more than or equal to twice the second max; return -1 otherwise.