Delete Operations

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]
1import heapq
2

3def deleteOperations(nums: List[int], operations: List[int]) -> List[int]:
4    deleted = set()
5    heap = []
6    # Store (value, index) in heap
7    for i, x in enumerate(nums):
8        heapq.heappush(heap, (x, i))
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]
Previous
K Closest Points to Origin
50
0
30
1
70
2
20
3
80
4
deleted=[]
Step 1 / 6
Step 1:
Init heap with (val, idx) and empty deleted set.
Focus: default