27. Remove Element

Intuition:

The problem asks us to remove all occurrences of a given value val from the array nums in-place and return the count of elements in the modified array. The order of the elements may change after the removal.

Approach:

Counting Occurrences: We first need to determine how many occurrences of val exist in the array nums. This can be done by iterating through the array and counting each occurrence.

Two Pointers Approach: After counting occurrences, we calculate the desired length of the modified array by subtracting the count of val occurrences from the total length of the array. Then, we use a two-pointers approach to modify the array in-place.

Initialize two pointers, i at the beginning (index 0) and j at the end (index n - 1, where n is the length of the array).

Iterate until i crosses the desired length or meets j.

If nums[i] is equal to val and nums[j] is not equal to val, swap nums[i] and nums[j], decrement j, and increment i.

If nums[i] is not equal to val, increment i.

If nums[j] is equal to val, decrement j.

Repeat until i crosses the desired length or meets j.

Return Length of Modified Array: Finally, return the desired length of the modified array.

Complexity Analysis:

Time Complexity:

Counting occurrences: O(n), where n is the length of the array nums.
Two pointers approach: O(n), where n is the length of the array nums.
Overall, the time complexity is O(n).

Space Complexity:

The solution modifies the array in-place without using any additional space. Hence, the space complexity is O(1).

Code


public class Solution {
    public int RemoveElement(int[] nums, int val) {
        int n = nums.Length;
        int k = 0;
        foreach(int a in nums) {
            if(a == val) k++;
        }
        int i = 0; 
        int j = n-1;
        int ret = n - k;

        while(i < ret && j > 0 && i < n) {
            if(nums[i] == val && nums[j] != val) {
                nums[i] = nums[j];
                j--;
                i++;
            }
            else if(nums[i] != val) i++;
            else if(nums[j] == val) j--;
        }

        return ret;
    }
}

Summary:

The solution efficiently removes all occurrences of a given value val from the array nums in-place using a two-pointers approach. It maintains the order of the elements and returns the count of non-val elements in the modified array. The time complexity of the solution is O(n), where n is the length of the array nums, and the space complexity is O(1).

Blog Posts