LeetCode Problem 747. Largest Number At Least Twice of Others || Java Solution Walkthrough

LeetCode is a great platform for people who want general coding practice, whether that be for interviews or just wanting to practice their problem solving. I will be taking you through all the steps of finding the optimal solution to each problem on the site following a logical ordering setout by LeetCode themselves.

In this video, we are going over the problem 747: Largest Number At Least Twice of Others, where the goal is to loop through keeping track of the largest element in the array and keep track if that element is also two times as large as the rest of the elements.

This problem is actually very simple if we just break it down into two separate parts. The first part is finding the largest value inside of the array, which is not hard to do. Then the second part is to check every value, other than the index of the largest element to see if the largest index is twice as large as all the others.

~~~ Stay Up To Date With My Social Media ~~~

#unknownkoder #leetcode #algorithms

[dunsteinthedragon]

Wouldn't it be more efficient to just loop through nums once and store the max, maxIndex and second max. Then if secondMax * 2 <= max return maxIndex else return -1? This would have O(n) instead of O(2n) time complexity and O(1) space complexity

public class Solution {
public int DominantIndex(int[] nums) {
int max = 0;
int maxIndex = 0;
int secondMax = 0;

for(int i = 0; i < nums.Length; i++)
{
var num = nums[i];

if(num > max){
secondMax = max;
max = num;
maxIndex = i;
}
else if(num > secondMax){
secondMax = num;
}
}

return secondMax * 2 <= max ? maxIndex : -1;
}
}