LeetCode 3052 - Maximize Items

The problem requires determining how many items can be stored in a warehouse with a limited square footage of 500,000. T

leetcodeharddatabase

LeetCode Problem 3052

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem requires determining how many items can be stored in a warehouse with a limited square footage of 500,000. The items are categorized as either prime_eligible or not_prime. The goal is to first maximize the number of prime_eligible items stored, then use any remaining space to store as many not_prime items as possible. Each item has a specific square_footage, and the total count of each type is determined by how many complete items of that type can fit in the warehouse space.

The input is a table Inventory with four columns: item_id (unique identifier), item_type (prime_eligible or not_prime), item_category (the type of item, e.g., Watches, Shoes), and square_footage (the space one item occupies). The output is a table with two columns: item_type and item_count, showing the maximum number of items of each type that can fit, ordered by descending item_count. If no not_prime items fit, the count must still be reported as 0.

Important edge cases include when all items are prime_eligible, when all items are not_prime, or when individual items have square_footage larger than the total warehouse space. The problem guarantees valid positive square_footage values, and we need to account for integer counts only.

Approaches

A brute-force approach would attempt every possible combination of items to maximize the count within the warehouse space. This would involve generating all combinations for prime_eligible items first, then repeating the same for not_prime items. While correct, this method is computationally infeasible for larger datasets because it has exponential time complexity due to combinatorial explosion.

The key insight for an optimal solution is to treat this as a variation of the unbounded knapsack problem. Since we can take multiple instances of the same item type, we sum the square footage of all items of a given type and calculate how many complete repetitions fit in the warehouse. Once the prime_eligible allocation is done, the remaining space is used to fit as many not_prime items as possible. Sorting items by square_footage is unnecessary because the warehouse can take multiple repetitions of the same item.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Generate all combinations of items for each type, too slow
Optimal O(n) O(1) Calculate total square footage per type and fit as many repetitions as possible

Algorithm Walkthrough

  1. Aggregate square footage by type: Compute the sum of square_footage for all prime_eligible items and separately for not_prime items. This represents the square footage of one full set of each type.
  2. Calculate repetitions for prime items: Determine how many times the prime_eligible set can fit into the warehouse by integer division of 500,000 by the total square footage of the set. Multiply the number of items in the set by this repetition count to get prime_eligible item count.
  3. Calculate remaining space: Subtract the total space occupied by prime_eligible items from 500,000 to get the remaining warehouse space.
  4. Calculate repetitions for non-prime items: Using the remaining space, determine how many times the not_prime set can fit. Multiply the number of items in the set by this repetition count to get the not_prime item count. If the remaining space is insufficient, set the count to 0.
  5. Prepare output: Return a table with item_type and item_count, ordered by item_count descending.

Why it works: The algorithm works because it uses integer division to compute how many full sets of items can fit. Since we are allowed to repeat items, the unbounded knapsack model guarantees the maximum number of items without violating the total warehouse space.

Python Solution

import pandas as pd

def maximize_items(inventory: pd.DataFrame) -> pd.DataFrame:
    WAREHOUSE_SPACE = 500_000
    
    prime_items = inventory[inventory['item_type'] == 'prime_eligible']
    non_prime_items = inventory[inventory['item_type'] == 'not_prime']
    
    prime_count = len(prime_items)
    prime_space = prime_items['square_footage'].sum()
    if prime_space == 0:
        total_prime_count = 0
    else:
        repetitions = int(WAREHOUSE_SPACE // prime_space)
        total_prime_count = repetitions * prime_count
    
    remaining_space = WAREHOUSE_SPACE - (repetitions * prime_space if prime_space else 0)
    
    non_prime_count = len(non_prime_items)
    non_prime_space = non_prime_items['square_footage'].sum()
    if non_prime_space == 0 or remaining_space <= 0:
        total_non_prime_count = 0
    else:
        repetitions = int(remaining_space // non_prime_space)
        total_non_prime_count = repetitions * non_prime_count
    
    result = pd.DataFrame({
        'item_type': ['prime_eligible', 'not_prime'],
        'item_count': [total_prime_count, total_non_prime_count]
    })
    result = result.sort_values(by='item_count', ascending=False).reset_index(drop=True)
    
    return result

The Python implementation first separates items by type, calculates total space, determines repetitions within the warehouse, then computes the total count of items. Sorting ensures the descending order requirement is met.

Go Solution

package main

import (
    "fmt"
    "sort"
)

type Item struct {
    ItemID        int
    ItemType      string
    ItemCategory  string
    SquareFootage float64
}

type Result struct {
    ItemType  string
    ItemCount int
}

func MaximizeItems(inventory []Item) []Result {
    WAREHOUSE_SPACE := 500000.0

    var primeItems, nonPrimeItems []Item
    for _, item := range inventory {
        if item.ItemType == "prime_eligible" {
            primeItems = append(primeItems, item)
        } else {
            nonPrimeItems = append(nonPrimeItems, item)
        }
    }

    primeSpace, primeCount := 0.0, len(primeItems)
    for _, item := range primeItems {
        primeSpace += item.SquareFootage
    }
    totalPrimeCount := 0
    repetitions := 0.0
    if primeSpace > 0 {
        repetitions = WAREHOUSE_SPACE / primeSpace
        totalPrimeCount = int(repetitions) * primeCount
    }

    remainingSpace := WAREHOUSE_SPACE - (float64(int(repetitions)) * primeSpace)

    nonPrimeSpace, nonPrimeCount := 0.0, len(nonPrimeItems)
    for _, item := range nonPrimeItems {
        nonPrimeSpace += item.SquareFootage
    }
    totalNonPrimeCount := 0
    if nonPrimeSpace > 0 && remainingSpace > 0 {
        repetitions = remainingSpace / nonPrimeSpace
        totalNonPrimeCount = int(repetitions) * nonPrimeCount
    }

    results := []Result{
        {"prime_eligible", totalPrimeCount},
        {"not_prime", totalNonPrimeCount},
    }
    sort.Slice(results, func(i, j int) bool {
        return results[i].ItemCount > results[j].ItemCount
    })

    return results
}

The Go solution mirrors the Python approach, taking care with type conversions and float arithmetic. Slices are used to collect items, and sorting ensures descending order by count.

Worked Examples

Example Input

item_id item_type item_category square_footage
1374 prime_eligible Watches 68.00
4245 not_prime Art 26.40
5743 prime_eligible Software 325.00
8543 not_prime Clothing 64.50
2556 not_prime Shoes 15.00
2452 prime_eligible Scientific 85.00
3255 not_prime Furniture 22.60
1672 prime_eligible Beauty 8.50
4256 prime_eligible Furniture 55.50
6325 prime_eligible Food 13.20

Step 1: Sum prime_eligible square footage = 68 + 325 + 85 + 8.5 + 55.5 + 13.2 = 555.2

Step 2: Calculate repetitions in warehouse = 500,000 // 555.2 = 900

Step 3: Total prime_eligible items = 900 * 6 = 5400

Step 4: Remaining space = 500,000 - 900*555.2 = 320

Step 5: Sum not_prime square footage = 26.4 + 64.5 + 15 + 22.6 = 128.5

Step 6: Repetitions in remaining space = 320 // 128.5 = 2

**Step