Remove duplicates from-sorted array-2 [LC150]

Hello friends,

Today we’re going to discuss another Leetcode DSA problem about removing duplicates from-sorted array. link-

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

To change the length of the array in some languages, you need to place the result in the first part of the array nums. Specifically, if there are k elements after removing duplicates, the first k elements of nums should contain the final result, and what remains beyond those elements does not matter.

Return k after placing the final result in the first k slots of nums.

Example 1:

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

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,,]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Solution-1 (Elementory):

        private static int RemoveDuplicates(int[] nums)
        {
            int count = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                nums[count] = nums[i];
                count++;

                if (i < nums.Length - 1 && nums[i] == nums[i + 1])
                {
                    nums[count] = nums[i + 1];
                    count++;
                    i = ReturnNextUniqueIndex(nums, i + 1);
                }
                else
                {
                    i = ReturnNextUniqueIndex(nums, i);
                }
            }
            return count;
        }

        private static int ReturnNextUniqueIndex(int[] nums, int i)
        {
            int index = i;
            for (; index < nums.Length - 1; index++)
            {
                if (nums[index].Equals(nums[index + 1]))
                {
                    continue;
                }
                else
                {
                    return index;
                }
            }
            return index;
        }

Explanation:

The provided code aims to remove duplicates from a sorted array in-place and return the new length of the array with unique elements.

Time Complexity:

• The main method RemoveDuplicates iterates through the array once, with the loop variable i potentially jumping ahead via the ReturnNextUniqueIndex method.
• The ReturnNextUniqueIndex method scans forward to find the next unique element, which in the worst case can traverse the remaining elements.
• Since each element is processed at most twice (once in the main loop and possibly again in ReturnNextUniqueIndex), the overall time complexity is O(2n) = ~O(n), where n is the length of the array.

Space Complexity:

• The algorithm modifies the input array in-place and uses only a few auxiliary variables (count, index), which require constant space.
• Therefore, the space complexity is O(1).

Solution-2 (Cleaner, Better)

private static int RemoveDuplicates2(int[] nums)
        {
            int count = 0;

            for (int i = 0; i < nums.Length; i++)
            {
                nums[count++] = nums[i];

                // If the current element is same as next element (occured twice), copy it in-place.
                if (i < nums.Length - 1 && nums[i] == nums[i + 1])
                {
                    nums[count++] = nums[i + 1];

                    // Skip over all duplicates until next unique element is found.
                    while (i < nums.Length - 1 && nums[i] == nums[i + 1])
                    {
                        i++;
                    }
                }
            }

            return count;
        }

Explanation:

The provided method RemoveDuplicates2 processes the input array to remove duplicates, allowing at most two occurrences of each element.

Time Complexity:

• The algorithm iterates through the array once with a for loop, which runs in O(n) time, where n is the length of the array.
• Inside the loop, the while loop advances the index i over consecutive duplicates, but since i only moves forward, the total number of iterations across both loops is proportional to n.
• Therefore, the overall time complexity is O(n).

Space Complexity:

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

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