Verify Promo Bundle Inventory Coverage

Problem Narrative

You’re building a promotion engine for a high-traffic e-commerce marketplace (millions of DAUs). During flash sales, the system must quickly verify whether a fulfillment center can assemble a promo bundle from its current inventory. A wrong “yes” can cause overselling and cancellations; a wrong “no” can suppress revenue.

Task

Implement a function:

• Input:
  • haystack: a list of items currently in inventory (may contain duplicates)
  • needle: a list of items required to assemble one promo bundle (may contain duplicates)
• Output:
  • Return True if haystack contains every item in needle with at least the same multiplicity.
  • Otherwise return False.

Items are represented as strings (e.g., SKU codes). Order does not matter.

Formally, for every distinct item x, let count(A, x) be the number of occurrences of x in list A. You must return True iff:

• For all items x: count(haystack, x) >= count(needle, x)

Constraints

• 0 <= haystack.length, needle.length <= 2 * 10^5
• Each item is a non-empty string of length 1..30
• Total input size is large enough that an O(n·m) approach may time out.

Notes / Clarifications

1. If needle is empty, return True.
2. If haystack is empty and needle is non-empty, return False.
3. You may assume strings are case-sensitive ("SKU1" != "sku1").