Can anybody tell me if this C++ solution is O(1) space complexity?

  • 6

    The idea here is to select n/3-th element and 2n/3-th element as candidates. And then check if they appear more than n/3 times;
    This solution does work, but the problem is I am not sure if it meets the O(1) space requirement.

        vector<int> majorityElement(vector<int>& nums) {
            int s=nums.size();
                return {};
            vector<int> res;
            int count=0, candidate1=0, candidate2=0;
            // reference here
            nth_element(nums.begin(), nums.begin() + s / 3, nums.end());  
            for(auto num:nums)
                num==candidate1 ? count++ : count;
            nth_element(nums.begin(), nums.begin() + 2 * s / 3, nums.end());   
            count=0, candidate2=nums[2*s/3];
            for(auto num:nums)
                num==candidate2 ? count++ : count;
            if(count>s/3 && candidate1 != candidate2)
            return res;

  • 0

    Yes, it definitely is. Very original solution. Thanks for sharing!

  • 1

    Function "nth_element" is quick select. It is an O(n) time and O(1) space algorithm.

  • 0

    Very original!!!

Log in to reply

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