2040. Kth Smallest Product of Two Sorted Arrays || Binary search || 2-pointers
This question involved using binary search on Ans-\n\nkey idea - we keep find out the number of product\u2264 our mid value and comparing it with our k\nwe keep
This question involved using binary search on Ans-\n\n**key idea** - we keep find out the **number of product\u2264 our mid value** and comparing it with our k\nwe keep shortening our upper bound when we have found our ans.\n\nchallenges faced-\n\n1. **effectively calculating the number of products of array in O(N) time**\nfor this we maintained a 2-pointer approach , since the array was sorted , we kept our **j pointer** to **last value of second array** and **i pointer** on **first value of second array** , if that value gave the answer less  than our num, all the values before that would give the same ans, so we update the cnt as j+1 and move i pointer ahead. Once j value reaches 0, increasing i pointer would not mean much and thus we exit out the loop.\n\n2.**handling negative numbers**\n\nour negative number would disturb the above approach and hence we have to handle them separately.\n\nWe first check **whether k lies in the negative side and positive side**, and according to that we proceed.\n\neg: if k lies in negative than we need only negative numbers to check and we multiply neg1 * pos2 and neg2 * pos1;\n\nalso **value of k decide which array we have to reverse**\n\n\u2192if k is in negative side to effectively get negative products count we would have to r**everse positive numbers** so as to fit our above logic\n\neg: arr1 = [-2,-1], arr2 = [3,4]\n\n-2 * 4 = -8  < -7 but -2 * 3 =-6 > -7\n\n\u2192by same logic when k is in positive side **we reverse negative numbers** to fit our logic\n\nI have taken low and high as most minimum and maximum values but you can take them as min and max value of products array\n```\nclass Solution {\npublic:\n    long long getnum(vector<int>& arr1,vector<int>& arr2,vector<int>& arr3,vector<int>& arr4,long long num){\n        int i = 0;\n        int j = arr2.size()-1;\n        long long  cnt = 0;\n        while(i<arr1.size() and j>=0 and arr2.size()>0){\n            if(1l*arr1[i]*arr2[j]<=num){\n                i++;\n                cnt+=(j+1);\n            }\n            else j--;\n        }\n        i=0;j=arr4.size()-1;\n        while(i<arr3.size() and j>=0 and arr4.size()>0){\n            if(1l*arr3[i]*arr4[j]<=num){\n                i++;\n                cnt+=(j+1);\n            }\n            else j--;\n        }\n        \n        return cnt;\n    }\n    \n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        \n        vector<int> pos1;\n        vector<int> neg1;\n        vector<int> pos2;\n        vector<int> neg2;\n        for(auto x:nums1){\n            if(x<0){\n                neg1.push_back(x);\n            }\n            else{\n                pos1.push_back(x);\n            }\n        }\n        for(auto x:nums2){\n            if(x<0){\n                neg2.push_back(x);\n            }\n            else{\n                pos2.push_back(x);\n            }\n        }\n        long long nofneg  = neg1.size() * pos2.size()  + neg2.size()*pos1.size();\n        bool iskneg = k>nofneg?false:true;\n        k = !iskneg?k-nofneg:k;\n        if(!iskneg){\n            reverse(neg1.begin(),neg1.end());\n            reverse(neg2.begin(),neg2.end());\n        }else{\n            reverse(pos1.begin(),pos1.end());\n            reverse(pos2.begin(),pos2.end());\n        }\n        long long low = -1e10,high = 1e10;\n        while(low<high){\n            long long mid = (long long)(low + (high-low)/2); \n            if(getnum(pos1,iskneg?neg2:pos2,neg1,iskneg?pos2:neg2,mid)>=k){\n                high = mid;\n            }else{\n                low = mid+1;\n            }\n            \n        }\n        return high;\n    }\n};\n```\n\n
['Two Pointers', 'Binary Tree']