Java solution O(n)


  • 0
    P
    class Solution {
        public int dominantIndex(int[] nums) {
            // base case
            if (nums == null || nums.length < 2) {
                return -1;
            }
            // find max
            int max = Integer.MIN_VALUE;
            int largest = -1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > max) {
                    max = nums[i];
                    largest = i;
                }
            }
            // check max is more than twice as big as x
            for (int  i = 0; i < nums.length; i++) {
                if (nums[i]*2 > max && i != largest) {
                    return -1;
                }
            }
            
            
            return largest;
        }
    }
    

  • 0

    may be we could only loop once?

    class Solution {
        public int dominantIndex(int[] nums) {
            if (nums.length == 1) return 0;
            int result = nums[0] > nums[1] ? 0 : 1, second = nums[0] > nums[1] ? 1 : 0;
            for (int i = 2; i < nums.length; i++) {
                if (nums[i] > nums[result]) {
                    second = result;
                    result = i;
                } else if (nums[i] > nums[second]) {
                    second = i;
                }
            }
            return nums[result] >= 2 * nums[second] ? result : -1;
        }
    }
    

Log in to reply
 

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