LeetCode 27: Remove Element - All Approaches Explained

Problem Statement

The Remove Element problem, LeetCode 27, is an easy-difficulty challenge involving an array. You’re given an integer array nums and an integer val, and your task is to remove all occurrences of val from the array in-place. The relative order of the remaining elements can be changed, and you must return the number of elements remaining (k) after removal. The first k elements of the array should contain the result, and the remaining elements beyond k are irrelevant.

Constraints

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

Example

Copy codeInput: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation:
- Remove all 3s: [3,2,2,3] → [2,2].
- Return k = 2, first 2 elements are [2,2].

Copy codeInput: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,3,0,4,_,_,_]
Explanation:
- Remove all 2s: [0,1,2,2,3,0,4,2] → [0,1,3,0,4].
- Return k = 5.

Understanding the Problem

We need to remove all instances of a given value from an array in-place and return the new length. Key observations:

• Unlike Problem 26, the array isn’t sorted, and order doesn’t matter.
• We only need to ensure the first k elements are the non-val elements.
• In-place means no extra array allocation.

Let’s explore two approaches:

1. Two-Pointer (Best Approach) : Use two pointers for efficiency.
2. Brute Force : Shift elements to remove val.

Approach 1: Two-Pointer (Best Approach)

Intuition

Use two pointers: one to track the position for the next non-val element (k) and another to scan the array (i). Move non-val elements to the front. This is the best approach due to its optimal time complexity and in-place nature.

How It Works

• Initialize k = 0 (position for next non-val element).
• Iterate i through the array:
  • If nums[i] != val, place it at nums[k] and increment k.
• Return k as the count of remaining elements.

Step-by-Step Example

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

• Start: k = 0, nums = [0,1,2,2,3,0,4,2].
• i = 0: 0 != 2, nums[0] = 0, k = 1.
• i = 1: 1 != 2, nums[1] = 1, k = 2.
• i = 2: 2 == 2, skip.
• i = 3: 2 == 2, skip.
• i = 4: 3 != 2, nums[2] = 3, k = 3.
• i = 5: 0 != 2, nums[3] = 0, k = 4.
• i = 6: 4 != 2, nums[4] = 4, k = 5.
• i = 7: 2 == 2, skip.
• Result: k = 5, nums = [0,1,3,0,4, , ,_].

Python Code (Best Approach)

Copy codedef removeElement(nums, val):
    k = 0  # Position for next non-val element
    for i in range(len(nums)):
        if nums[i] != val:
            nums[k] = nums[i]
            k += 1
    return k

# Test cases
nums1 = [3,2,2,3]
print(removeElement(nums1, 3), nums1[:removeElement(nums1, 3)])  # 2, [2,2]
nums2 = [0,1,2,2,3,0,4,2]
print(removeElement(nums2, 2), nums2[:removeElement(nums2, 2)])  # 5, [0,1,3,0,4]

Detailed Walkthrough

• Two Pointers : k tracks result position, i scans array.
• In-Place : Overwrite with non-val elements.
• Return : k is the new length.

Complexity

• Time Complexity : O(n), where n is the length of nums. Single pass.
• Space Complexity : O(1), in-place modification.

Why It’s the Best

• Optimal time and space complexity.
• Simple and efficient.
• Preferred in interviews for in-place techniques.

Approach 2: Brute Force

Intuition

Shift elements left whenever val is encountered, effectively removing it by overwriting. This preserves order but is less efficient.

How It Works

• Iterate through the array.
• When val is found, shift all subsequent elements left.
• Track the new length and adjust accordingly.

Step-by-Step Example

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

• Start: nums = [3,2,2,3], k = 4.
• i = 0: 3 == 3, shift [2,2,3] left, nums = [2,2,3,3], k = 3.
• i = 1: 2 != 3, continue.
• i = 2: 2 != 3, continue.
• i = 3: 3 == 3, shift [], nums = [2,2,3,3], k = 2.
• Result: k = 2, nums = [2,2, , ].

Python Code

Copy codedef removeElement_brute(nums, val):
    k = len(nums)
    i = 0
    while i < k:
        if nums[i] == val:
            # Shift elements left
            for j in range(i, k - 1):
                nums[j] = nums[j + 1]
            k -= 1
        else:
            i += 1
    return k

# Test cases
nums1 = [3,2,2,3]
print(removeElement_brute(nums1, 3), nums1[:removeElement_brute(nums1, 3)])  # 2, [2,2]
nums2 = [0,1,2,2,3,0,4,2]
print(removeElement_brute(nums2, 2), nums2[:removeElement_brute(nums2, 2)])  # 5, [0,1,3,0,4]

Detailed Walkthrough

• Shift : Move elements left to overwrite val.
• Length : Decrease k for each removal.
• Iteration : Continue until end of current length.

Complexity

• Time Complexity : O(n²), where n is the length of nums. Shifting takes O(n) per removal.
• Space Complexity : O(1), in-place but slower.

Pros and Cons

• Pros : Preserves order, easy to understand.
• Cons : Inefficient due to shifting.

Comparison of Approaches

Edge Cases to Consider

1. Empty array : [] → 0.
2. No occurrences : [1,2,3], val=4 → 3, [1,2,3].
3. All same : [3,3,3], val=3 → 0, [_].
4. Single element : [1], val=1 → 0, [_].

Final Thoughts

• Brute Force : Intuitive but slow due to shifting.
• Two-Pointer : The best approach —fast, in-place, and practical. Master the two-pointer solution for its efficiency and applicability to array manipulation problems in interviews. Try modifying this to remove elements greater than a threshold as a follow-up!