Remove Element

🎯

Remove Element

easyTWO_POINTERAmazonGoogle

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.

💡 This problem is a classic example of using two pointers moving in the same direction to modify an array in-place. Beginners often struggle because they try to remove elements by shifting the array multiple times, which is inefficient. Understanding the two-pointer approach helps avoid unnecessary operations and leads to optimal in-place solutions.

📋

Problem Statement

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

💡

Example

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

Output2

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

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

Output5

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

• All elements are val → output length 0
• No elements are val → output length equals original length
• val not present in array → array unchanged
• Array of length 1 with val present → output length 0

⚠️

Common Mistakes

Shifting elements inside the loop without adjusting indices

Skips elements or infinite loop

✅ Only increment index when no removal occurs

Not handling empty array or single element array

Runtime errors or incorrect length

✅ Add checks or ensure loops handle small arrays gracefully

Using extra space instead of in-place modification

Fails interview constraints

✅ Use two-pointer approach to modify array in-place

Confusing when to increment pointers in swap approach

Infinite loop or incorrect removal

✅ Only increment start pointer when current element is not val

Returning wrong length or not updating array correctly

Incorrect output or partial removal

✅ Return the write pointer or start pointer as new length and slice array accordingly

🧠

Brute Force (Nested Loops / Shifting Elements)

💡 This approach exists to show the naive way of solving the problem by removing elements one by one and shifting the rest. It helps beginners understand why this is inefficient and motivates better solutions.

Intuition

Scan the array from left to right. Whenever you find an element equal to val, shift all subsequent elements one position to the left to overwrite it. Decrease the array length accordingly.

Algorithm

1. Initialize length as the size of the array.
2. Iterate over the array with index i from 0 to length-1.
3. If nums[i] == val, shift all elements after i one step left and reduce length by 1.
4. Repeat until the end of the array is reached.

💡 The nested shifting makes it hard to see efficiency, but it clearly shows the removal process step-by-step.

</>

Code

def remove_element(nums, val):
    length = len(nums)
    i = 0
    while i < length:
        if nums[i] == val:
            for j in range(i, length - 1):
                nums[j] = nums[j + 1]
            length -= 1
        else:
            i += 1
    return length

# Driver code
if __name__ == '__main__':
    arr = [3,2,2,3]
    val = 3
    new_len = remove_element(arr, val)
    print(new_len, arr[:new_len])

Line Notes

length = len(nums)Initialize length to track current valid array size

while i < lengthTraverse array with index i, adjusting length dynamically

if nums[i] == valCheck if current element needs removal

for j in range(i, length - 1)Shift elements left to overwrite the removed element

import java.util.*;
public class RemoveElement {
    public static int removeElement(int[] nums, int val) {
        int length = nums.length;
        int i = 0;
        while (i < length) {
            if (nums[i] == val) {
                for (int j = i; j < length - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                length--;
            } else {
                i++;
            }
        }
        return length;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,2,3};
        int val = 3;
        int newLen = removeElement(arr, val);
        System.out.print(newLen + " ");
        for (int i = 0; i < newLen; i++) System.out.print(arr[i] + " ");
    }
}

Line Notes

int length = nums.length;Track current valid array length

while (i < length)Traverse array with dynamic length

if (nums[i] == val)Check if current element matches val

for (int j = i; j < length - 1; j++)Shift elements left to overwrite removed element

#include <iostream>
#include <vector>
using namespace std;

int removeElement(vector<int>& nums, int val) {
    int length = nums.size();
    int i = 0;
    while (i < length) {
        if (nums[i] == val) {
            for (int j = i; j < length - 1; j++) {
                nums[j] = nums[j + 1];
            }
            length--;
        } else {
            i++;
        }
    }
    return length;
}

int main() {
    vector<int> arr = {3,2,2,3};
    int val = 3;
    int newLen = removeElement(arr, val);
    cout << newLen << " ";
    for (int i = 0; i < newLen; i++) cout << arr[i] << " ";
    return 0;
}

Line Notes

int length = nums.size();Initialize length to track valid array size

while (i < length)Traverse array with index i and dynamic length

if (nums[i] == val)Check if current element equals val

for (int j = i; j < length - 1; j++)Shift elements left to overwrite removed element

function removeElement(nums, val) {
    let length = nums.length;
    let i = 0;
    while (i < length) {
        if (nums[i] === val) {
            for (let j = i; j < length - 1; j++) {
                nums[j] = nums[j + 1];
            }
            length--;
        } else {
            i++;
        }
    }
    return length;
}

// Test
const arr = [3,2,2,3];
const val = 3;
const newLen = removeElement(arr, val);
console.log(newLen, arr.slice(0, newLen));

Line Notes

let length = nums.length;Track current valid length of array

while (i < length)Traverse array with dynamic length

if (nums[i] === val)Check if current element matches val

for (let j = i; j < length - 1; j++)Shift elements left to overwrite removed element

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Each removal causes shifting of up to n elements, leading to O(n^2) in worst case when many elements equal val.

💡 For n=20, this means up to 400 operations, which is inefficient for large arrays.

Interview Verdict: TLE for large inputs; only useful to introduce problem

This approach is too slow for large inputs but helps understand the problem and motivates better solutions.

🧠

Two Pointers - Overwrite Approach

💡 This approach improves efficiency by using two pointers to overwrite unwanted elements instead of shifting repeatedly. It introduces the core two-pointer technique for in-place array modification.

Intuition

Use one pointer to iterate over the array and another to track the position to write the next valid element. When the current element is not val, copy it to the write pointer and increment the write pointer.

Algorithm

1. Initialize write pointer at 0.
2. Iterate read pointer from 0 to end of array.
3. If nums[read] != val, copy nums[read] to nums[write] and increment write.
4. Return write as the new length.

💡 This approach is easier to implement and understand once you grasp the two-pointer concept.

</>

Code

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write

# Driver code
if __name__ == '__main__':
    arr = [3,2,2,3]
    val = 3
    new_len = remove_element(arr, val)
    print(new_len, arr[:new_len])

Line Notes

write = 0Initialize write pointer to track position for next valid element

for read in range(len(nums))Read pointer scans entire array

if nums[read] != valCheck if current element should be kept

nums[write] = nums[read]Overwrite element at write pointer with valid element

public class RemoveElement {
    public static int removeElement(int[] nums, int val) {
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] != val) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,2,3};
        int val = 3;
        int newLen = removeElement(arr, val);
        System.out.print(newLen + " ");
        for (int i = 0; i < newLen; i++) System.out.print(arr[i] + " ");
    }
}

Line Notes

int write = 0;Write pointer tracks next position for valid element

for (int read = 0; read < nums.length; read++)Read pointer scans all elements

if (nums[read] != val)Check if element should be kept

nums[write] = nums[read];Overwrite element at write pointer with valid element

#include <iostream>
#include <vector>
using namespace std;

int removeElement(vector<int>& nums, int val) {
    int write = 0;
    for (int read = 0; read < nums.size(); read++) {
        if (nums[read] != val) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

int main() {
    vector<int> arr = {3,2,2,3};
    int val = 3;
    int newLen = removeElement(arr, val);
    cout << newLen << " ";
    for (int i = 0; i < newLen; i++) cout << arr[i] << " ";
    return 0;
}

Line Notes

int write = 0;Write pointer tracks position for next valid element

for (int read = 0; read < nums.size(); read++)Read pointer scans entire array

if (nums[read] != val)Check if element is not val

nums[write] = nums[read];Overwrite element at write pointer with valid element

function removeElement(nums, val) {
    let write = 0;
    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== val) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

// Test
const arr = [3,2,2,3];
const val = 3;
const newLen = removeElement(arr, val);
console.log(newLen, arr.slice(0, newLen));

Line Notes

let write = 0;Write pointer tracks next valid element position

for (let read = 0; read < nums.length; read++)Read pointer scans all elements

if (nums[read] !== val)Check if element should be kept

nums[write] = nums[read];Overwrite element at write pointer with valid element

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited once by the read pointer and possibly copied once, resulting in linear time.

💡 For n=20, this means about 20 operations, which is efficient even for large arrays.

Interview Verdict: Accepted and optimal for in-place removal

This approach is the standard solution expected in interviews for this problem.

🧠

Two Pointers - Swap with End Approach

💡 This approach is useful when the order of elements does not need to be preserved. It reduces the number of writes by swapping unwanted elements with the last element, shrinking the array from the end.

Intuition

Use two pointers: one at the start and one at the end. When the start pointer finds val, swap it with the end pointer's element and reduce the end pointer. Otherwise, move the start pointer forward.

Algorithm

1. Initialize start pointer at 0 and end pointer at last index.
2. While start <= end, if nums[start] == val, swap with nums[end] and decrement end.
3. If nums[start] != val, increment start.
4. Return start as the new length.

💡 This approach minimizes writes by swapping only when necessary and avoids shifting.

</>

Code

def remove_element(nums, val):
    start, end = 0, len(nums) - 1
    while start <= end:
        if nums[start] == val:
            nums[start], nums[end] = nums[end], nums[start]
            end -= 1
        else:
            start += 1
    return start

# Driver code
if __name__ == '__main__':
    arr = [3,2,2,3]
    val = 3
    new_len = remove_element(arr, val)
    print(new_len, arr[:new_len])

Line Notes

start, end = 0, len(nums) - 1Initialize two pointers at start and end

while start <= endLoop until pointers cross

if nums[start] == valCheck if start pointer points to val to remove

nums[start], nums[end] = nums[end], nums[start]Swap val with element at end to remove it

public class RemoveElement {
    public static int removeElement(int[] nums, int val) {
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            if (nums[start] == val) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                end--;
            } else {
                start++;
            }
        }
        return start;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,2,3};
        int val = 3;
        int newLen = removeElement(arr, val);
        System.out.print(newLen + " ");
        for (int i = 0; i < newLen; i++) System.out.print(arr[i] + " ");
    }
}

Line Notes

int start = 0, end = nums.length - 1;Initialize two pointers at start and end

while (start <= end)Loop until pointers cross

if (nums[start] == val)Check if start pointer points to val

Swap elements at start and endRemove val by swapping with end element

#include <iostream>
#include <vector>
using namespace std;

int removeElement(vector<int>& nums, int val) {
    int start = 0, end = nums.size() - 1;
    while (start <= end) {
        if (nums[start] == val) {
            swap(nums[start], nums[end]);
            end--;
        } else {
            start++;
        }
    }
    return start;
}

int main() {
    vector<int> arr = {3,2,2,3};
    int val = 3;
    int newLen = removeElement(arr, val);
    cout << newLen << " ";
    for (int i = 0; i < newLen; i++) cout << arr[i] << " ";
    return 0;
}

Line Notes

int start = 0, end = nums.size() - 1;Initialize two pointers at start and end

while (start <= end)Loop until pointers cross

if (nums[start] == val)Check if start pointer points to val

swap(nums[start], nums[end]);Swap val with element at end to remove it

function removeElement(nums, val) {
    let start = 0, end = nums.length - 1;
    while (start <= end) {
        if (nums[start] === val) {
            [nums[start], nums[end]] = [nums[end], nums[start]];
            end--;
        } else {
            start++;
        }
    }
    return start;
}

// Test
const arr = [3,2,2,3];
const val = 3;
const newLen = removeElement(arr, val);
console.log(newLen, arr.slice(0, newLen));

Line Notes

let start = 0, end = nums.length - 1;Initialize two pointers at start and end

while (start <= end)Loop until pointers cross

if (nums[start] === val)Check if start pointer points to val

[nums[start], nums[end]] = [nums[end], nums[start]];Swap val with element at end to remove it

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most once by start pointer and swapped at most once, resulting in linear time.

💡 For n=20, this means about 20 operations, efficient and minimal writes.

Interview Verdict: Accepted and optimal when order does not matter

This approach is preferred if element order preservation is not required, reducing writes.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, the two-pointer overwrite approach is the best to code due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Two Pointers - Overwrite	O(n)	O(1)	No	N/A	Code this approach
3. Two Pointers - Swap with End	O(n)	O(1)	No	N/A	Mention if order does not matter

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying requirements, then explain brute force to show understanding, followed by optimal solutions. Practice coding and testing edge cases.

How to Present

Clarify problem constraints and ask if element order must be preserved.State the brute force approach to show initial understanding.Explain the two-pointer overwrite approach as the optimal solution.If order does not matter, mention the swap with end approach.Write clean code and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force, knowledge of two-pointer techniques, and code correctness including edge cases.

Common Follow-ups

• What if the order of elements must be preserved? → Use overwrite approach.
• Can you do it with minimal writes? → Swap with end approach if order doesn't matter.

💡 These follow-ups test your flexibility and understanding of constraints affecting solution choice.

🔍

Pattern Recognition

When to Use

1) Need to remove or partition elements in an array in-place, 2) Constraints require O(1) extra space, 3) Problem hints at modifying array order or not, 4) Two pointers moving in same direction or from ends can be applied.

Signature Phrases

remove all occurrencesin-place modificationrelative order may be changed

NOT This Pattern When

Problems requiring sorting or complex DP are different patterns.

Similar Problems

Remove Duplicates from Sorted Array - similar in-place removal with order preservationMove Zeroes - partitioning array with two pointers

Practice

1. You are given a problem where you must reverse the order of characters in an array in-place, without using extra space. Which algorithmic approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Using two pointers starting at opposite ends of the array and swapping elements until they meet.

B. Using a brute force approach that creates a new array and copies elements in reverse order.

C. Using a dynamic programming approach to store intermediate reversed substrings.

D. Using a greedy approach that swaps characters only when they are vowels.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing characters in-place without extra space, so approaches that use additional arrays are suboptimal.

2. Step 2: Identify the optimal approach

   Two pointers starting at opposite ends allow swapping characters in O(n) time and O(1) extra space, fulfilling the problem requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer in-place reversal is standard for optimal string reversal [OK]

Hint: Two pointers from ends swap in-place efficiently [OK]

Common Mistakes:

• Thinking DP or greedy applies to reversing strings
• Assuming extra space is allowed
• Confusing brute force with optimal in-place

2. You are given a string and need to determine if it reads the same forwards and backwards, ignoring case and non-alphanumeric characters. Which approach guarantees an optimal O(n) time and O(n) space solution for this problem?

easy

A. Reverse the original string and compare it directly to the input string without any preprocessing.

B. Use dynamic programming to check all substrings for palindrome properties.

C. Use a greedy approach to skip characters that don't match and try to fix mismatches on the fly.

D. Preprocess the string by removing non-alphanumeric characters and converting to lowercase, then use two pointers from opposite ends to compare characters.

Solution

1. Step 1: Understand problem constraints

   The problem requires ignoring case and non-alphanumeric characters, so direct comparison or naive reversal won't work correctly.

2. Step 2: Identify approach that handles preprocessing and efficient comparison

   Preprocessing to clean the string and then using two pointers from opposite ends ensures O(n) time and space, and correctly handles all cases.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Preprocessing + two pointers is standard for palindrome checks ignoring punctuation [OK]

Hint: Preprocess then two pointers is optimal palindrome check [OK]

Common Mistakes:

• Trying to compare original string directly without cleaning
• Using DP which is overkill and slower
• Greedy skipping mismatches leads to incorrect results

3. What is the time complexity of the optimal in-place merge algorithm that uses two pointers starting from the end of the arrays to merge two sorted arrays of sizes m and n?

medium

A. O((m + n) log(m + n)) due to sorting after merging

B. O(m * n) because of nested loops comparing elements

C. O(m + n) because each element is processed exactly once

D. O(m + n) but with O(m + n) extra space for temporary storage

Solution

1. Step 1: Identify the loops

   The algorithm uses a single while loop that processes each element from the end once.

2. Step 2: Analyze operations per element

   Each element from nums1 and nums2 is moved at most once, so total operations are proportional to m + n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time complexity with constant extra space [OK]

Hint: Two-pointer merge is linear time, no sorting needed [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops cause quadratic time

4. Consider the following buggy code for merging two sorted arrays in-place. Which line contains the subtle bug that causes missing elements in the final merged array?

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    # Missing copying remaining nums2 elements

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)

medium

A. Line 12: Missing while loop to copy remaining nums2 elements

B. Line 9: nums1[k] = nums2[j]

C. Line 4: i = m - 1

D. Line 7: if nums1[i] > nums2[j]:

Solution

1. Step 1: Analyze the main merging loop

   The main loop merges elements from the back correctly but stops when either i or j is negative.

2. Step 2: Identify missing step

   There is no loop copying remaining elements from nums2 if any remain, causing missing elements in nums1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without copying leftover nums2 elements, final array is incomplete [OK]

Hint: Always copy leftover nums2 elements after main loop [OK]

Common Mistakes:

• Forgetting leftover nums2 copy
• Overwriting nums1 elements too early

5. Suppose the input array is no longer sorted but you still need to return the squares of each number in sorted order. Which of the following approaches is correct and efficient?

hard

A. Square each element and then sort the resulting array using a standard sorting algorithm.

B. Use a max-heap to insert squares and extract them in sorted order.

C. Use the two-pointer approach from ends, as it works regardless of input order.

D. Modify the input array in place by squaring and then perform an in-place merge sort.

Solution

1. Step 1: Recognize input is unsorted

   Two-pointer approach relies on sorted input; it fails if input is unsorted.

2. Step 2: Choose a correct approach

   Squaring then sorting with a standard sort is correct and efficient (O(n log n)) for unsorted input.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting after squaring handles unsorted input correctly [OK]

Hint: Two-pointer requires sorted input; else sort after squaring [OK]

Common Mistakes:

• Applying two-pointer on unsorted input
• Using complex data structures unnecessarily
• Assuming in-place modifications preserve order