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

• 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();
if(!s)
return {};
vector<int> res;
int count=0, candidate1=0, candidate2=0;

// reference here http://www.cplusplus.com/reference/algorithm/nth_element/
nth_element(nums.begin(), nums.begin() + s / 3, nums.end());

candidate1=nums[s/3]
for(auto num:nums)
num==candidate1 ? count++ : count;
if(count>s/3)
res.push_back(candidate1);

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)
res.push_back(candidate2);

return res;
}``````

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

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

• Very original!!!

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