Compute maximum distinct-product pickup days
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
##### Question
Given an array of positive integers representing quantities of different products, on day i (starting from
1) you must pick exactly i distinct products, taking one unit from each chosen product. After each pick the chosen products' quantities decrease by 1 and cannot go below 0. Compute the maximum number of days the process can continue.
Quick Answer: This question evaluates a candidate's understanding of greedy and resource-allocation strategies along with combinatorial reasoning to maximize operations under discrete constraints.
You are given an array quantities of positive integers, where quantities[i] is the number of units of product i. Starting from day 1, on day d you must pick exactly d distinct products (if possible), taking one unit from each picked product. After each day's picks, the chosen products' quantities each decrease by 1 and never go below 0. You may choose which products to pick each day to maximize the number of days. Return the maximum number of consecutive days (starting from day 1) the process can continue.
Constraints
- 1 <= len(quantities) <= 2e5
- 1 <= quantities[i] <= 1e9
- Sum of quantities <= 2e5
- Answer is at most len(quantities)
Solution
from typing import List
import heapq
def max_distinct_pickup_days(quantities: List[int]) -> int:
# Build a max-heap using negative values
heap = [-q for q in quantities if q > 0]
heapq.heapify(heap)
day = 1
while True:
if len(heap) < day:
return day - 1
taken = []
for _ in range(day):
if not heap:
return day - 1
c = heapq.heappop(heap) # c is negative
c += 1 # decrement absolute count by 1
taken.append(c)
for c in taken:
if c < 0: # still has remaining units
heapq.heappush(heap, c)
day += 1
Explanation
Use a max-heap (priority queue) to always pick from the largest remaining quantities, preserving as many positive counts as possible for future days. On day d, if fewer than d positive quantities remain, no valid selection exists and the process stops. Otherwise, pop the top d counts, decrement each by 1, and push back any that remain positive. This greedy strategy is optimal by exchange: replacing any pick from a smaller count with a larger one cannot reduce future feasibility because it keeps the number of positive entries at least as high as before.
Time complexity: O(S log n), where S = sum(quantities) and n = len(quantities). Space complexity: O(n).
Hints
- On day d you need at least d products with positive remaining quantities.
- Greedily take one unit from the d largest available quantities each day.
- A max-heap efficiently retrieves the largest counts at each step.
- Stop when the heap has fewer than d elements.