2542. Maximum Subsequence Score - Explanation

1. Brute Force (Recursion)

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n = len(nums1)

        def dfs(i, k, minVal, curSum):
            if k == 0:
                return curSum * minVal
            if i == n or (n - i) < k:
                return float("-inf")
            if minVal == 0:
                return 0

            res = dfs(i + 1, k, minVal, curSum)
            res = max(res, dfs(i + 1, k - 1, min(minVal, nums2[i]), curSum + nums1[i]))
            return res

        return dfs(0, k, float("inf"), 0)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Min-Heap - I

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        pairs = sorted(zip(nums1, nums2), key=lambda p: p[1], reverse=True)

        minHeap = []
        n1Sum = 0
        res = 0

        for n1, n2 in pairs:
            n1Sum += n1
            heapq.heappush(minHeap, n1)

            if len(minHeap) > k:
                n1Sum -= heapq.heappop(minHeap)

            if len(minHeap) == k:
                res = max(res, n1Sum * n2)

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Min-Heap - II

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n = len(nums1)
        arr = [(nums2[i] << 30) | nums1[i] for i in range(n)]
        arr.sort(reverse=True)

        minHeap = []
        n1Sum = 0
        res = 0

        for num in arr:
            n1, n2 = num & ((1 << 30) - 1), num >> 30
            n1Sum += n1
            heapq.heappush(minHeap, n1)

            if len(minHeap) > k:
                n1Sum -= heapq.heappop(minHeap)

            if len(minHeap) == k:
                res = max(res, n1Sum * n2)

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$