Quick Overview

This question evaluates a candidate's understanding of greedy and resource-allocation strategies along with combinatorial reasoning to maximize operations under discrete constraints.

Compute maximum distinct-product pickup days

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

##### 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.

Overview: 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)

Hints

  1. On day d you need at least d products with positive remaining quantities.
  2. Greedily take one unit from the d largest available quantities each day.
  3. A max-heap efficiently retrieves the largest counts at each step.
  4. Stop when the heap has fewer than d elements.

Loading coding console...

Show the approach

Approach

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)