algoadvance

Leetcode 27. Remove Element

Problem Statement

The problem asks you to remove all instances of a specific value from an array, modifying the array in place, and return the new length of the array. The relative order of the elements may be changed. It doesn’t matter what values are set beyond the new length.

Example:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 2. It doesn't matter what you leave beyond the returned length.

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 length = 5, with the first five elements of nums containing 0, 1, 4, 0, and 3. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.

Clarifying Questions

  1. Q: Does the function need to handle empty arrays? What should be returned?
    • A: Yes, it should handle empty arrays. If the array is empty, the function should return 0.
  2. Q: Can we use additional space for another array?
    • A: No, you need to solve the problem in place with O(1) extra space.
  3. Q: Does the order of remaining elements matter?
    • A: No, the relative order does not matter.

Strategy

  1. Use the two-pointer technique to solve this problem.
  2. One pointer (i) iterates through the array, and the other (j) keeps track of positions for non-target elements.
  3. Whenever a non-target element is found, it is placed in the position indicated by the second pointer (j), and j is then incremented.
  4. After the loop completes, j will be the new length of the array without the specified value.

Code

#include <vector>
using namespace std;

int removeElement(vector<int>& nums, int val) {
    int j = 0; // The second pointer
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != val) {
            nums[j] = nums[i];
            j++;
        }
    }
    return j;
}

Time Complexity

This strategy ensures that we efficiently remove the specified value from the array while keeping the order of remaining elements arbitrary, fulfilling the in-place modification requirement.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI