Remove duplicates from-sorted array [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/

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

1. Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
2. Return k.

Example 1:

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

Solution 1 (Basic):

Code:

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        int count = 0;
int index = default;
for (int i = 0; i < nums.Length; i++)
{

    nums[count] = nums[i];
    count++;

    //i = ReturnNextUniqueEleIndex(nums, i);
    index = i;

    for (; index < nums.Length - 1; index++)
    {
        if (nums[index].Equals(nums[index + 1]))
        {                       
            continue;
        }
        else
        {                        
            break;
        }
    }
    i = index;

}
return count;
}
}

Explanation:
Time Complexity:

• The outer loop runs from i = 0 to i < nums.Length, effectively iterating through each element once.
• Inside the outer loop, there’s an inner for loop that advances the index to skip over duplicate elements. In the worst case, this inner loop can traverse multiple elements, but since the outer loop’s index i is updated to the position after the last duplicate, each element is processed at most twice (once in the outer loop and once in the inner loop).
• Overall, each element is visited a constant number of times, leading to a linear time complexity. Therefore, the total 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 and index).
• No additional data structures proportional to the input size are used.
• Hence, the space complexity is O(1).

Solution 2 (Better, Simple):
Code:

    
public class Solution {
public int RemoveDuplicates(int[] nums) {
if (nums.Length == 0)
    {
        return 0;
    }

    int j = 0;
    for (int i = 1; i < nums.Length; i++)
    {
        if (nums[j] != nums[i])
        {
            nums[++j] = nums[i];
        }
    }

    return j + 1;       
}

}

Explanation:

Time Complexity:

1. The algorithm iterates through the array exactly once with a single for-loop from i = 1 to nums.Length – 1.
2. Each comparison and potential assignment inside the loop is an O(1) operation.
3. Therefore, the overall time complexity is O(n), where n is the length of the array.

Space Complexity:

1. The algorithm uses only a few additional variables (j and i), which occupy constant space.
2. It modifies the input array in-place without requiring extra space proportional to the input size.
3. Hence, the space complexity is O(1).

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