Largest Values From Labels - Video Solutions

Problem Overview: You are given two arrays: values and labels. Each item has a value and a label. You may choose at most numWanted items, but each label can only be used up to useLimit times. The goal is to maximize the total value of the selected items.

Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)

The key observation is that the objective is purely value maximization with a constraint on how many times a label can appear. That naturally suggests a greedy strategy: always try to take the highest-value items first. Pair each value with its label, then sort the items in descending order by value using a sorting step. Iterate through the sorted list and keep selecting items while tracking how many times each label has been used.

A simple counter structure such as a hash map or array keeps the usage count for every label. If the current item's label has been used fewer than useLimit times, include it and add its value to the result. Stop once numWanted items have been chosen. Sorting dominates the runtime, giving O(n log n) time, while the label counter uses O(n) space in the worst case.

Approach 2: Heap-based Greedy Using Priority Queue (O(n log n) time, O(n) space)

This version replaces explicit sorting with a max-heap (priority queue). Insert all items into a heap ordered by value. Each step pops the largest available value, checks the label usage, and decides whether to include the item. Label frequencies are tracked using a hash table.

The heap ensures that every extraction returns the current highest-value candidate. Continue popping until either numWanted valid items are selected or the heap becomes empty. Heap insertion and removal cost O(log n), so processing all elements results in O(n log n) time with O(n) space for the heap and label counts.

Recommended for interviews: The greedy sorting approach is the most common solution expected in interviews. It clearly demonstrates the correct insight: prioritize the highest values while enforcing label limits with a simple counter. Implementing the heap version shows familiarity with priority queues, but sorting is shorter, easier to reason about, and typically preferred during coding rounds.