algoadvance

Leetcode 747. Largest Number At Least Twice of Others Certainly! Let’s break down the problem step by step.

Problem Statement:

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

Clarifying Questions:

  1. Input Constraints:
    • Can the array be empty?
    • What are the possible values in the array (range of integers)?
  2. Output:
    • Index of the largest number if the condition holds.
    • -1 if the condition does not hold.
  3. Single Element Array: If the array has only one element, should we return its index (0) since there’s no other element to compare?

Let’s move forward assuming typical constraints:

Strategy:

  1. Edge Case Check: If the array has only one element, return 0.
  2. Iterate to Find Maximum and Second Maximum:
    • Keep track of the maximum value and its index.
    • Simultaneously, keep track of the second maximum value.
  3. Condition Check:
    • After the iteration, compare the maximum value with twice the second maximum value.
    • If the maximum is at least twice the second maximum, return its index.
    • Otherwise, return -1.

Code:

Here’s the C++ code implementing the above strategy:

#include <vector>
#include <iostream>
#include <algorithm>
#include <limits.h>

using namespace std;

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        if (nums.size() == 1) {
            return 0; // If there's only one number, it's trivially the largest.
        }
        
        int maxIndex = 0;
        int maxVal = INT_MIN;
        int secondMaxVal = INT_MIN;
        
        // Find maximum and second maximum values
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > maxVal) {
                secondMaxVal = maxVal; // Update second maximum
                maxVal = nums[i]; // Update maximum
                maxIndex = i; // Update index of maximum
            } else if (nums[i] > secondMaxVal) {
                secondMaxVal = nums[i]; // Update second maximum
            }
        }
        
        // Check the condition
        if (maxVal >= 2 * secondMaxVal) {
            return maxIndex;
        } else {
            return -1;
        }
    }
};

int main() {
    Solution sol;
    vector<int> nums = {3, 6, 1, 0};
    cout << "Dominant Index: " << sol.dominantIndex(nums) << endl; // Output: 1
    return 0;
}

Time Complexity:

This solution is efficient and straightforward, ensuring that the condition is verified in a single iteration over the array, resulting in an optimal time complexity.

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