27. Remove Element

Resources: Remove Element - LeetCode

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.

Stack

• DS: Arrays
• Algo:
• Technique: Pattern Ghost Array

---

Solutions

Mine

class Solution {
public:
    
    int removeElement(vector<int>& nums, int val) {
        
        if(nums.size()==0){
            return 0;
        }
        
        vector <int>::iterator valit = nums.end()-1;
        vector <int>::iterator arrit = nums.end() -2;
 
        // find first non val
        while(*valit == val && valit > nums.begin()) {
            valit--;    
        }
        
        // if valit reaches begin
        if(valit == nums.begin()){
            if(*valit == val)
                return 0;
            return 1;
        }
            
        
        arrit = valit-1;
        
        // if *arrit = *valit
        while(arrit >= nums.begin()){
            if(*arrit == val){
                iter_swap(valit, arrit);
                valit--;
            }
            arrit--;
        }
        
        // return count of remaingin array
        int count = 0;
        while(valit >= nums.begin()){
            valit--;
            count++;
        }
        
        return count;
    }
};

Official

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

Explanation

Mine Simple Reverse two pointer, at the same end, one stays in front of the first non-target element from the back. The other traverses the array to find targets to swap with. Official Rewrite the array from the start, as thought it were a ghost array using a pointer, and let the other pointer run forward to find the next element thats not a “val” Second Official just keep writing elements from the end of the array to the val indexes

Insights

Time Complexity: O(N) Space Complexity: O(1)

Related