Remove element in-place

_readme.md

https://leetcode.com/problems/remove-element/description/

This was interesting: I made this problem a lot harder by trying to move the "to remove" elements to the end instead of moving the "to keep" elements to the beginning.

I found my idea hard to implement iteratively, and I had to switch to recursion to get it working. After that, I was able to convert my solution to iterative -- but it would've been pretty hard to implement this approach iteratively from the start!

But if we move "to keep" elements to the beginning instead, this problem is really simple iteratively.

• solution1: My tricky recursive solution
• solution2: My tricky iterative solution based on solution1
• solution3: The easy iterative solution

solution1.py

#!/usr/bin/env python3.12
from typing import List


class Solution:
    def removeElement(self, *args, **kwargs):
        return removeElement(*args, **kwargs)


def removeElement(nums: List[int], val: int) -> int:
    return helper(nums, val, 0, len(nums) - 1)


def helper(nums, val, lo, hi):
    size = hi - lo + 1

    if size == 0:
        return lo
    if size == 1:
        if nums[lo] != val:
            return lo + 1
        else:
            return lo

    assert size > 1
    if nums[lo] != val:
        return helper(nums, val, lo + 1, hi)
    elif nums[lo] == val and nums[hi] != val:
        nums[lo], nums[hi] = nums[hi], nums[lo]
        return helper(nums, val, lo + 1, hi - 1)
    elif nums[lo] == val and nums[hi] == val:
        return helper(nums, val, lo, hi - 1)
    else:
        raise Exception('unreachable case')

solution2.py

#!/usr/bin/env python3.12
from typing import List


class Solution:
    def removeElement(self, *args, **kwargs):
        return removeElement(*args, **kwargs)


def removeElement(nums: List[int], val: int) -> int:
    lo = 0
    hi = len(nums) - 1

    while (size := hi - lo + 1) > 1:
        if nums[lo] != val:
            lo += 1
        elif nums[lo] == val and nums[hi] != val:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1
            hi -= 1
        elif nums[lo] == val and nums[hi] == val:
            hi -= 1
        else:
            raise Exception('unreachable case')

    if size == 0:
        return lo

    if size == 1:
        if nums[lo] != val:
            return lo + 1
        else:
            return lo

solution3.py

# Copied from https://leetcode.com/problems/remove-element/solutions/3670940/best-100-c-java-python-beginner-friendly/
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        index = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[index] = nums[i]
                index += 1
        return index

tests.py

def test(nums, val, expected_size, expected_elements):
    actual_size = removeElement(nums, val)
    if actual_size != expected_size:
        print(f'Fail: {actual_size=} {expected_size=}')
        return

    actual_elements = sorted(nums[:expected_size])
    expected_elements = sorted(expected_elements)
    if actual_elements != expected_elements:
        print(f'Fail: {actual_elements=} {expected_elements=}')
        return

    print('Pass')


test([], 99, 0, [])
test([1], 99, 1, [1])
test([99], 99, 0, [])
test([1, 2, 99, 3, 4, 5], 99, 5, [1, 2, 3, 4, 5])
test([1, 2, 99, 3, 4, 5, 99], 99, 5, [1, 2, 3, 4, 5])
test([99, 1], 99, 1, [1])