Maximize Items

Problem

Table: Inventory

+----------------+---------+
| Column Name    | Type    |
+----------------+---------+
| item_id        | int     |
| item_type      | varchar |
| item_category  | varchar |
| square_footage | decimal |
+----------------+---------+
item_id is the column of unique values for this table.
Each row includes item id, item type, item category and sqaure footage.

Leetcode warehouse wants to maximize the number of items it can stock in a 500,000 square feet warehouse. It wants to stock as many prime items as possible, and afterwards use the remaining square footage to stock the most number of non-prime items.

Write a solution to find the number of prime and non-prime items that can be stored in the 500,000 square feet warehouse. Output the item type with prime_eligible followed by not_prime and the maximum number of items that can be stocked.

Note:

Item count must be a whole number (integer).
If the count for the not_prime category is 0, you should output 0 for that particular category.

Return the result table ordered by item count indescending order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


Input: 
Inventory table:
+---------+----------------+---------------+----------------+
| 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          | 
+---------+----------------+---------------+----------------+
Output: 
+----------------+-------------+
| item_type      | item_count  | 
+----------------+-------------+
| prime_eligible | 5400        | 
| not_prime      | 8           | 
+----------------+-------------+
Explanation: 
- The prime-eligible category comprises a total of 6 items, amounting to a combined square footage of 555.20 (68 + 325 + 85 + 8.50 + 55.50 + 13.20). It is possible to store 900 combinations of these 6 items, totaling 5400 items and occupying 499,680 square footage.
- In the not_prime category, there are a total of 4 items with a combined square footage of 128.50. After deducting the storage used by prime-eligible items (500,000 - 499,680 = 320), there is room for 2 combinations of non-prime items, accommodating a total of 8 non-prime items within the available 320 square footage.
Output table is ordered by item count in descending order.

Solution

Method 1 – Greedy Knapsack with Sorting

Intuition

To maximize the number of items, we first fill the warehouse with as many prime items as possible (since they have priority), starting from the smallest square footage. Then, with the remaining space, we fill with as many non-prime items as possible, again starting from the smallest.

Approach

Select all items with item_type = 'prime_eligible' and sort them by square_footage ascending.
Select all items with item_type = 'not_prime' and sort them by square_footage ascending.
Greedily add prime items until the warehouse is full or no more prime items can fit.
Use the remaining space to add as many non-prime items as possible.
Output the count of each type.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


WITH prime_items AS (
  SELECT item_id, square_footage
  FROM Inventory
  WHERE item_type = 'prime_eligible'
  ORDER BY square_footage
),
not_prime_items AS (
  SELECT item_id, square_footage
  FROM Inventory
  WHERE item_type = 'not_prime'
  ORDER BY square_footage
),
prime_acc AS (
  SELECT item_id, square_footage,
         SUM(square_footage) OVER (ORDER BY square_footage) AS acc_sqft,
         ROW_NUMBER() OVER (ORDER BY square_footage) AS rn
  FROM prime_items
),
max_prime AS (
  SELECT MAX(rn) AS cnt, COALESCE(MAX(acc_sqft),0) AS used_sqft
  FROM prime_acc
  WHERE acc_sqft <= 500000
),
not_prime_acc AS (
  SELECT item_id, square_footage,
         SUM(square_footage) OVER (ORDER BY square_footage) AS acc_sqft,
         ROW_NUMBER() OVER (ORDER BY square_footage) AS rn
  FROM not_prime_items
),
max_non_prime AS (
  SELECT MAX(rn) AS cnt
  FROM not_prime_acc, max_prime
  WHERE acc_sqft <= 500000 - max_prime.used_sqft
)
SELECT 'prime_eligible' AS item_type, COALESCE(max_prime.cnt,0) AS items_stocked FROM max_prime
UNION ALL
SELECT 'not_prime', COALESCE(max_non_prime.cnt,0) FROM max_non_prime;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


WITH prime_items AS (
  SELECT item_id, square_footage
  FROM Inventory
  WHERE item_type = 'prime_eligible'
  ORDER BY square_footage
),
not_prime_items AS (
  SELECT item_id, square_footage
  FROM Inventory
  WHERE item_type = 'not_prime'
  ORDER BY square_footage
),
prime_acc AS (
  SELECT item_id, square_footage,
         SUM(square_footage) OVER (ORDER BY square_footage) AS acc_sqft,
         ROW_NUMBER() OVER (ORDER BY square_footage) AS rn
  FROM prime_items
),
max_prime AS (
  SELECT MAX(rn) AS cnt, COALESCE(MAX(acc_sqft),0) AS used_sqft
  FROM prime_acc
  WHERE acc_sqft <= 500000
),
not_prime_acc AS (
  SELECT item_id, square_footage,
         SUM(square_footage) OVER (ORDER BY square_footage) AS acc_sqft,
         ROW_NUMBER() OVER (ORDER BY square_footage) AS rn
  FROM not_prime_items
),
max_non_prime AS (
  SELECT MAX(rn) AS cnt
  FROM not_prime_acc, max_prime
  WHERE acc_sqft <= 500000 - max_prime.used_sqft
)
SELECT 'prime_eligible' AS item_type, COALESCE(max_prime.cnt,0) AS items_stocked FROM max_prime
UNION ALL
SELECT 'not_prime', COALESCE(max_non_prime.cnt,0) FROM max_non_prime;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def maximize_items(df: 'pd.DataFrame') -> dict:
    df_prime = df[df['item_type'] == 'prime_eligible'].sort_values('square_footage')
    df_non_prime = df[df['item_type'] == 'not_prime'].sort_values('square_footage')
    sqft = 0
    cnt_prime = 0
    for sf in df_prime['square_footage']:
        if sqft + sf > 500000:
            break
        sqft += sf
        cnt_prime += 1
    cnt_non_prime = 0
    for sf in df_non_prime['square_footage']:
        if sqft + sf > 500000:
            break
        sqft += sf
        cnt_non_prime += 1
    return {'prime_eligible': cnt_prime, 'not_prime': cnt_non_prime}

Complexity

⏰ Time complexity: O(n log n) — for sorting both groups.
🧺 Space complexity: O(n) — for storing sorted lists.

Problem#

Examples#

Solution#

Method 1 – Greedy Knapsack with Sorting#

Intuition#

Approach#

Code#

Complexity#