Search code examples
arraystime-complexitybinary-searchspace-complexity

Why 1st code gives Memory Limit exceeded and 2nd code works fine?


Why 1st code gives Memory Limit exceeded and 2nd code works fine???? This is question no 1855. Maximum Distance Between a Pair of Values of Leetcode. I think in both code space complexity should be constant but why first code is giving memory limit exceeded while second code works fine.

1.

class Solution {
public:
    int binarySearch(vector<int> nums, int l, int h, int target) {
        int res=-1;
        
        while(l<=h) {
            int mid = (l+h)/2;
            if(nums[mid] >= target)
            {
                res=mid;
                l=mid+1;
            }
            else h=mid-1;
        }     
        return res;
    }
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int maxi = 0;
        
        for(int i=0; i<nums1.size(); i++) {
            int ind = binarySearch(nums2, i, nums2.size()-1, nums1[i]);
            if(ind != -1) {
                maxi=max(ind-i, maxi);
            }
        }
        
        return maxi;
    }
};

2.

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int maxi = 0;
        
        for(int i=0; i<nums1.size(); i++) {
            int h=nums2.size()-1, l=i;
            while(l<=h) {
                int mid = (l+h)/2;
                if(nums2\[mid\] >= nums1\[i\])
                {
                    maxi=max(mid-i, maxi);
                    l=mid+1;
                }
                else h=mid-1;
            }
        } 
        
        return maxi;
    }
};

Solution

  • One of the possible reasons can be that in the first approach, the vector is passed by value. So whenever the function is called, a copy of the vector nums is created which is used further in the function. I think passing the vector by reference would not lead to MLE.