LeetCode Problem Link

https://leetcode.com/problems/remove-element

Intuition

  • At begins, use auxiliary space to make the logic simple.
  • but, I need the space complexity \(O(1)\)!
  • use two pointers!

Approach

  • tried make a simple logic 
      int removeElement(vector<int>& nums, int val) {
      int w=0;
      int r=0;
      for (; r<nums.size(); r++) {
          if (nums[r] == val) {
              if (0==w) {
                  w=r;
              }
          }
          else {
              nums[w++] = nums[r];
          }
      }
      return w;
  • corner case is val:3, nums: [3,3]
  • not possible to use guard clause => val:3, nums: [3,3] or [3,3,3]…
  • tried to use flag if (only_v) w = 0; => val:2, nums: [2,2,3]
  • then, think another way… use flag for the first discovery of val => val:3, nums: [2] 
          bool found = false;
      for (; r<nums.size(); r++) {
          if (nums[r] == val) {
              if (!found) {
                  found = true;
                  w=r;
              }
              else {
              }
          }
          else if (found) {
              nums[w++] = nums[r];
          }
          else {
              continue;
          }
      }
      return w;
  • ok. the final put: if (!found) w = r;
  • the same logic happens in std::erase(std::remove()) skill called Erase-Remove Idiom 
          nums.erase(std::remove(nums.begin(), nums.end(), val), nums.end());
      return nums.size()

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
#if 1
        nums.erase(std::remove(nums.begin(), nums.end(), val), nums.end());
        return nums.size();
#else
        int w=0;
        int r=0;
        bool found = false;
        for (; r<nums.size(); r++) {
            if (nums[r] == val) {
                if (!found) {
                    found = true;
                    w=r;
                }
                else {
                }
            }
            else if (found) {
                nums[w++] = nums[r];
            }
            else {
                continue;
            }
        }
        if (!found) w = r;
        return w;
#endif
    }
};

GitHub

remove-element