New Year Chaos

  • + 0 comments

    Iterate from right to left, if you have seen 3 values lower than the current it's too chaotic, othewise add the seen list index to the bribe count.

    • j = 0, the value is smaller than any seen
    • j = 1, you have seen one value smaller
    • j = 2, you have seen 2 values smaller
    • j = 3 you have seen at least 3 values smaller, which is not valid.

    bisect used to maintain order, only need to keep the 3 smallest values seen.

    from bisect import bisect_left
    
    def minimumBribes(q):
        
        bribes = 0
        seen = []
        for i in range(len(q)-1, -1, -1):
            v = q[i]
            j = bisect_left(seen, v)
            if j >= 3:
                print('Too chaotic')
                return
            bribes += j
            seen.insert(j, v)
            seen = seen[:3]
                 
        print(bribes)