C++ || Detailed Explanation || Binary Search || Counting ||
Intuition\n###### The key intuition to solve this problem is to use binary search on the answer space rather than generating all possible products. Instead of a
# Intuition\n###### The key intuition to solve this problem is to use **`binary search`** on the answer space rather than generating all possible products. Instead of asking "what is the **`kth`** smallest product?", we transform the question to "how many products are less than or equal to a given value **`x`**?". If we can efficiently answer this question, we can binary search for the **`kth`** smallest product. The tricky part is counting these products quickly. Since we\'re dealing with multiplication, we need to consider **three** **cases**: when the first number is **positive**, **negative**, or **zero**, as this affects how we count valid pairs. For positive numbers, we\'re looking for products less than **`x`**, so we need the second number to be less than **`x`** divided by our first number. For negative numbers, the inequality flips, so we need the second number to be greater than **`x`** divided by our first number. Since our second array is sorted, we can use binary search (**`upper_bound`** for **positive**, **`lower_bound`** for **negative**) to quickly count how many numbers satisfy these conditions. Zero is a special case that\'s easy to handle separately. By leveraging this counting method within our binary search on the answer space, we can efficiently find the **`kth`** smallest product without actually generating all possible products, giving us a solution that\'s much faster than a brute force approach.\n\n# Approach\n###### The solution uses binary search on the answer space **`[-10^10, 10^10]`** to find the **`kth`** smallest product \n- For each potential answer **`x`**, we count how many products are **`\u2264 x`** \n- For efficient counting, we iterate through each number **`a`** in **`nums1`** and handle three cases: **positive**, **negative**, and **zero** \n  - For **positive** **`a`**, we find how many **`b`** in **`nums2`** satisfy **`b \u2264 x/a`** using **`upper_bound`** \n  - For **negative** **`a`**, we find how many **`b`** in **`nums2`** satisfy **`b \u2265 x/a`** using **`lower_bound`** (since the inequality flips) \n  - For **zero**, we count all numbers in **`nums2`** if **`x \u2265 0`** \n  - The counting function can terminate early if we find **`k`** or more valid products \n- If we find **`\u2265 k`** products **`\u2264 x`**, we store **`x`** as a potential answer and try a smaller value in our binary search \n- If we find **`< k`** products, we need to try a larger value \n- Binary search continues until we find the smallest **`x`** that has at least **`k`** products less than or equal to it \n- The solution avoids generating all possible products, instead using binary search twice: once for the answer and once for counting, making it efficient for large inputs.\n\n# Code Walkthrough\n- The binary search implementation:\n    ```\n    ll low = -1e10;\n    ll high = 1e10;\n    ll ans = 0;\n    while(low <= high) {\n        ll mid = low + (high-low)/2;\n        if(isPossible(mid, nums1, nums2, k)) {\n            ans = mid;\n            high = mid-1;\n        } else {\n            low = mid+1;\n        }\n    }\n    ```\n    - ###### This is trying to find the smallest value \'x\' such that there are at least k pairs whose product is less than or equal to x.\n- The crucial part is the isPossible function:\n    ```\n    bool isPossible(ll x, vector<int>& nums1, vector<int>& nums2, ll k)\n    ```\n    - ###### This function checks if there are at least **`k`** pairs whose product is less than or equal to **`x`**.\n    - \n###### Let\'s understand the **three cases**:\n###### **a)** When **`nums1[i] < 0`** (negative number):\n```\nif(nums1[i] < 0) {\n    ll rem = ceil((double)x/nums1[i]);\n    int ind = lower_bound(nums2.begin(), nums2.end(), rem) - nums2.begin();\n    count += (n2-ind);\n}\n```\n###### When multiplying a negative number, the inequality reverses. So, for **`nums1[i] * nums2[j] <= x`**:\n- We need **`nums2[j] >= x/nums1[i]`**\n- We use ceil because we want the smallest number that satisfies this\n- lower_bound finds the first element **`>= rem`**\n- All elements from this index to the end will satisfy our condition\n\n###### **b)** When **`nums1[i] > 0`** (positive number):\n```\nelse if(nums1[i] > 0) {\n    ll rem = floor((double)x/nums1[i]);\n    int ind = upper_bound(nums2.begin(), nums2.end(), rem) - nums2.begin();\n    count += ind;\n}\n```\n###### For positive numbers:\n- We need **`nums2[j] <= x/nums1[i]`**\n- We use floor because we want the largest number that satisfies this\n- **`upper_bound`** finds the first **`element > rem`**\n- All elements before this index will satisfy our condition\n\n###### **c)** When **`nums1[i] == 0`**:\n```\nelse {\n    if(x >= 0) {\n        count += n2;\n    }\n}\n```\n###### When multiplying by **`zero`**:\n- If **`x >= 0`**, all products (which will be 0) are **`<= x`**\n- If **`x < 0`**, no products satisfy the condition\n\n###### The function returns **`true`** if the total count of satisfying pairs is **`>= k`**.\n\n# Special Focus(Dry Run):\n\n###### Let\'s dive deeper into these two cases with examples.\n\n###### **A)** When **`nums1[i] < 0`** (Negative Number Case)\n###### Let\'s take an example:\n```\nnums1[i] = -2\nnums2 = [1, 3, 5, 7]\nx = 10\n```\n###### We want to find how many products **`(-2 * nums2[j])`** are less than or equal to **`10`**.\n\n- ###### First, we calculate **`rem = ceil(x/nums1[i])`**\n    ```\n    rem = ceil(10/-2) = ceil(-5) = -5\n    ```\n- ###### Now, the inequality we\'re solving:\n    ```\n    -2 * nums2[j] \u2264 10\n    nums2[j] \u2265 -5    (dividing both sides by -2, inequality sign flips)\n    ```\n- ###### We use **`lower_bound`** to find the first element in **`nums2`** that is **`\u2265 -5`**. In our example, all elements are **`\u2265 -5`**, so **`index = 0`**\n- ###### **`Count`** is incremented by **`(n2 - index) = 4 - 0 = 4`**\n\n###### This means all four products ($$-2\\times1$$ = -2, $$-2\\times3$$ = -6, $$-2\\times5$$ = -10, $$-2\\times 7$$ = -14) are **`\u2264 10`**.\n\n###### **B)** When nums1[i] > 0 (Positive Number Case)\n###### Let\'s take another example:\n```\nnums1[i] = 2\nnums2 = [1, 3, 5, 7]\nx = 10\n```\n###### We want to find how many products **`(2 * nums2[j])`** are less than or equal to **`10`**.\n\n- First, we calculate rem = floor(x/nums1[i])\n    ```\n    rem = floor(10/2) = floor(5) = 5\n    ```\n- The inequality we\'re solving:\n    ```\n    2 * nums2[j] \u2264 10\n    nums2[j] \u2264 5    (dividing both sides by 2, inequality sign remains the same)\n    ```\n- We use upper_bound to find the first element in nums2 that is > 5. In our example, this is the index 3 (element 7)\n- Count is incremented by this index: 3\n\n###### This means three products ($$2*1 = 2,~~2*3 = 6,~~2*5 = 10$$) are **`\u2264 10`**.\n\n###### **Why the difference in approach?**\n\n- **Ceiling vs Floor**\n\n    - For negative numbers, we use ceiling because when we divide by a negative number, we want to round up to get the smallest number that satisfies our inequality\nFor positive numbers, we use floor because we want the largest number that satisfies our inequality\n\n\n- **Lower_bound vs Upper_bound**\n\n    - For negative numbers, we use lower_bound because we\'re looking for numbers greater than or equal to our calculated rem\nFor positive numbers, we use upper_bound because we\'re looking for the point where numbers become greater than our calculated rem\n\n\n- **Counting**\n\n  - For negative numbers, we count from the found index to the end\n  - For positive numbers, we count from the beginning to the found index\n\n\n\n###### **Here\'s a visualization:**\n```\nNegative case (-2):\nnums2:  1   3   5   7\nx/n1:  -5  -5  -5  -5\n        \u2191   \u2191   \u2191   \u2191\n     All count because all \u2265 -5\n\nPositive case (2):\nnums2:  1   3   5   7\nx/n1:   5   5   5   5\n        \u2191   \u2191   \u2191   \n     These count   \u2934 This doesn\'t\n     because \u2264 5\n```\n\n# Complexity\n- **Time complexity:**\n  - Binary search takes $$O(log(10^{10}))$$ iterations\n  - For each iteration, isPossible function takes O(n1 * log(n2))\n  - Total: $$O(n1 * log(n2) * log(10^{10}))$$\n\n- **Space complexity:** $$O(1)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    using ll = long long;\n    bool isPossible(ll x, vector<int>& nums1, vector<int>& nums2, ll k){\n        int n1 = nums1.size();\n        int n2 = nums2.size();\n        ll count=0;\n        for(int i=0;i<n1;i++){\n            if(nums1[i]<0){\n                ll rem = ceil((double)x/nums1[i]);\n                int ind = lower_bound(nums2.begin(), nums2.end(), rem)-nums2.begin();\n                count += (n2-ind);\n            }else if(nums1[i]>0){\n                ll rem = floor((double)x/nums1[i]);\n                int ind = upper_bound(nums2.begin(), nums2.end(), rem)-nums2.begin();\n                count += ind;\n            }else{\n                if(x>=0){\n                    count += n2;\n                }\n            }\n            if(count>=k) return true;\n        }\n        return count>=k;\n    }\n    ll kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, ll k) {\n        int n1 = nums1.size();\n        int n2 = nums2.size();\n        ll low = -1e10;\n        ll high = 1e10;\n        ll ans=0;\n        while(low<=high){\n            ll mid = low+(high-low)/2;\n            if(isPossible(mid, nums1, nums2, k)){\n                ans = mid;\n                high = mid-1;\n            }else{\n                low = mid+1;\n            }\n        }\n        return ans;\n    }\n};\n```\n## If you found this helpful, an upvote would be greatly appreciated!\n## Comment any doubt or suggestions.
['Array', 'Binary Search', 'Counting', 'C++']