LeetCode 27 - Remove Element

LeetCode Problem 27

Difficulty: 🟢 Easy
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem gives us an integer array nums and a target value val. Our task is to remove every occurrence of val from the array, but we must do it in-place. This means we are not supposed to create another array and return it. Instead, we modify the original array directly.

The function should return an integer k, which represents how many elements remain after removing all instances of val. After the operation is complete, the first k positions of nums must contain only values that are not equal to val.

An important detail is that the order of the remaining elements does not matter. The problem explicitly allows rearranging elements if needed. Also, anything beyond index k - 1 is ignored by the judge, so those values do not matter.

For example, if:

nums = [3,2,2,3], val = 3

after removing all 3s, the array may become:

[2,2,_,_]

The underscores represent positions that are irrelevant after the valid portion of the array ends.

The constraints are very small:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

Since the array length is at most 100, even less efficient approaches could technically pass. However, the goal of the problem is to practice in-place array manipulation and the two-pointer technique.

Several edge cases are important to consider:

• The array may be empty.
• Every element may equal val.
• No element may equal val.
• The target value may appear multiple times consecutively.
• The target value may appear at the beginning or end of the array.

A correct solution must handle all of these safely without accessing invalid indices or returning an incorrect count.

Approaches

Brute Force Approach

A straightforward solution is to create a new temporary array that stores only the elements not equal to val.

We iterate through nums, and whenever we see a value different from val, we append it to the temporary array. After finishing the traversal, we copy the contents of the temporary array back into nums.

This approach is correct because every non-target element is preserved exactly once, and every target element is skipped.

However, this solution uses extra memory proportional to the size of the array. The problem specifically asks for an in-place solution, so although this works logically, it does not satisfy the intended optimization requirement.

Optimal Approach, Two Pointers

The key insight is that we do not actually need another array. We only need to keep track of where the next valid element should be written.

We use two pointers:

• A read pointer that scans through every element in the array
• A write pointer that tracks the next position where a non-val element should be placed

Whenever the read pointer finds a value that should be kept, we copy it into the write pointer position and advance the write pointer.

By the end:

• All valid elements are compacted into the front of the array
• The write pointer value equals the number of valid elements

This works because every kept element is written exactly once into the earliest available valid position.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses an additional array to store valid elements
Optimal	O(n)	O(1)	Uses two pointers and modifies the array in-place

Algorithm Walkthrough

1. Initialize a variable called write_index to 0.

This pointer represents the next position where a valid element should be written. 2. Traverse the array using a loop.

Each element is examined exactly once. 3. For every element, check whether it is different from val.

If it equals val, we skip it because it should be removed. 4. If the current element is not equal to val, copy it into nums[write_index].

This ensures that all valid elements are packed toward the front of the array. 5. Increment write_index.

After placing a valid element, the next valid element should go into the next position. 6. Continue until the entire array has been processed. 7. Return write_index.

This value represents the number of elements not equal to val.

Why it works

The algorithm maintains the invariant that all positions before write_index contain valid elements that are not equal to val.

Every time we encounter a valid element, we place it into the next available valid position. Since every array element is processed exactly once, and only non-target elements are copied forward, the first k elements of the array will contain exactly the required values when the loop finishes.

Python Solution

from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        write_index = 0

        for num in nums:
            if num != val:
                nums[write_index] = num
                write_index += 1

        return write_index

The implementation begins by initializing write_index to 0. This variable tracks the next location where a valid element should be stored.

The loop iterates through every value in nums. For each element, the code checks whether it differs from val.

If the element should be kept, it is copied into nums[write_index]. Then write_index is incremented so the next valid element will be placed immediately after it.

Elements equal to val are ignored completely, which effectively removes them from the valid section of the array.

Finally, the function returns write_index, which equals the number of remaining valid elements.

Go Solution

func removeElement(nums []int, val int) int {
    writeIndex := 0

    for _, num := range nums {
        if num != val {
            nums[writeIndex] = num
            writeIndex++
        }
    }

    return writeIndex
}

The Go implementation follows the same logic as the Python version.

Go slices are reference-like structures, so modifying nums inside the function updates the original underlying array directly. No additional allocation is required.

There are no special concerns about integer overflow because the array size is extremely small. Empty slices are naturally handled because the loop simply executes zero times.

Worked Examples

Example 1

nums = [3,2,2,3]
val = 3

Initial state:

Step	Current Number	Action	nums	write_index
Start	-	Initialize	[3,2,2,3]	0

Iteration details:

Step	Current Number	Action	nums	write_index
1	3	Skip because it equals val	[3,2,2,3]	0
2	2	Write to index 0	[2,2,2,3]	1
3	2	Write to index 1	[2,2,2,3]	2
4	3	Skip because it equals val	[2,2,2,3]	2

Final result:

k = 2
nums = [2,2,_,_]

Only the first two positions matter.

Example 2

nums = [0,1,2,2,3,0,4,2]
val = 2

Initial state:

Step	Current Number	Action	nums	write_index
Start	-	Initialize	[0,1,2,2,3,0,4,2]	0

Iteration details:

Step	Current Number	Action	nums	write_index
1	0	Write to index 0	[0,1,2,2,3,0,4,2]	1
2	1	Write to index 1	[0,1,2,2,3,0,4,2]	2
3	2	Skip	[0,1,2,2,3,0,4,2]	2
4	2	Skip	[0,1,2,2,3,0,4,2]	2
5	3	Write to index 2	[0,1,3,2,3,0,4,2]	3
6	0	Write to index 3	[0,1,3,0,3,0,4,2]	4
7	4	Write to index 4	[0,1,3,0,4,0,4,2]	5
8	2	Skip	[0,1,3,0,4,0,4,2]	5

Final result:

k = 5
nums = [0,1,3,0,4,_,_,_]

The order does not matter, so this output is accepted.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is visited exactly once
Space	O(1)	Only a few variables are used regardless of input size

The algorithm performs a single pass through the array, so the running time grows linearly with the number of elements.

No auxiliary data structures are allocated. The array is modified directly in-place, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        write_index = 0

        for num in nums:
            if num != val:
                nums[write_index] = num
                write_index += 1

        return write_index

solution = Solution()

# Example 1
nums = [3, 2, 2, 3]
k = solution.removeElement(nums, 3)
assert k == 2  # Removes two occurrences of 3
assert sorted(nums[:k]) == [2, 2]

# Example 2
nums = [0, 1, 2, 2, 3, 0, 4, 2]
k = solution.removeElement(nums, 2)
assert k == 5  # Removes all 2s
assert sorted(nums[:k]) == [0, 0, 1, 3, 4]

# Empty array
nums = []
k = solution.removeElement(nums, 1)
assert k == 0  # No elements to process

# No occurrences of val
nums = [1, 2, 3]
k = solution.removeElement(nums, 4)
assert k == 3  # Array remains unchanged
assert sorted(nums[:k]) == [1, 2, 3]

# All elements equal val
nums = [5, 5, 5]
k = solution.removeElement(nums, 5)
assert k == 0  # Everything removed

# Single element kept
nums = [7]
k = solution.removeElement(nums, 3)
assert k == 1  # Single valid element remains
assert nums[:k] == [7]

# Single element removed
nums = [7]
k = solution.removeElement(nums, 7)
assert k == 0  # Single element removed

# Consecutive target values
nums = [1, 2, 2, 2, 3]
k = solution.removeElement(nums, 2)
assert k == 2  # Multiple consecutive removals
assert sorted(nums[:k]) == [1, 3]

# Target values at both ends
nums = [4, 1, 2, 4]
k = solution.removeElement(nums, 4)
assert k == 2  # Removes boundary values
assert sorted(nums[:k]) == [1, 2]

Test	Why
[3,2,2,3], val=3	Validates the basic example from the problem
[0,1,2,2,3,0,4,2], val=2	Tests multiple removals across the array
[], val=1	Ensures empty arrays work correctly
[1,2,3], val=4	Confirms no changes when target is absent
[5,5,5], val=5	Ensures complete removal works
[7], val=3	Tests single-element array where value is kept
[7], val=7	Tests single-element array where value is removed
[1,2,2,2,3], val=2	Validates handling consecutive target values
[4,1,2,4], val=4	Tests removals at array boundaries

Edge Cases

Empty Array

An empty array is a common edge case because loops and index operations can fail if not handled carefully. In this implementation, the loop simply executes zero times, and write_index remains 0. The function correctly returns 0.

All Elements Equal to val

If every element matches the target value, the algorithm should remove everything. A buggy implementation might accidentally leave stale values in the valid range or return the wrong count.

This solution skips every element, so write_index never increases. The returned result is 0, which correctly indicates that no valid elements remain.

No Elements Equal to val

If the target value never appears, the array should remain unchanged and the returned length should equal the original array size.

The algorithm naturally handles this because every element passes the num != val condition. Each value is copied back into its own position, and write_index eventually equals len(nums).

Consecutive Target Values

Consecutive removable elements can expose pointer movement bugs in some implementations. For example, repeatedly shifting elements left can accidentally skip values.

The two-pointer approach avoids this issue entirely because the read pointer always moves independently through the array, while the write pointer only advances when a valid element is found. Consecutive target values are simply skipped one after another.