Remove array element in-place [LC150]

Hello friends,

Today we’re going to discuss another Leetcode DSA problem about removing array element in-place. link- https://leetcode.com/problems/remove-element/description

Given an integer array nums and an integer val, remove all instances of val from nums in place. The order of elements can be changed. Return the count of elements in nums that are not equal to val.

Consider the count of elements in nums that are not val, which we call k. To be accepted, you need to do the following:

• Change the array nums so that the first k elements contain elements not equal to val. The rest of nums doesn’t matter.
• Return k.

Example 1:

Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2,_,_] Explanation: Your function should return k = 2, with the first two elements of nums being 2.It does not matter what you leave beyond the returned k (hence they are underscores). Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4. Note that the five elements can be returned in any order.It does not matter what you leave beyond the returned k (hence they are underscores).

Solution:

Time complexity: O(n), Space complexity: O(1)
Code:

int count = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != val)
                {
                    nums[count] = nums[i];
                    count++;
                }
            }
            return count;

Explanation:

The provided code iterates through the array nums once, checking each element to see if it is not equal to val. When an element is not equal to val, it is copied to the position indicated by count, which is then incremented. Finally, the function returns count, representing the number of elements not equal to val.

Time Complexity:

• The loop runs exactly n times, where n is the length of nums.
• Each iteration performs a constant amount of work (comparison and assignment).
• Therefore, the overall time complexity is O(n).

Space Complexity:

• The algorithm modifies the input array in-place and uses only a few additional variables (count, i).
• No extra space proportional to the input size is used.
• Hence, the space complexity is O(1).

Hope you liked the article. Please share your comment/ suggestion.