Remove occurences Editorial

Practice Problem Link: Remove occurences

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array and a number k, remove all occurrences of k from the array (in-place). Return the number of elements 'remainingSize' left after removing k. There can be anything beyond the first 'remainingSize' elements. It will be ignored.

Approach

The approach to solve this is to use the method of 2 pointers, to move the current element with the value equal to k to the end of array by incrementing its current pointer appropriately ahead to its proper position.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int removeOccurences(vector<int> A, int k) {
	int n = A.size();
	int j = 0;
	for (int i = 0; i < n; i++) {
		if (A[i] != k) {
			A[j++] = A[i];
		}
	}
	return j;
}

Java

class Solution {
	int removeOccurences(int[] A, int k) {
		int n = A.length;
		int j = 0;
		for (int i = 0; i < n; i++) {
			if (A[i] != k) {
				A[j++] = A[i];
			}
		}
		return j;
	}
}