FastPrep
Problem · Hash Table

Max Book Copies 🫐

● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Amazon maintains an inventory portal where booksellers can add or remove copies of books. The updates are given in an integer array portalUpdate.

  • If portalUpdate[i] is positive, one copy of the book with id portalUpdate[i] is added to the inventory.
  • If portalUpdate[i] is negative, one copy of the book with id |portalUpdate[i]| is removed from the inventory. Each removal is guaranteed to be valid: the inventory contains at least one copy of that book before the removal.
  • portalUpdate[i] is never zero.

After each update, record the maximum number of copies held by any single book id. If the inventory is empty, the maximum is 0.

Return an array containing this maximum after every update.

Examples
01 · Example 1
portalUpdate = [6, 6, 2, -6, -2, -6]
return = [1, 2, 2, 1, 1, 0]
Example 1 illustration

The inventory changes as follows:

  • After 6: book 6 has 1 copy, maximum is 1.
  • After 6: book 6 has 2 copies, maximum is 2.
  • After 2: book 6 has 2 copies and book 2 has 1 copy, maximum is 2.
  • After -6: book 6 and book 2 each have 1 copy, maximum is 1.
  • After -2: book 6 has 1 copy, maximum is 1.
  • After -6: the inventory is empty, maximum is 0.
02 · Example 2
portalUpdate = [1, 2, -1, 2]
return = [1, 1, 1, 2]

After update 1, the maximum count is 1. After update 2, books 1 and 2 each have 1 copy, so the maximum remains 1. After update -1, only book 2 remains with 1 copy. After the final update 2, book 2 has 2 copies, so the maximum is 2.

Constraints
  • 1 <= n <= 106
  • -109 <= portalUpdate[i] <= 109
  • portalUpdate[i] != 0
  • Every negative update removes a copy that is currently present in the inventory.
More Amazon problems
drafts saved locally
public int[] maximumBookCopies(int[] portalUpdate) {
    // write your code here
}
portalUpdate[6, 6, 2, -6, -2, -6]
expected[1, 2, 2, 1, 1, 0]
checking account