Problem of the day
You are given a sorted integer array 'arr' of size 'n'.
You need to remove the duplicates from the array such that each element appears only once.
Return the length of this new array.
Do not allocate extra space for another array. You need to do this by modifying the given input array in place with O(1) extra memory.
'n' = 5, 'arr' = [1 2 2 2 3].
The new array will be [1 2 3].
So our answer is 3.
The first line contains an integer ‘n’ denoting the number of elements in the array.
The second line contains ‘n’ space-separated integers representing the elements of the array.
Output format:
Return the length of the modified array.
Note:
You don't need to print anything, it has already been taken care of. Just Implement the given function.
10
1 2 2 3 3 3 4 4 5 5
5
The new array will be [1 2 3 4 5].
So our answer is 5.
9
1 1 2 3 3 4 5 5 5
5
The expected time complexity is O(n).
1 <= 'n' <= 10^6
-10^9 <= 'arr[i]' <=10^9
Where ‘arr[i]’ is the value of elements of the array.
Time limit: 1 sec
Keep a pointer which will point to the index of the array where you can store the next value. Now think about how you can define another pointer to keep track of next value.
We know that the array is sorted, and hence all the occurrences of a number will be clustered together. Keeping this in mind, we keep two pointers 'i' and ‘j’, where ‘i’ is the slow pointer and ‘j’ is the fast pointer.
Now, as long as ‘arr[i]’ == ‘arr[j]’ -> we keep on incrementing ‘j’ to skip all the duplicates.
Now, when we encounter ‘arr[i]’ != ‘arr[j]’ -> the duplicate run ends, and hence now, we must copy the value of ‘arr[j]’ to ‘arr[i+1]’, ‘i’ is then incremented.
We repeat the same process until j reaches the end of the array. Return the value of ‘i’ at the end.
O(n), Where ‘n’ is the length of the array.
We will do ‘n’ - 1 checks, and thus the time complexity will be O(n).
O(1).
Since constant extra space is required, thus the space complexity will be O(1).