LeetCode 747 in Java: Largest Number At Least Twice of Others Explained

Difficulty: Easy
Topics: Array, Sorting
Platform: Leetcode

Problem Statement

You are given an integer array nums where the largest integer is unique.
Determine whether the largest element in the array is at least twice as much as every other number in the array. If it is, return the index of the largest element, or return -1 otherwise.
Problem Statement Simplified
Check if the largest didgit is twice the other

Mistakes and Learning

Started working on it with the assumption to check if the largest number is twice - but the problem is atleast twice. 

Example 1

Input: nums = [3,6,1,0]
Output: 1
Explanation: 6 is the largest integer.
For every other number in the array x, 6 is at least twice as big as x.
The index of value 6 is 1, so we return 1.

Example 2

Input: nums = [1,2,3,4]
Output: -1
Explanation: 4 is less than twice the value of 3, so we return -1.
Key Insight
Check the largest number
Check if it is atleast twice the other
If yes then return the index 
If no then return -1

Algorithm

1. Copy nums array to another array.
2. Sort the new array.
3. Check if the largest is atleast twice the second largest
4. 5If yes then loop through the nums array
5. Check if nums[i]==largest in new array.
6. Return i;
7. End if 
8. End loop
9. End if
10. Else return -1.

Algorithm in simple words

Copy the nums array to another array to preserve the original index.
Then sort the new array, and check of the largest of new array is atleast twice the second largest array, if yes then loop through the nums array and find the original index of that largest array.
If the largest is not atleast twice the second largest then return -1.

Java code

class Solution {
    public int dominantIndex(int[] nums) {
        int [] arr = Arrays.copyOf(nums, nums.length);
        Arrays.sort(arr);
        int index=0;
        int secondLargest=arr[arr.length-2];
        if(arr[arr.length-1]>=2*secondLargest){
            for(int i=0;i<nums.length;i++){
                if(nums[i]==arr[arr.length-1]){
                    index=i;
                }
            }
        }
        else{
            index=-1;
        }       
        return index;
    }
}

Time & Space Complexity

Time Complexity: O(nlogn)
Space Complexity: O(n)

Comments

[Andy Nian]

Sorting the array to find the largest and second-largest numbers is inefficient when you could just do a single pass to track both values, saving you from that O(nlogn) overhead. I've been using LeetCode for DSA, but prachub.com has some company-specific questions that are really close to what recruiters ask. It's worth checking out if you want to better simulate what you'll encounter in technical screens.