Problem Explanation

This problem is asking us to return the index of the largest number in the array if it is at least twice as big as every other number in the array. If no such number exists we should return -1.

Let's consider an example to get more clear understanding, For instance, you are given an array [3, 6, 1, 0]. The largest number in this array is 6 (with index 1) and it is at least twice as big as every other number in the array. Therefore for this case we would return 1.

In case of array like [1, 2, 3, 4], the largest number 4 isn't at least twice as big as the second largest number 3. Therefore, for this case we would return -1.

Solution Approach

The main idea here is to maintain a track of both maximum and second maximum number in the array. Here are the main steps we perform to solve this problem:

• Initialize maximum and second maximum variables to 0 and answer variable (to keep track of index of maximum element) to 0.
• Iterate through the array:
  1. For any element in array which is larger than the maximum, we update the second maximum and then update the maximum.
  2. If it is not greater than the maximum but greater than the second maximum, we then only update the second maximum.
• At last, if the maximum number is at least twice as big as second maximum, return answer otherwise return -1.

Python Solution

1
2python
3class Solution:
4    def dominantIndex(self, nums: List[int]) -> int:
5        maximum = second_max = ans = 0
6        for i in range(len(nums)):
7            if nums[i] > maximum:
8                second_max = maximum
9                maximum = nums[i]
10                ans = i
11            elif nums[i] > second_max:
12                second_max = nums[i]
13        return ans if maximum >= 2 * second_max else -1

Java Solution

1
2java
3class Solution {
4    public int dominantIndex(int[] nums) {
5        int max = 0, secondMax = 0, ans = 0;
6        for(int i=0; i< nums.length; i++){
7            if(nums[i] > max){
8                secondMax = max;
9                max = nums[i];
10                ans = i;
11            }else if(nums[i] > secondMax){
12                secondMax = nums[i];
13            }
14        }
15        return max >= 2 * secondMax ? ans : -1;
16    }
17}

JavaScript Solution

1
2javascript
3var dominantIndex = function(nums) {
4    let max = 0, secondMax = 0, ans=0;
5    for(let i=0; i< nums.length; i++){
6        if(nums[i] > max){
7            secondMax = max;
8            max = nums[i];
9            ans = i;
10        }else if(nums[i] > secondMax){
11            secondMax = nums[i];
12        }
13    }
14    return max >= 2 * secondMax ? ans : -1;
15};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int dominantIndex(vector<int>& nums) {
6        int ans = 0;
7        int max = 0;
8        int secondMax = 0;
9        for (int i = 0; i < nums.size(); ++i)
10            if (nums[i] > max) {
11                secondMax = max;
12                max = nums[i];
13                ans = i;
14            } else if (nums[i] > secondMax) {
15                secondMax = nums[i];
16            }
17        return max >= 2 * secondMax ? ans : -1;
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public int DominantIndex(int[] nums) {
5        int max = 0, secondMax = 0, ans = 0;
6        for(int i = 0; i < nums.Length; i++){
7            if(nums[i] > max){
8                secondMax = max;
9                max = nums[i];
10                ans = i;
11            }else if(nums[i] > secondMax){
12                secondMax = nums[i];
13            }
14        }
15        return max >= 2 * secondMax ? ans : -1;
16    }
17}

In all the solutions, we are just iterating the array and comparing each element with max and secondMax and updating accordingly. The time complexity for this approach is O(n), where n is the length of nums. And the space complexity is O(1), as we are using constant extra space.In certain situations where the array data isn't in a random order and has certain specifications, we can create a more efficient algorithm. However, for a randomly ordered array, this seems to be the simplest and most efficient solution approach for this problem.

However, if we know that incoming input will have certain characteristics, we can potentially improve time complexity by altering our algorithm. More specifically, if we know that the input array is sorted either in ascending or descending order, we can complete the check in constant, O(1) time by just comparing the first two or last two elements of the array (depending on the sort order).

In conclusion, it is important to keep in mind that the most effective algorithm can fluctuate based on the characteristics of the incoming input.

Now that I shared an algorithm to solve the problem, it's time for you to work on some examples to get comfortable with this problem. Remember, practice is key to mastering technical questions during coding interviews.