O(n) Python; 2 pointers


  • 0
    Y

    The invariant is that everything to the right of i is q. To maintain this invariant, when i finds q, j hunts for the next q to swap with i.

    def remove_element(xs, q):
        # https://leetcode.com/problems/remove-element/description/
        n = len(xs)
        i = j = n-1
        while min(i, j) >= 0:
            if xs[i] != q:
                j = i-1
                while j >= 0 and xs[j] != q:
                    j -= 1
                if j == -1:
                    break
                else:
                    xs[j] = xs[i]
            i -= 1
        return i+1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.