How hard is LeetCode 2931. Maximum Spending After Buying Items?

LeetCode 2931. Maximum Spending After Buying Items is rated Hard on LeetCode.

What is the time complexity of LeetCode 2931. Maximum Spending After Buying Items?

The Python solution on this page runs in O(m \times n \times \log m).

What is the space complexity of LeetCode 2931. Maximum Spending After Buying Items?

The Python solution on this page uses O(m) auxiliary space.

What topics does LeetCode 2931. Maximum Spending After Buying Items cover?

LeetCode 2931. Maximum Spending After Buying Items is tagged Greedy, Array, Matrix, Sorting and Heap (Priority Queue) on LeetCode.

Maximum Spending After Buying Items — LeetCode 2931 Python Solution

HardGreedyArrayMatrixSortingHeap (Priority Queue)

Problem: #2931
Pattern: Heap / Priority Queue
Reading time: 3 min
Source: leetcode.com

The problem

You are given a 0-indexed m * n integer matrix values, representing the values of m * n different items in m different shops. Each shop has n items where the jth item in the ith shop has a value of values[i][j].

Example

Input: values = [[8,5,2],[6,4,1],[9,7,3]]
Output: 285
Explanation: On the first day, we buy product 2 from shop 1 for a price of values[1][2] * 1 = 1.

Python solution

Python

class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        n = len(values[0])
        pq = [(row[-1], i, n - 1) for i, row in enumerate(values)]
        heapify(pq)
        ans = d = 0
        while pq:
            d += 1
            v, i, j = heappop(pq)
            ans += v * d
            if j:
                heappush(pq, (values[i][j - 1], i, j - 1))
        return ans

Complexity

Measure	Complexity
Time	O(m \times n \times \log m)
Space	O(m) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2931. Maximum Spending After Buying Items is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2931. Maximum Spending After Buying Items?: LeetCode 2931. Maximum Spending After Buying Items is rated Hard on LeetCode.
What is the time complexity of LeetCode 2931. Maximum Spending After Buying Items?: The Python solution on this page runs in O(m \times n \times \log m).
What is the space complexity of LeetCode 2931. Maximum Spending After Buying Items?: The Python solution on this page uses O(m) auxiliary space.
What topics does LeetCode 2931. Maximum Spending After Buying Items cover?: LeetCode 2931. Maximum Spending After Buying Items is tagged Greedy, Array, Matrix, Sorting and Heap (Priority Queue) on LeetCode.