Number Greater Than Twice of Others


  • 0

    Click here to see the full article post


  • 1
    J

    Also O(N) solution, but scanning through the array once.
    Find largest and second largest numbers in the array and check if the largest is at least twice as large as the second largest number.


  • 0
    C

    Yes jwgoh, one scan through array with Max and second max will do the solution in O(N)


  • 0
    C

    Here is Golang solution
    func DominantIndex(a []int) int {
    max := 0
    maxLast := 0

    for i := 0 ; i < len(a); i++ {
    
    	if a[i] > max {
    		maxLast = max
    		max = a[i]
    	}
    }
    
    if max < maxLast * 2 {
    	return 0
    }
    return 1
    

    }


  • 0
    G

    @Cchhabra.pankaj I sorry for say that ,your solution probably wrong! When the first element is the largest element, your "maxLast" always equal with "max".Have a try when nums = [9,0,5]


  • 0
    C

    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
    

    }


  • 0
    I

    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)

  • 0
    S

    @impromptu

    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.


  • 0
    M

    The above solution gives wrong result if the highest number is repeated.


  • 0
    V

    @talktoswapna

    Doesn't matter if the highest number has occured multiple times, it's still highest number right? Product of every other number with 2 should be less than the highest number. Hope i making some sense.


  • 0
    M

    @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])


  • 0
    R

    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;
        
    }

  • 0
    C

    My solution using python:

    class Solution:
    def dominantIndex(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    size = len(nums)
    maxNum = max(nums)
    count = 0

        if 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

  • 0
    P

    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 = None

        for 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

  • 0
    D

    /**

    • @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;
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.