Asked in: AMAZON
Image of the Question
All Testcases Passed ✔
Solution
def orderBooks(volumes):
answer = []
visited = set()
cnt = 1
// ... rest of solution available after purchaseExplanation
```
To solve this problem, you need to simulate the process of volumes becoming available over n days, and on each day decide which volumes can be purchased based on the prequel condition. The goal is to output what volumes are bought each day, following the rules strictly.
Here is a detailed approach to think through this problem:
1. **Understanding the problem context:**
You have n volumes numbered 1 to n, all out of stock initially. On day i, exactly one new volume becomes available (given by volumes[i]). You can only purchase volumes if you have all their prequels already purchased. Prequels for volume x are all volumes with numbers less than x.
2. **The core condition for purchase:**
You can buy a volume only if you already own all volumes with numbers less than it. This means you cannot jump ahead and buy volume 5 without owning volumes 1 through 4 first. Also, you want to buy the maximum number of volumes possible each day, meaning if multiple volumes are now purchasable, buy all of them immediately.
3. **Key observations:**
- The volumes become available in a certain order (not necessarily sorted).
- You can only buy volumes consecutively starting from volume 1, moving upward, without gaps.
- When a volume becomes available, you may or may not be able to buy it immediately depending on whether its prequels are already purchased.
- Sometimes you have to wait several days before you can buy certain volumes because the earlier volumes are not yet available or purchased.
4. **How to track purchased volumes and availability:**
You need to keep track of which volumes have become available but are not yet purchased (because their prequels are missing).
You also need to track the next volume number you expect to purchase. Initially, this will be volume 1, as you must start from the first volume.
5. **Step-by-step simulation:**
For each day i from 1 to n:
- Mark the newly available volume as available.
- Check if the volume number corresponds to the "next expected volume to buy" or if it unlocks a chain of purchasable volumes.
- From the next expected volume, check how many consecutive volumes are now available. You can purchase all these consecutive volumes in one go.
- Update the next expected volume to be the one after the last purchased volume.
- Record the purchased volumes for the day or record [-1] if none are purchased.
6. **Data structures to help:**
- A boolean array or set to mark which volumes are available but not yet purchased.
- An integer pointer to track the next volume expected to buy (starting at 1).
- On each day, after adding the newly available volume, try to advance this pointer as far as possible, purchasing all consecutive available volumes.
7. **Algorithmic complexity:**
- Each volume is considered once when it becomes available and once when it is purchased.
- Checking consecutive available volumes can be done efficiently by moving the pointer forward until a volume is missing.
- Overall complexity is O(n), which is efficient for up to 10^5 volumes.
8. **Example walkthrough:**
Consider volumes = [2, 1, 4, 3] for n=4:
- Day 1: Volume 2 available. Next expected volume to buy is 1, but volume 1 not available yet, so cannot buy 2. Result: [-1]
- Day 2: Volume 1 available. Now volumes 1 and 2 are both available and consecutive starting from 1. Purchase both. Result: [1, 2]
- Day 3: Volume 4 available. Next expected volume to buy is 3, but 3 not available yet, so cannot buy 4. Result: [-1]
- Day 4: Volume 3 available. Now volumes 3 and 4 are both available and consecutive starting from 3. Purchase both. Result: [3, 4]
9. **Edge cases to consider:**
- Volumes arriving in perfect ascending order: you buy one volume each day.
- Volumes arriving in descending order: you buy none until the first volume arrives, then buy all remaining in one go.
- Large n with scattered arrivals: the approach still applies efficiently.
10. **Summary:**
The problem boils down to simulating availability day by day, keeping track of the next volume you can buy, and buying as many consecutive volumes as possible starting from that point whenever possible. Maintaining a data structure to track availability and a pointer for the next expected volume lets you implement this efficiently and correctly.
By focusing on these steps and the idea of purchasing consecutive volumes starting from the smallest missing volume, you can solve the problem reliably.
```