Read Write Heads

Remove Elements

27. Remove Element (Easy)

Solution

Intention here is to remove a particular element val.

Have two pointers, one is used to read from read and the other is used to write to write.

Advance read pointer to read elements, whenever the read doesnt points to the val, we need to maintain that element in the array, hence we need to write the element into write pointer.

If the read points to val, then we need to skip writing the element, since we need to remove it. This is the reason why we just need to advance read pointer to read the next element.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def removeElement(self, nums: List[int], val: int) -> int:
    n = len(nums)
    read = write = 0
    while read < n:
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
        read += 1
    return write

Solution

Very similar to previous approach, but instead of overwriting write pointer by read pointer, we just swap both of them.

Essentially they are same considering the fact that they give the same answer.

But subtle difference is that: (Eg: arr = [7, 4, 2, 9, 2, 3, 2, 2, 5, 1] and remove 2)

  • When overwritten, the last k elements would be original elements at particular position. * arr = [7, 4, 9, 3, 5, 1, 2, 2, 5, 1] , where actual answer is arr = [7, 4, 9, 3, 5, 1] and rest are garbage.

  • When swapped, the last k elements will be the elements which were supposed to remove. * arr = [7, 4, 9, 3, 5, 1, 2, 2, 2, 2] , where actual answer is arr = [7, 4, 9, 3, 5, 1] and rest are garbage. But note that, removed elements are actually moved to the end.

def removeElement(self, nums: List[int], val: int) -> int:
    read, write = 0, 0
    while read < len(nums):
        if nums[read] != val:
            nums[read], nums[write] = nums[write], nums[read]
            write += 1
        read += 1
    return write

283. Move Zeroes (Easy)

Solution

There are 2 subproblems:

  • Remove 0, and preserve order of the array.

  • Make last k elements 0. k is the number of zeros)

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def moveZeroes(self, nums: List[int]) -> None:
    n = len(nums)
    read = write = 0
    while read < n:
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
        read += 1

    while write < n:
        nums[write] = 0
        write += 1

Solution

Since, swapping read and write elements, the removal elements will be moved to the back of the array. By using this property, we can directly remove 0, so that all the 0’s would be moved to the back. More explanation is on 27. Remove Element (Easy).

def moveZeroes(self, nums: List[int]) -> None:
    n = len(nums)
    read = write = 0
    while read < n:
        if nums[read] != 0:
            nums[read], nums[write] = nums[write], nums[read]
            write += 1
        read += 1

1119. Remove Vowels from a String (Easy)

Solution

There are 2 subproblems:

  • Remove 0, and preserve order of the array.

  • Make last k elements 0. k is the number of zeros)

Analysis

Time Complexity: O(N)

where:

  • N is the length of the string

Space Complexity: O(1)

def removeVowels(self, s: str) -> str:
    s = list(s)
    n = len(s)
    read = write = 0
    vowels = set("aeiou")
    while read < n:
        if s[read] not in vowels:
            s[write] = s[read]
            write += 1
        read += 1
    return "".join(s[:write])

Remove Elements from Sorted Array

Generic - Max frequency is k

Solution

Reference: StefanPochmann solution

If arr = [1, 1, 1, 2, 2, 3] and k = 2, third one should be removed. When we process third 1, our read and write pointer points to index 2. We can have 1 from index 2 only if we didn’t have 1 at index 0. Which means in order for us to have 1 at index 2(read), write - 2 == 2 - 2 == 0 shouldnt be 1.

Can we write like nums[write - 2] != nums[read]. In other words, we can have elements if nums[write - 2] > nums[read].

We need to consider an edge case where the first 2 elements should be present and skipped from any checks.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def removeDuplicatesK(nums, k: int):
    n = len(nums)
    read = write = 0
    while read < n:
        if read < k or nums[write - k] < nums[read]:
            nums[write] = nums[read]
            write += 1
        read += 1
    return write

80. Remove Duplicates from Sorted Array II (Medium)

Solution

Reference: StefanPochmann solution

A special case of the generic version where k = 2 since maximum allowed frequency of any number is 2.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def removeDuplicates(self, nums: List[int]) -> int:
    return removeDuplicatesK(nums, k=2)

26. Remove Duplicates from Sorted Array (Easy)

Also

Solution

Reference: StefanPochmann solution

A special case of the generic version where k = 2 since maximum allowed frequency of any number is 1. Which means, no duplicates are allowed at all.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def removeDuplicates(self, nums: List[int]) -> int:
    return removeDuplicatesK(nums, k=1)

Sort the Array

922. Sort Array By Parity II (Easy)

Solution

Seems like we could use Left Right Heads approach just like its sibling problem 905. Sort Array By Parity (Easy). But for some cases, it would end up in an infinite loop. Just try using it and you will know the bug (maybe use the same code as sibling problem).

Here we actually need to use Read Write Heads to solve them correctly.

This is not exactly Read Write Heads approach, but hybrid of both Read Write Heads and Left Right Heads.

Algorithm:

  • Start read from index 1 and write from index 0. Because, read will only look for odd numbers and write for even.

  • Advance read by 2 index as long as it points to an odd number.

  • When read points to an even number, advance write as long as it points to an even number.

  • When read points to an even number and write points to an odd number, just swap them and advance both pointers.

Analysis

Time Complexity: O(N)

where:

  • N is the length of the array

Space Complexity: O(1)

def sortArrayByParityII(self, nums: List[int]) -> List[int]:
    n = len(nums)
    read, write = 1, 0
    while read < n:
        if nums[read] % 2 == 1:
            read += 2
        elif nums[write] % 2 == 0:
            write += 2
        else:
            nums[read], nums[write] = nums[write], nums[read]
            read += 2
            write += 2
    return nums