Queue from which first occurrences may be removed

Question

I participated in an Amazon coding challenge, and one of the questions was a really simple one. To paraphrase:

Develop a method to handle shopping carts that takes two inputs, items being the current shopping cart which is an array of product IDs, and queue being the operation IDs to apply to the shopping cart.

If the ID is positive, append the product ID to the end of the cart, if the ID is negative, remove the first instance of the absolute value of the ID from the shopping cart. Return the processed shopping cart.

I implemented a simple solution, and it passed all the simple test cases, however it failed all the test cases with large inputs. I ended up not having time to come up with a more efficient solution, my best being O(n²) I think:

def problem_solution(items: list[int], query: list[int]) -> list[int]:
    for item in query:
        if item > 0:
            items.append(item)
            
        else:
            items.remove(abs(item))
            
    return items

I thought about using either a collections.deque or collections.defaultdict, but couldn't see how to really improve the efficiency. What am I missing here?

Answer 1

One idea would be to delay the deletions until all queries have been processed, and only register how many of each value should be deleted (in a dict).

Then, after processing the queries, iterate the collected items, and as long as the current value should be deleted, skip it and at the same time decrease the deletion-count we have for that item. You could do this inplace, in the items list, and shift values to the left as you visit them. At the end, truncate the list:

from collections import defaultdict

def problem_solution(items: list[int], query: list[int]) -> list[int]:
    deleted_count = defaultdict(int)
    for item in query:
        if item > 0:
            items.append(item)
        else:
            deleted_count[-item] += 1
    i = 0
    for item in items:
        if deleted_count.get(item, 0) > 0:
            deleted_count[item] -= 1
        else:
            items[i] = item
            i += 1
    del items[i:]
    return items

NB: As this mutates the items given as argument, it should not be necessary to actually return it.