Problem 40 - Remove Element

Explore our archive for previous posts.

Problem 39 - Intersection of Two Arrays

Problem 38 - Valid Anagram

Question

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.

• Return k.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 0 <= nums.length <= 100

• 0 <= nums[i] <= 50

• 0 <= val <= 100

Approach

The high-level approach to solving this problem is to traverse the given array while maintaining two indices: i for the current element and newIndex for the new array. We compare each element in the original array with the target value val. If the current element is not equal to val, we copy it to the new array using the newIndex, which is incremented for each valid element. In the end, the new array will contain all elements except val, and newIndex will represent the new length of the modified array.

The key idea is to overwrite elements in the original array in place, effectively removing instances of the target value while maintaining the order of the remaining elements. This process eliminates the need to create a new array, which results in a space-efficient solution.

Solution

Solve it here

class Solution {
    public int removeElement(int[] nums, int val) {
        int newIndex = 0; // Index for the new array without the 'val'.
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[newIndex] = nums[i];
                newIndex++;
            }
        }
        
        return newIndex;
    }
}

Time and space complexity

Time Complexity: The solution has a time complexity of O(n), where n is the length of the input array nums. We iterate through the array once.

Space Complexity: The solution has a space complexity of O(1). It doesn't require any additional data structures that grow with the input size; it only uses a constant amount of space.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Nailing Coding Interviews: Mindset Matters

Ethical Dilemmas in Coding Interviews: Should You Reveal Prior Knowledge?