27. Remove Element
Model: qwen2.5-coder:14b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 49.5%
Problem Breakdown
The problem requires us to remove all instances of a given value val from an array nums in-place, meaning we cannot use additional space for another array. The function should return the new length of the array after removals. The order of elements beyond the new length does not matter.
Inputs:
- An integer array
nums. - An integer
val.
Outputs:
- An integer representing the new length of the array after removing all instances of
val. - The first
new_lengthelements ofnumsshould be modified in-place to excludeval.
Implicit Constraints and Edge Cases:
- If
numsis empty, the function should return 0. - If
valis not present innums, the array remains unchanged. - All elements in
numsare within the range [0, 50]. - The length of
numscan be up to 100.
Intuition
A brute-force approach would involve iterating through the array and creating a new array without the value val. However, this requires extra space, which is not allowed. Instead, we need an in-place solution.
The key insight is to use two pointers: one to iterate through the array (i) and another to track the position where the next non-val element should be placed (j). This way, we can overwrite elements equal to val with subsequent elements that are not equal to val.
Approach
- Initialize a pointer
jto 0. - Iterate through the array using a pointer
i. - For each element in the array:
- If the element is not equal to
val, place it at positionjand incrementj.
- If the element is not equal to
- After the loop,
jwill be the new length of the array with all instances ofvalremoved.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array. We iterate through the array once.
- Space Complexity: O(1). We use only a constant amount of extra space for the pointers.
Solution
def removeElement(nums, val):
j = 0
for i in range(len(nums)):
if nums[i] != val:
nums[j] = nums[i]
j += 1
return j
Edge Cases Handled
- Empty Array: If
numsis empty, the loop does not execute, andjremains 0. The function correctly returns 0. - No Instances of
val: Ifvalis not present innums, all elements are copied to their original positions, andjequals the length ofnums. - All Elements Equal to
val: If all elements innumsare equal toval, the loop overwrites all elements with subsequent non-valelements (none exist), andjremains 0. The function correctly returns 0. - Single Element Array: Handles both cases where the single element is equal to or not equal to
val.