Leetcode 27: Remove Duplicates from Sorted Array

 

1. Problem Statement (Simple Explanation):

You are given:

• An integer array nums

• An integer val

You must:

• Remove all occurrences of val from nums in-place.

• The order of remaining elements may change (no need to keep original order).

• Return k = the number of elements in nums that are not equal to val.

After your function:

• The first k elements of nums must be the elements that are not equal to val (order doesn’t matter).

• The rest of the elements beyond index k - 1 can be anything.

2. Examples:

Example 1:

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

All 3s are removed, remaining elements are [2,2].

Output: k = 2, nums = [2,2,_,_]

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2

Elements not equal to 2 are: 0,1,3,0,4 (any order allowed).

Output: k = 5, nums = [0,1,4,0,3,_,_,_]

Constraints:

• 0 <= nums.length <= 100

• 0 <= nums[i] <= 50

• 0 <= val <= 100

3. Approach – Two Pointers (Write Index):

Since order doesn’t matter for remaining elements, we can use a simple “filter” pattern:

• Use pointer write to indicate the position where the next kept value will be written.

• Use pointer read to scan the array.

Intuition:

• Initialize write = 0.

• Loop read from 0 to n-1:

• If nums[read] != val:

• Write nums[read] to nums[write].

• Increment write.

• If nums[read] == val, skip it (do not write).

• At the end, write is the number of elements not equal to val, i.e., k.

This approach preserves relative order of non-val elements, which is even stronger than required (order may change), and is simple.

Algorithm (Step-by-Step):

1. Initialize write = 0.

2. For read from 0 to len(nums) - 1:

• If nums[read] != val:

• nums[write] = nums[read]

• write++

3. Return write as k.

Pseudo-code:

Complexity:

Let n = len(nums):

• Time: O(n)

• Space: O(1) (in-place)

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code: