LC-2542 Medium LeetCode

2542. Maximum Subsequence Score

Array Greedy Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 54% Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

import itertools
import heapq


# greedy, heap
class Solution(object):
    def maxScore(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: int
        """
        result = curr = 0
        min_heap = []
        for a, b in sorted(itertools.izip(nums1, nums2), key=lambda x: x[1],  reverse=True):
            curr += a
            heapq.heappush(min_heap, a)
            if len(min_heap) > k:
                curr -= heapq.heappop(min_heap)
            if len(min_heap) == k:
                result = max(result, curr*b)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT