Remove Element

📋

Problem

Imagine you have a list of items and you want to quickly remove all unwanted items without using extra space, like cleaning your desk by pushing unwanted papers aside.

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed. Return the new length of the array after removal. Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 500 ≤ val ≤ 100

Edge cases: All elements are val → output length 0No elements are val → output length equals original lengthval not present in array → array unchanged

</>

IDE

def remove_element(nums: list[int], val: int) -> int:public int removeElement(int[] nums, int val)int removeElement(vector<int>& nums, int val)function removeElement(nums, val)

def remove_element(nums, val):
    # Write your solution here
    pass

class Solution {
    public int removeElement(int[] nums, int val) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int removeElement(vector<int>& nums, int val) {
    // Write your solution here
    return 0;
}

function removeElement(nums, val) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrect length due to counting val elements as part of resultFailing to skip val elements when incrementing write pointer✅ Increment write pointer only when nums[i] != val; do not increment on val elements

Wrong: Array elements not overwritten correctly, leftover val elements remainNot overwriting val elements or shifting elements properly✅ Use a write pointer to overwrite val elements with subsequent non-val elements

Wrong: Fails on empty input or single-element arrays, causing errors or wrong lengthNo check for empty array or improper handling of single-element arrays✅ Add guard clauses for empty arrays and handle single-element arrays correctly

Wrong: Time limit exceeded on large inputsUsing nested loops or shifting elements repeatedly causing O(n^2) complexity✅ Implement two-pointer overwrite approach with O(n) time complexity

✓

Test Cases

Focus on handling edge cases like empty arrays and arrays where all elements are val.

Consider tricky inputs where val is absent or clustered at array ends.

Optimize your solution to linear time using two pointers to handle large inputs efficiently.

t1_01basic

Input{"nums":[3,2,2,3],"val":3,"n":4}

Expected2

⏱ Performance - must finish in 2000ms

After removing all 3's, the array becomes [2,2]. The function returns 2 as the new length.

💡 Use two pointers to track positions for overwriting unwanted elements.

💡 Check if current element equals val; if not, copy it to the next write position.

💡 Maintain a write index that increments only when copying non-val elements.

Why it failed: Returned length incorrect due to not properly skipping val elements or incorrect overwrite logic. Fix by incrementing write index only when copying non-val elements.

✓ Correctly removes all val elements and returns the new length.

t1_02basic

Input{"nums":[0,1,2,2,3,0,4,2],"val":2,"n":8}

Expected5

⏱ Performance - must finish in 2000ms

After removing all 2's, the array becomes [0,1,3,0,4]. The function returns 5 as the new length.

💡 Traverse the array once, overwriting elements equal to val.

💡 Use a write pointer to place non-val elements sequentially.

💡 Return the write pointer as the new length after traversal.

Why it failed: Incorrect length due to failing to overwrite all val elements or miscounting. Fix by ensuring write pointer only increments on non-val elements.

✓ Correctly removes all val elements and returns the new length.

t2_01edge

Input{"nums":[],"val":1,"n":0}

Expected0

⏱ Performance - must finish in 2000ms

Empty array input; nothing to remove, length remains 0.

💡 Check if input array is empty before processing.

💡 Handle zero-length arrays gracefully without errors.

💡 Return 0 immediately if array length is zero.

Why it failed: Fails on empty input due to not handling zero-length arrays. Fix by adding a check for empty array before processing.

✓ Handles empty input correctly by returning 0.

t2_02edge

Input{"nums":[5],"val":5,"n":1}

Expected0

⏱ Performance - must finish in 2000ms

Single element equal to val; after removal, length is 0.

💡 Test single-element arrays where element equals val.

💡 Ensure the element is removed and length updated to zero.

💡 Return 0 when the only element matches val.

Why it failed: Fails single-element val removal by not updating length to zero. Fix by checking each element and updating length accordingly.

✓ Correctly removes single val element and returns 0.

t2_03edge

Input{"nums":[1,1,1,1],"val":1,"n":4}

Expected0

⏱ Performance - must finish in 2000ms

All elements equal val; after removal, length is 0.

💡 Test arrays where all elements are val.

💡 Ensure all elements are removed and length is zero.

💡 Return 0 when no elements remain after removal.

Why it failed: Fails to remove all val elements when entire array matches val. Fix by ensuring write pointer does not increment for val elements.

✓ Correctly removes all val elements and returns 0.

t3_01corner

Input{"nums":[2,3,4,5,6],"val":1,"n":5}

Expected5

⏱ Performance - must finish in 2000ms

val not present in array; array unchanged, length remains 5.

💡 Check behavior when val does not appear in the array.

💡 Ensure no elements are removed and length remains original.

💡 Return original length if no elements equal val.

Why it failed: Incorrectly removes elements or changes length when val not present. Fix by only removing elements equal to val.

✓ Correctly returns original length when val not found.

t3_02corner

Input{"nums":[4,4,4,4,1,2,3],"val":4,"n":7}

Expected3

⏱ Performance - must finish in 2000ms

Removes all 4's from start; remaining elements [1,2,3], length 3.

💡 Test arrays with val elements clustered at start.

💡 Ensure all val elements are removed regardless of position.

💡 Use two pointers to overwrite val elements with non-val elements.

Why it failed: Fails to remove val elements at start due to incorrect pointer initialization. Fix by initializing write pointer at 0 and scanning entire array.

✓ Correctly removes val elements at start and returns new length.

t3_03corner

Input{"nums":[1,2,3,4,5,6,7,8,9,10],"val":5,"n":10}

Expected9

⏱ Performance - must finish in 2000ms

Removes single val element in middle; length reduces by one.

💡 Test removal of val element in the middle of array.

💡 Ensure elements after val are shifted correctly.

💡 Maintain order of non-val elements after removal.

Why it failed: Fails to shift elements after val correctly, causing incorrect length or leftover val. Fix by overwriting val elements with subsequent non-val elements.

✓ Correctly removes val element in middle and returns updated length.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000; solution must run in O(n) time to complete within 2 seconds.

💡 Avoid nested loops; use a single pass with two pointers.

💡 Time complexity should be linear in n.

💡 Use in-place overwrite to achieve O(1) space and O(n) time.

Why it failed: TLE due to O(n^2) approach like nested loops or shifting elements repeatedly. Fix by implementing two-pointer overwrite approach.

✓ Solution runs in O(n) time and completes within time limit.

Practice

1. You are given an integer array and a target integer. The task is to find three integers in the array whose sum is closest to the target. Which approach guarantees an optimal solution with O(n²) time complexity?

easy

A. Sort the array and use a fixed pointer with two pointers scanning from both ends.

B. Use a brute force triple nested loop to check all triplets.

C. Apply dynamic programming to store sums of pairs and find closest triplet sum.

D. Use a greedy approach by picking the closest element to target and then two others.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding three numbers whose sum is closest to a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach with O(n²) complexity

   Sorting the array allows fixing one element and using two pointers to find pairs that sum closest to the remaining target, achieving O(n²) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is classic for 3Sum Closest [OK]

Hint: Sorting + two pointers reduces complexity to O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with this problem
• Assuming greedy works for closest sum

2. You are given an array of integers and need to reorder it so that all even numbers appear before all odd numbers. Which algorithmic approach guarantees an optimal in-place solution with O(n) time and O(1) space complexity?

easy

A. Using a two-pointer technique that partitions the array in a single pass by swapping elements

B. Using dynamic programming to track even and odd counts and reorder accordingly

C. Sorting the array using a comparison-based sort and then grouping evens and odds

D. Using a brute force approach by creating two separate arrays for evens and odds and concatenating them

Solution

1. Step 1: Understand the problem constraints

   The problem requires reordering the array so that evens come before odds, ideally in-place and efficiently.

2. Step 2: Identify the optimal approach

   The two-pointer technique allows scanning the array once, swapping evens to the front, achieving O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer partitioning is classic for in-place parity partitioning [OK]

Hint: Two-pointer partitioning solves in-place parity grouping [OK]

Common Mistakes:

• Assuming sorting is needed for parity grouping
• Thinking DP applies to simple partitioning
• Believing extra arrays are optimal for in-place constraints

3. The following code attempts to move zeroes to the end of the array in-place:

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for num in nums:
        if num != 0:
            nums[lastNonZeroFoundAt] = num
            lastNonZeroFoundAt += 1
    # Bug introduced here
    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = nums[i]

What is the bug in this code?

medium

A. The variable lastNonZeroFoundAt is incremented incorrectly.

B. The first loop does not correctly identify non-zero elements.

C. The second loop does not fill zeroes after lastNonZeroFoundAt, leaving old values intact.

D. The assignment inside the first loop overwrites zeroes incorrectly.

Solution

1. Step 1: Analyze second loop behavior

   The second loop assigns nums[i] = nums[i], which does nothing and fails to fill zeroes.

2. Step 2: Identify correct fix

   It should assign nums[i] = 0 to move zeroes to the end properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Zeroes remain unfilled, causing incorrect output [OK]

Hint: Second loop must fill zeroes, not copy existing values [OK]

Common Mistakes:

• Forgetting to fill zeroes after moving non-zero elements
• Misunderstanding loop purpose

4. What is the time complexity of the in-place two-pointer partition algorithm for partitioning an array by parity, and why?

medium

A. O(n) because each element is visited once and swapped at most once

B. O(n log n) because of the swaps involved

C. O(n^2) because swapping elements inside the loop can be costly

D. O(n) but with O(n) auxiliary space due to recursion stack

Solution

1. Step 1: Analyze loop iterations

   The algorithm iterates over the array once, visiting each element exactly once.

2. Step 2: Analyze swaps and space

   Swaps occur only when an even element is found, at most once per element. No recursion or extra space is used.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant swaps -> O(n) time and O(1) space [OK]

Hint: Single pass with constant swaps -> O(n) time [OK]

Common Mistakes:

• Assuming swaps cause O(n^2) complexity
• Confusing with sorting complexity O(n log n)
• Thinking recursion or extra space is involved

5. Suppose the input array can contain any integer values, not just 0, 1, and 2, but you still want to sort it in a single pass using a similar three-pointer approach. Which modification to the Dutch National Flag algorithm is necessary to handle this general case correctly?

hard

A. Use counting sort instead, as three pointers only work for three distinct values

B. Extend the algorithm to dynamically partition into k segments with k pointers

C. Map the values to 0,1,2 first, then apply the original algorithm

D. Use quicksort partitioning with recursive calls instead of pointers

Solution

1. Step 1: Understand limitation of original algorithm

   The Dutch National Flag algorithm is designed specifically for three distinct values and uses three pointers to partition accordingly.

2. Step 2: Generalize to k distinct values

   For more than three distinct values, the algorithm must be extended to k pointers or multiple passes to partition into k segments, as a single pass with three pointers cannot correctly sort arbitrary values.

3. Step 3: Evaluate other options

   Counting sort is two-pass, mapping values is not always feasible, and quicksort is general but not single pass.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Generalizing requires more pointers or passes, not just three pointers [OK]

Hint: Three pointers only for three distinct values [OK]

Common Mistakes:

• Trying to map values first
• Using quicksort for single pass
• Assuming counting sort is single pass