Number Greater Than Twice of Others


Thanks, I misunderstood the problem earlier, thanks for pointing 
func NumberTwiceAsOther(nums []int) int {
if len(nums) <= 1 { return 1 } min := nums[0] max := nums[0] maxIndex := 0 for i := 1; i < len(nums); i++ { if min > nums[i] { min = nums[i] } if max < nums[i] { max = nums[i] maxIndex = i } if max >= (2 * min) { return maxIndex } } return 1
}

Don't know whether binary search can improve the performance.
My code can pass the test and I think it's O(logn) as it's binary search (but use more space)Basic idea:
every "binarySearch" returns (max_idx, tag)
max_idx: the index of maximum value
tag: whether nums[max_idx] >= all other numbers *2 in these range.
So every time we update both max_idx and the tag by comparing nums[left_max_idx] and nums[right_max_idx]Codes
class Solution(object): def dominantIndex(self, nums): """ :type nums: List[int] :rtype: int """ if not nums or len(nums) < 2: return len(nums)1 idx, tag = self.binarySearch(nums, 0, len(nums)1) return idx if tag else 1 def binarySearch(self, nums, start, end): if start == end: return (start, True) middle = (start+end)/2 left_max_idx, left_tag = self.binarySearch(nums, start, middle) right_max_idx, right_tag = self.binarySearch(nums, middle+1, end) left_max, right_max = nums[left_max_idx], nums[right_max_idx] if left_max >= 2 * right_max: return (left_max_idx, left_tag) elif right_max >= 2 * left_max: return (right_max_idx, right_tag) elif left_max > right_max: return (left_max_idx, False) else: return (right_max_idx, False)

I do not think binary search will speed up the computation from O(N) to O(log(N)), because the input is not sorted and you have to visit every element at least once, thus making a O(N) algorithm.
A side note: binary search is helpful only when you do not have to check every element in the array.

@vkscs92
Requirement is correct as you stated.My comments are with respect to the below Linear Scan accepted solution:
class Solution {
public int dominantIndex(int[] nums) {
int maxIndex = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] > nums[maxIndex])
maxIndex = i;
}
for (int i = 0; i < nums.length; ++i) {
if (maxIndex != i && nums[maxIndex] < 2 * nums[i])
return 1;
}
return maxIndex;
}
}For ex: [2,8,4,8]  the above solution returns 1 when the expected answer is 1.
The additional condition in If statement is required to fix this to check for repetitive highest number:
if(maxIndex!=i && nums[maxIndex]<2 * nums[i] && nums[maxIndex]!=nums[i])

I believe we should be able to tell in just one iteration. The idea is to find second maximum and compare it with maximum in the array.
public int dominantIndex(int[] nums) {
int max = nums[0];
int secondMax = 0;
int index = 0;for (int i=1; i<nums.length; i++) { int n = nums[i]; if (n > max) { index = i; secondMax = max; max = n; } else if (n > secondMax) { secondMax = n; } } return max >= 2 * secondMax ? index : 1; }

My solution using python:
class Solution:
def dominantIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
maxNum = max(nums)
count = 0if size <= 1 or size > 50: return 0 for i in range(size): if 2 * nums[i] <= maxNum and i != nums.index(maxNum): count += 1 # return nums.index(maxNum) if count == size  1: return nums.index(maxNum) else: return 1

We only need to scan through the array once:
class Solution(object):
def dominantIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
current_largest = None
second_largest = None
current_largest_index = Nonefor index, i in enumerate(nums): if i > current_largest: second_largest = current_largest current_largest = i current_largest_index=index elif i > second_largest: second_largest = i if not second_largest: return current_largest_index elif (second_largest*2 > current_largest): return 1 else: return current_largest_index

/**

@param {number[]} nums

@return {number}
*/
var dominantIndex = function(nums) {
var currentMaxDouble = Number.MIN_VALUE;var index = 1;
for(var i = 0; i< nums.length;i++){
if(nums[i] >= currentMaxDouble){
index = i;
currentMaxDouble = nums[index] * 2;
} else if(nums[i] * 2 > nums[index] ){
index = 1;
}
}
return index;
};
