27. Remove Element - Detailed Explanation

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. After removing, return the new length of the array containing only the elements that are not equal to val.

Important:
It does not matter what values are set beyond the returned length.

Examples

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, with nums = [2,2,_,_]

Explanation:
After removing all occurrences of 3, the array might become [2,2,_,_] (where the underscores denote values that can be ignored). The new length is 2.

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, with nums = [0,1,3,0,4,_,_,_]

Explanation:
After removing all occurrences of 2, the array might become [0,1,3,0,4,_,_,_] in any order, and the new length is 5.

Example 3:

Input: nums = [1,1,1,1], val = 1
Output: 0, with nums = [_,_,_,_]

Explanation:
Every element equals val, so after removal, there are no elements left. The new length is 0.

Constraints

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

Hints

1. In-Place Requirement:
   You must modify the array without using extra space for another array. This means you have to rearrange the existing array elements.

2. Two-Pointer Technique:
   Consider using two pointers (or indices): one to scan through the array and another to mark the position where the next non-val element should be placed.

3. Order Does Not Matter:
   Since the order of the remaining elements can be changed, you only need to ensure that the first part of the array (up to the returned length) contains the non-val elements.

Approaches

1. Brute Force Approach

Idea:
Iterate through the array and, each time you find an element equal to val, shift all subsequent elements to the left by one position. Continue this until the end of the array.

Why it’s inefficient:

• In the worst case (where nearly every element is val), every removal could require shifting many elements.
• This leads to an overall time complexity of O(n²), which is acceptable for small arrays but inefficient as n grows.

2. Optimal Approach: Two-Pointer Technique

Idea:
Use two pointers:

• Slow pointer (i): This pointer keeps track of the position in the array where the next valid (non-val) element should be placed.
• Fast pointer (j): This pointer iterates through every element of the array.

Procedure:

• Initialize i = 0.
• For each index j in the array:
  • If nums[j] is not equal to val, copy nums[j] to nums[i] and then increment i.
• After processing, i will represent the new length of the array with all the elements not equal to val in the first i positions.

Example Walkthrough (using Example 2):

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

1. Start:

   • i = 0
   • j = 0 → nums[0] = 0 is not 2 → assign nums[0] = 0, increment i to 1.

2. Next:

   • j = 1 → nums[1] = 1 is not 2 → assign nums[1] = 1, increment i to 2.

3. j = 2:

   • nums[2] = 2 equals val → do nothing, i remains 2.

4. j = 3:

   • nums[3] = 2 equals val → do nothing, i remains 2.

5. j = 4:

   • nums[4] = 3 is not 2 → assign nums[2] = 3 (overwriting a 2), increment i to 3.

6. j = 5:

   • nums[5] = 0 is not 2 → assign nums[3] = 0, increment i to 4.

7. j = 6:

   • nums[6] = 4 is not 2 → assign nums[4] = 4, increment i to 5.

8. j = 7:

   • nums[7] = 2 equals val → do nothing.

After the loop, i = 5. The first 5 elements of nums now contain the valid elements [0, 1, 3, 0, 4].

Complexity:

• Time: O(n) since we traverse the array once.

• Space: O(1) since only constant extra space is used.

Code Implementations

Python Implementation