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;
}