BinarySearch 1028 Validate Delivery Orders

Problem statement

https://binarysearch.com/problems/Validate-Delivery-Orders/

Solution

For each order number keep all places we have it. Also use trick where we use positive indexes for P and negative for D.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, orders):
        d = defaultdict(list)
        for i, x in enumerate(orders):
            sgn = 1 if x[0] == "P" else -1
            d[int(x[1:])] += [sgn * (i + 1)]

        for x in d:
            if len(d[x]) != 2 or d[x][0] < 0 or d[x][1] > 0: return False
        return True