Delete Operations

01 · Question

You're given an array of n integers, nums, and another array of at most n integers, operations, where each integer represents an operation to be performed on nums.

If the operation number is k >= 0, the operation is "delete the number at index k in the original array if it has not been deleted yet. Otherwise, do nothing."
If the operation number is -1, the operation is "delete the smallest number in nums that has not been deleted yet, breaking ties by smaller index."

Return the state of nums after applying all the operations. Every number in operations is guaranteed to be between -1 and n-1, included.

Example:

Input: nums = [50, 30, 70, 20, 80], operations = [2, -1, 4, -1]
Output: [50]

02 · Analysis

Heap entries retain original indices, so deletions never change the meaning of a later operation. Mark index deletions immediately; before deleting a minimum, pop entries whose indices are already marked. Each entry becomes stale and is popped at most once. Finally scan the original array to preserve order. For n values and q operations, heapify plus processing takes O(n + q log(n+1)) total time and O(n) auxiliary space; q <= n here.

03 · Solution

Reference solution

1import heapq
2
3def deleteOperations(nums: List[int], operations: List[int]) -> List[int]:
4    deleted = set()
5    heap = [(x, i) for i, x in enumerate(nums)]
6
7    # Keep original indices; build the heap in linear time.
8    heapq.heapify(heap)
9
10    for op in operations:
11        if op >= 0:
12            deleted.add(op)
13        else:
14            # Lazy deletion: pop from heap until we find a non-deleted element
15            while heap:
16                val, idx = heap[0]
17                if idx in deleted:
18                    heapq.heappop(heap)
19                else:
20                    heapq.heappop(heap)
21                    deleted.add(idx)
22                    break
23
24    return [x for i, x in enumerate(nums) if i not in deleted]

K Closest Points to Origin

Merge Sorted Streams