How hard is LeetCode 2813. Maximum Elegance of a K-Length Subsequence?

LeetCode 2813. Maximum Elegance of a K-Length Subsequence is rated Hard on LeetCode.

What is the time complexity of LeetCode 2813. Maximum Elegance of a K-Length Subsequence?

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

What is the space complexity of LeetCode 2813. Maximum Elegance of a K-Length Subsequence?

The Python solution on this page uses O(n), where n is the number of items auxiliary space.

What topics does LeetCode 2813. Maximum Elegance of a K-Length Subsequence cover?

LeetCode 2813. Maximum Elegance of a K-Length Subsequence is tagged Stack, Greedy, Array, Hash Table, Sorting and Heap (Priority Queue) on LeetCode.

Maximum Elegance of a K-Length Subsequence — LeetCode 2813 Python Solution

HardStackGreedyArrayHash TableSortingHeap (Priority Queue)

Problem: #2813
Pattern: Heap / Priority Queue
Reading time: 4 min
Source: leetcode.com

The problem

You are given a 0-indexed 2D integer array items of length n and an integer k. items[i] = [profiti, categoryi], where profiti and categoryi denote the profit and category of the ith item respectively.

Example

Input: items = [[3,2],[5,1],[10,1]], k = 2
Output: 17
Explanation: In this example, we have to select a subsequence of size 2.

Python solution

Python

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key=lambda x: -x[0])
        tot = 0
        vis = set()
        dup = []
        for p, c in items[:k]:
            tot += p
            if c not in vis:
                vis.add(c)
            else:
                dup.append(p)
        ans = tot + len(vis) ** 2
        for p, c in items[k:]:
            if c in vis or not dup:
                continue
            vis.add(c)
            tot += p - dup.pop()
            ans = max(ans, tot + len(vis) ** 2)
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n), where n is the number of items auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2813. Maximum Elegance of a K-Length Subsequence 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 2813. Maximum Elegance of a K-Length Subsequence?: LeetCode 2813. Maximum Elegance of a K-Length Subsequence is rated Hard on LeetCode.
What is the time complexity of LeetCode 2813. Maximum Elegance of a K-Length Subsequence?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2813. Maximum Elegance of a K-Length Subsequence?: The Python solution on this page uses O(n), where n is the number of items auxiliary space.
What topics does LeetCode 2813. Maximum Elegance of a K-Length Subsequence cover?: LeetCode 2813. Maximum Elegance of a K-Length Subsequence is tagged Stack, Greedy, Array, Hash Table, Sorting and Heap (Priority Queue) on LeetCode.