Successful Pairs of Spells and Potions

Leetcode Daily Challenge (2nd April, 2023)

2 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

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

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Link: https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/

Problem Explanation with examples:-

Example 1

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

Example 2

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

Constraints

n == spells.length
m == potions.length
1 <= n, m <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010

Intuition:-

Here we need something which can tell us how many elements are greater than or equal to a given number.
Using this, we can iterate over the spells array, find the divisor of success and find the number of potions greater than or equal to that number.
We can use a prefix sum array to find the number of potions greater than or equal to a given number iterating from the end of the potions array.

Solution:-

Sort the potions array.
Create a prefix sum array of size potions[len(potions)-1]+2 and initialize it with 0.
Initialize two pointers i and j to the last element of the potions array and the last element of the prefix sum array respectively.
Run a while loop until j >= 0.
If i == potions[j], then check if the value at arr[i] is greater than 0, if yes, then increment it by 1, else assign it the value of arr[i+1]+1.
Incrementing by 1 when the value is greater than 0 tells that the same value is repeated in the potions array.
Then decrement j by 1. If j < 0, then break the loop.
Run another while loop while i > potions[j] inside the first while loop.
Decrement i by 1.
If i != potions[j], then assign arr[i] the value of arr[i+1].
After the while loop, decrement i by 1.
Run another while loop while i >= 0 independent of the first while loop.
Assign arr[i] the value of arr[i+1] and decrement i by 1.
Now, iterate over the spells array and find the divisor of success.
If the divisor is greater than or equal to the length of the prefix sum array, then append 0 to the ans array.
Else, append the value at arr[divisor] to the ans array.
Return the ans array.

Code:-

JAVA Solution

class Solution {
    public List<Integer> successfulPairs(List<Integer> spells, List<Integer> potions, int success) {
        Collections.sort(potions);
        int n = potions.get(potions.size()-1);
        int[] arr = new int[n+2];
        int j = potions.size()-1;
        int i = n;

        while (j >= 0) {
            if (i == potions.get(j)) {
                if (arr[i] > 0) {
                    arr[i] += 1;
                } else {
                    arr[i] = (arr[i+1]+1);
                }
                j -= 1;
                if (j < 0) {
                    break;
                }
            }
            while (i > potions.get(j)) {
                i -= 1;
                if (i != potions.get(j)) {
                    arr[i] = arr[i+1];
                }
            }
        }
        i -= 1;
        while (i >= 0) {
            arr[i] = arr[i+1];
            i -= 1;
        }
        List<Integer> ans = new ArrayList<>();
        for (int x : spells) {
            int d = (int)Math.ceil(success/(double)x);
            if (d >= arr.length) {
                ans.add(0);
                continue;
            }
            ans.add(arr[d]);
        }

        return ans;
    }
}

Python Solution

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        n = potions[len(potions)-1]
        arr = [0]*(n+2)
        j = len(potions)-1
        i = n

        while j >= 0:
            if i == potions[j]:
                if arr[i] > 0:
                    arr[i] += 1
                else:
                    arr[i] = (arr[i+1]+1)
                j -= 1
                if j < 0:
                    break
            
            while i > potions[j]:
                i -= 1
                if i != potions[j]:
                    arr[i] = arr[i+1]
        i -= 1
        while i >= 0:
            arr[i] = arr[i+1]
            i -= 1
        ans = []
        for x in spells:
            d = int(math.ceil(success/x))
            if d >= len(arr):
                ans.append(0)
                continue
            ans.append(arr[d])

        return ans

Complexity Analysis:-

TIME:-

The time complexity is O(n log n), where n is the length of the potions array. This is because the potions array is sorted using the Collections.sort() method, which has a time complexity of O(n log n). The remaining operations have a time complexity of O(n), since we are iterating over the potions array once and performing constant-time operations within the while loops.

SPACE:-

The space complexity is O(n), where n is the maximum value in the potions array. This is because we create an array arr of size n+2, and use additional space to store variables i, j, and d. The space required for the input and output lists is not counted in this analysis.

References:-

Prefix Sum