27. Remove Element¶

Given an array and a val remove all it occurrences in-place and return the number of remaining elements

Input: 
nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]

if there are k occurrence of val change the array nums such that the first k elements of nums contain the elements which are not equal to val.

Intuition¶

• An element shifts by the occurrence amount of val before it.

Approach¶

• Start from beginning of the array tracking the occurrence of val (lets say its tracked by i)
• Move an elements i steps forward in array if there are i occurrence of val before it.

Complexity¶

• Time complexity : \(\text{O}(n)\)
• as we iterate the array only once
• Space complexity : \(\text{O}(1)\)
• No extra space is needed as everything is done in place

Code¶

public int removeElement(int[] nums, int val) {
    // This will track the occurrence count of the val
    int placesToBeMovedBy = 0;

    for (int i = 0; i < nums.length; ++i) {
        // If current value is val increase the occurrence count and continue 
        if(nums[i] == val) {
            placesToBeMovedBy++;
            continue;
        } 

        // If there is an occurence of val we can overwrite it
        nums[i - placesToBeMovedBy] = nums[i];
    }

    return nums.length - placesToBeMovedBy;
}

Comments