<p>You are given two positive integer arrays <code>spells</code> and <code>potions</code>, of length <code>n</code> and <code>m</code> respectively, where <code>spells[i]</code> represents the strength of the <code>i<sup>th</sup></code> spell and <code>potions[j]</code> represents the strength of the <code>j<sup>th</sup></code> potion.</p>

<p>You are also given an integer <code>success</code>. A spell and potion pair is considered <strong>successful</strong> if the <strong>product</strong> of their strengths is <strong>at least</strong> <code>success</code>.</p>

<p>Return <em>an integer array </em><code>pairs</code><em> of length </em><code>n</code><em> where </em><code>pairs[i]</code><em> is the number of <strong>potions</strong> that will form a successful pair with the </em><code>i<sup>th</sup></code><em> spell.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> spells = [5,1,3], potions = [1,2,3,4,5], success = 7
<strong>Output:</strong> [4,0,3]
<strong>Explanation:</strong>
- 0<sup>th</sup> spell: 5 * [1,2,3,4,5] = [5,<u><strong>10</strong></u>,<u><strong>15</strong></u>,<u><strong>20</strong></u>,<u><strong>25</strong></u>]. 4 pairs are successful.
- 1<sup>st</sup> spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2<sup>nd</sup> spell: 3 * [1,2,3,4,5] = [3,6,<u><strong>9</strong></u>,<u><strong>12</strong></u>,<u><strong>15</strong></u>]. 3 pairs are successful.
Thus, [4,0,3] is returned.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> spells = [3,1,2], potions = [8,5,8], success = 16
<strong>Output:</strong> [2,0,2]
<strong>Explanation:</strong>
- 0<sup>th</sup> spell: 3 * [8,5,8] = [<u><strong>24</strong></u>,15,<u><strong>24</strong></u>]. 2 pairs are successful.
- 1<sup>st</sup> spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful. 
- 2<sup>nd</sup> spell: 2 * [8,5,8] = [<strong><u>16</u></strong>,10,<u><strong>16</strong></u>]. 2 pairs are successful. 
Thus, [2,0,2] is returned.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == spells.length</code></li>
	<li><code>m == potions.length</code></li>
	<li><code>1 &lt;= n, m &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= spells[i], potions[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= success &lt;= 10<sup>10</sup></code></li>
</ul>

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        """
        LC solution. Sort + Binary Search. 
        """
        potions.sort()
        output = []
        p = len(potions)
        
        # for spell in spells:
        #     left = 0
        #     right = p
        #     while left < right:
        #         mid = (left + right) // 2
        #         if potions[mid] * spell < success:
        #             left = mid + 1
        #         else:
        #             right = mid
        #     output.append(p - left)
        # return output
        for spell in spells:
            # leftmost insertion position
            left = 0
            right = p-1    # to make p-1 work, edge handling...
            
            # edge case 1
            if success < potions[left] * spell:
                idx = left
                output.append(p-idx)
                continue
            
            # edge case 2
            elif success > potions[right] * spell:
                idx = right + 1
                output.append(p - idx)
                continue

            while left < right:   ## <= does not work
                mid = (left + right) // 2
                if potions[mid] * spell < success:
                    left = mid + 1
                else:
                    right = mid
            output.append(p - left)
        return output
        
    def successfulPairsDJ(self, spells: List[int], potions: List[int], success: int) -> List[int]:        
        """
        my solution - accepted
        """
        potions.sort()  ## O(nlogn) time
        output = []
        for spell in spells:
            # binary search --> index
            # idx = self.bs([spell * p for p in potions], success)            
            idx = self.bs(potions, success/spell)
            output.append(len(potions) - idx)
            
        return output 
    
    def bs(self, sorted_list, target) -> int:
        """
        Find the insertion position for the target 
        value in a sorted list using binary search.
        E.g., sorted_list = [1,2,3,4,5], target = 1.2 --> 1
        E.g., sorted_list = [1,2,3,4,5], target = 0.5 --> 0
        """
        l, r = 0, len(sorted_list) - 1
        # edge case 1
        if target < sorted_list[l]:
            return l
        
        # edge case 2
        elif target > sorted_list[r]:
            return r + 1
        
        # binary search
        while l < r:
            mid = l + (r - l) // 2 
            
            if sorted_list[mid] < target:
                # If the value at mid is less than the target, 
                # move the left pointer to mid + 1 (since the 
                # target must be to the right of mid).
                l = mid + 1
            else:
                # Otherwise, move the right pointer to mid 
                # (since the target could be at mid or to the left).
                r = mid
        return l
1071