Solve Two OA Algorithm Problems

The post describes two separate coding questions from an online assessment:

1. Greedy deletion by minimum value Given an integer array nums, repeatedly perform the following operation until every element has been deleted:

• Among all undeleted elements, choose the one with the smallest value. If multiple elements have the same value, choose the leftmost one.
• Add its value to the answer.
• Delete that element and its immediate neighbors in the original array (i - 1 and i + 1) if those neighbors have not already been deleted.

Return the final accumulated answer.

2. Minimum emergency refill days You manage a warehouse with capacity max_products and initial inventory 0. On day i, the inventory changes by task[i] at the end of the day. Before processing a day, you may perform an emergency refill and increase the inventory by any amount, as long as the inventory after the refill does not exceed max_products. Using a refill on a day counts as one refill day regardless of how much inventory you add.

Constraints:

• After each day, inventory must never exceed max_products.
• On days where task[i] == 0, the end-of-day inventory must be non-negative.
• On other days, negative inventory is temporarily allowed.

Return the minimum number of refill days needed to satisfy all constraints, or -1 if no valid plan exists.

Part 1: Greedy Deletion by Minimum Value

You are given an integer array nums. Repeatedly perform the following operation until every element has been deleted: choose the undeleted element with the smallest value; if several undeleted elements share that value, choose the leftmost one. Add its value to the answer, then delete that element and its immediate neighbors in the original array (index i - 1 and i + 1) if they have not already been deleted. Return the final accumulated answer.

Constraints

• 0 <= len(nums) <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9
• Use 64-bit arithmetic in fixed-width languages because the sum can exceed 32-bit range.

Examples

Example 1

Input: ([3, 1, 5, 2, 4],)
Output: 3

Explanation: Pick 1 at index 1, deleting indices 0, 1, 2. Then pick 2 at index 3, deleting indices 3 and 4. Total = 1 + 2 = 3.

Example 2

Input: ([1, 1, 1],)
Output: 2

Explanation: Tie-breaking chooses the leftmost 1 first, deleting indices 0 and 1. The remaining 1 at index 2 is then chosen. Total = 2.

Hints

1. The next chosen element depends only on value and original index, so consider processing elements in sorted order.
2. Instead of physically removing items from the array, keep a boolean array that marks whether each index has already been deleted.

Part 2: Minimum Emergency Refill Days

A warehouse has capacity max_products and starts with inventory 0. On day i, the inventory changes by task[i] at the end of the day. Before a day starts, you may perform at most one emergency refill and increase the inventory by any amount, as long as the inventory immediately after the refill does not exceed max_products. Using a refill on a day counts as one refill day no matter how much you add. The rules are: inventory must never exceed max_products, either after a refill or after the day's change; on days where task[i] == 0, the end-of-day inventory must be non-negative; on days where task[i] != 0, negative end-of-day inventory is allowed. Return the minimum number of refill days needed, or -1 if no valid plan exists.

Constraints

• 0 <= len(task) <= 2 * 10^5
• 1 <= max_products <= 10^9
• -10^9 <= task[i] <= 10^9
• Use 64-bit arithmetic for prefix sums and bounds in fixed-width languages.

Examples

Example 1

Input: (10, [-3, 0, -3, 0])
Output: 1

Explanation: Refill once on the first zero day to the maximum safe level. That single refill keeps the later zero day non-negative as well.

Example 2

Input: (5, [-1, 0, 5, -8, 0])
Output: 2

Explanation: The +5 day limits how much inventory can safely be carried early, so one refill is needed at the first zero day and another at the last zero day.

Hints

1. Let prefix[i] be the sum of task[0] through task[i]. If the total refill amount used so far is R, then the inventory after day i is R + prefix[i].
2. When a zero-day forces more inventory, it is optimal to refill on that day and raise R to the largest value that is still safe for all remaining days.