[C++] O(n) with explanation.


  • -1

    The nature of the problem is such that we can just find the two max elements and then check the criteria on them.

    Explanation is included in the comments.

    class Solution {
    public:
        int dominantIndex(vector<int>& nums) {
            if(nums.empty() || nums.size()<2) return 0;
            
            //Get an iterator to, and the value of the max element
            auto maxElementIndex = max_element(nums.begin(), nums.end());
            int maxElementValue = *maxElementIndex;
            //Convert that iterator into its index
            int ans = maxElementIndex-nums.begin();
            
            //Erase the max element
            nums.erase(maxElementIndex);
            
            //Find the next highest element (in a method similar as above)
            auto maxElementIndexNow = max_element(nums.begin(), nums.end());
            int maxElementValueNow = *maxElementIndexNow;
            
            //check if the two elements satisfy the criteria
            if(maxElementValue >= 2*maxElementValueNow)
                return ans;
            else
                return -1;
        }
    };
    

Log in to reply
 

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