Efficient C++ code. O(1) Space. O(max(nlogn),mlog(m)) time complexity. beats 86.05%


  • 0
    N
    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            vector<int>ans;
            sort(nums1.begin(),nums1.end());
            sort(nums2.begin(),nums2.end());
            for(int i=0,j=0;i<nums1.size()&&j<nums2.size();)
            {
                if(nums1[i]==nums2[j])
                {
                    int temp=nums1[i];
                    int cnt1=0,cnt2=0;
                    while(nums1[i]==temp&&i<nums1.size())
                    {
                        i++;
                        cnt1++;
                    }
                    while(nums2[j]==temp&&j<nums2.size())
                    {
                        j++;
                        cnt2++;
                    }
                    int cnt=min(cnt1,cnt2);
                    while(cnt--)ans.push_back(temp);
                }
                else if(nums1[i]>nums2[j])
                {
                    while(nums1[i]>nums2[j]&&i<nums1.size())j++;
                }
                else 
                {
                    while(nums1[i]<nums2[j]&&j<nums2.size())i++;
                }
            }
            return ans;
        }
    };

Log in to reply
 

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