from typing import List


def remove_element(arr: List[int], key: int) -> int:
    """
    Time Complexity: O(len(arr))
    Space Complexity: O(1)

    :param arr: input array
    :param key: target key
    :return: the new length of the array after removing all instances of 'key' in-place
    """
    p1 = 0
    for p2 in range(len(arr)):
        if arr[p2] != key:
            arr[p1] = arr[p2]
            p1 += 1
    return p1