Largest Number At Least Twice of Others

Problem Description

Imagine you’re at a party, and there’s that one friend who insists they can eat twice as many slices of pizza as anyone else. But can they really? This problem is all about finding out if there’s a number in an array that is at least twice as large as every other number. If it is, return the index of the largest number; otherwise, return -1.

Code Solution


class Solution {
  public int dominantIndex(int[] nums) {
    int ans = 0;
    int mx = 0;
    int secondMax = 0;

    for (int i = 0; i < nums.length; ++i)
      if (nums[i] > mx) {
        secondMax = mx;
        mx = nums[i];
        ans = i;
      } else if (nums[i] > secondMax) {
        secondMax = nums[i];
      }

    return mx >= 2 * secondMax ? ans : -1;
  }
}

Approach

The approach here is straightforward yet effective. We iterate through the array to find the maximum number (mx) and the second maximum number (secondMax). If we find a new maximum, we update the second maximum accordingly. Finally, we check if the maximum number is at least twice the second maximum. If it is, we return the index of the maximum; otherwise, we return -1.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(n)
Space Complexity O(1)

Real-World Example

Imagine a race where one runner claims they can run twice as fast as everyone else. If they finish the race in 10 seconds, but the second-fastest runner finishes in 12 seconds, our claim is validated! However, if the second runner finishes in 8 seconds, well, our runner might need to rethink their strategy. This mirrors our problem perfectly: we need to check if the fastest runner (the largest number) is indeed twice as fast as the second-fastest (the second largest number).

Similar Problems

If you enjoyed this problem, you might also like these:

  • Two Sum Solution in Java
  • Three Sum Solution in Java
  • Four Sum Solution in Java