leetcode lnk :-

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

Introduction:

In this blog post, we will explore the "Remove Duplicates from Sorted Array" problem on LeetCode and provide a solution in Java. We will discuss the problem statement, the approach used, the time and space complexity, and provide the solution code.

Problem Description:

Given sorted array nums, our task is to remove the duplicate elements in-place such that each element appears only once. We need to modify the input array and return the new length of the array.

Approach:

To solve this problem, we can use a two-pointer approach. We will maintain two pointers, p1 and p2, where p1 points to the current position where we want to place the next unique element, and p2 is used to iterate through the array.

We start with p1 at the first index (0) and p2 at the second index (1). We iterate through the array, comparing the elements at nums[p1] and nums[p2]. If they are the same, we increment p2 to move to the next element. If they are different, we increment p1, update the value at nums[p1] to the value at nums[p2], and then increment both p1 and p2.

We continue this process until p2 reaches the end of the array. Finally, we return p1 + 1, which represents the new length of the modified array.

Time Complexity:

The two-pointer approach allows us to solve this problem in a single pass through the array, resulting in a linear time complexity of O(n), where n is the length of the input array.

Space Complexity:

Since we are modifying the input array in-place without using any extra data structures, the space complexity is O(1), constant space.

Solution in Java:

javaCopy codeclass Solution {
    public int removeDuplicates(int[] nums) {
        int p1 = 0;
        int p2 = 1;

        while (p2 < nums.length) {
            if (nums[p1] == nums[p2]) {
                p2++;
            } else {
                p1++;
                nums[p1] = nums[p2];
                p2++;
            }
        }

        return p1 + 1;
    }
}

Conclusion: In this blog post, we discussed the "Remove Duplicates from Sorted Array" problem, its approach using two pointers, and provided a solution in Java. We analyzed the time and space complexity, which is O(n) and O(1) respectively. The provided solution code can be used to remove duplicates from a sorted array efficiently.