Largest Values From Labels - Practice Coding Problems

Largest Values From Labels - Problem

You are given n items with their values and labels as two integer arrays values and labels. You are also given two integers numWanted and useLimit.

Your task is to find a subset of items with the maximum sum of their values such that:

The number of items is at most numWanted
The number of items with the same label is at most useLimit

Return the maximum sum.

Input & Output

Example 1 — Basic Selection

$ Input: values = [5,4,3,2], labels = [1,0,0,1], numWanted = 3, useLimit = 1

› Output: 9

💡 Note: Sort by values: (5,1), (4,0), (3,0), (2,1). Pick (5,1) and (4,0). Can't pick (3,0) because label 0 already used once. Result: 5+4=9

Example 2 — Constraint Limiting

$ Input: values = [5,4,3,2], labels = [1,0,0,1], numWanted = 2, useLimit = 1

› Output: 9

💡 Note: Same sorting, but numWanted=2 limits us to 2 items. Pick highest values (5,1) and (4,0). Result: 5+4=9

Example 3 — High Use Limit

$ Input: values = [9,8,8,7], labels = [0,0,0,1], numWanted = 3, useLimit = 2

› Output: 25

💡 Note: Sort: (9,0), (8,0), (8,0), (7,1). Pick first 3: 9+8+8=25. useLimit=2 allows 2 items with label 0

Constraints

1 ≤ values.length == labels.length ≤ 2 × 10⁴
0 ≤ values[i], labels[i] ≤ 2 × 10⁴
1 ≤ numWanted, useLimit ≤ values.length

Visualization

Tap to expand

Understanding the Visualization

Input

Items with values and labels, plus constraints

Process

Sort by value and greedily select best items

Output

Maximum possible sum

Key Takeaway

🎯 Key Insight: Greedy selection works because we want maximum value and constraints are independent - sort by value and pick greedily

Asked in

G Google 15 a Amazon 12

The key insight is to use a greedy approach: sort items by value in descending order and pick the highest value items while respecting label usage and total count constraints. Best approach is Greedy Selection with Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n)	O(n)	Generate all possible subsets and find the one with maximum sum that satisfies constraints
Greedy Approach - Sort by Value	O(n log n)	O(n)	Sort items by value in descending order, then greedily pick highest value items while respecting constraints

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all possible subsets of items
Step 2: For each subset, check if it satisfies numWanted and useLimit constraints
Step 3: Track the maximum sum among valid subsets

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^n possible combinations

Check Constraints

Validate numWanted and useLimit for each subset

Track Maximum

Keep the highest sum among valid subsets

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ITEMS 100
#define MAX_LABELS 1000

int solution(int* values, int* labels, int n, int numWanted, int useLimit) {
    int maxSum = 0;
    
    // Try all possible subsets using bit manipulation
    for (int mask = 0; mask < (1 << n); mask++) {
        int subsetSum = 0;
        int itemCount = 0;
        int labelCount[MAX_LABELS] = {0};
        int valid = 1;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                itemCount++;
                labelCount[labels[i]]++;
                subsetSum += values[i];
                
                // Check constraints
                if (itemCount > numWanted || labelCount[labels[i]] > useLimit) {
                    valid = 0;
                    break;
                }
            }
        }
        
        if (valid && subsetSum > maxSum) {
            maxSum = subsetSum;
        }
    }
    
    return maxSum;
}

int main() {
    char line[1000];
    int values[MAX_ITEMS], labels[MAX_ITEMS];
    int n = 0;
    
    // Parse values array
    fgets(line, sizeof(line), stdin);
    char* ptr = strchr(line, '[') + 1;
    char* end = strchr(line, ']');
    *end = '\0';
    char* token = strtok(ptr, ",");
    while (token != NULL) {
        values[n++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    // Parse labels array
    int labelCount = 0;
    fgets(line, sizeof(line), stdin);
    ptr = strchr(line, '[') + 1;
    end = strchr(line, ']');
    *end = '\0';
    token = strtok(ptr, ",");
    while (token != NULL) {
        labels[labelCount++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    int numWanted, useLimit;
    scanf("%d", &numWanted);
    scanf("%d", &useLimit);
    
    printf("%d\n", solution(values, labels, n, numWanted, useLimit));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Generate 2^n subsets, each taking O(n) time to validate constraints

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and temporary storage for subset validation

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler