You are given a sorted array and its length. Arrange the array so that there are no duplicates up to certain range. Return the large .
Example:
INPUT :
1 | 2 | 2 | 3 | 3 |
OUTPUT:
1 | 2 | 3 | 2 | 3 |
Return 3
Let’s understand the question.
We are given a sorted array if there are any duplicate elements then we need to arrange the array in such a way that the 1st k elements are unique. We need to return the k.
1 | 2 | 2 | 3 | 3 |
2 and 3 are duplicate
1 | 2 | 3 | 2 | 3 |
Here 1st 3 are unique
Return 3
Step 1: Initialize a variable k with 1 which is used to store the first k unique elements in the array.
Step 2: Check whether the length of array is 0 or not. If so return 0 i.e. no such k.
Step 3: Store the first value of the array to a variable x.
Step 4: Run a loop from second to last element in the array
Step 5: Check another x! = arr[i]
if so
Change x = arr[i]
Swap arr[k] and arr[i]
Here we are checking whether the 1st value not equal to 2nd value then change the current value to x and swap with current index k and arr[i].
Step 6: Increment k by 1 to increase the count of unique elements as the condition is true i.e. the elements are not same.
Step 7: Repeat steps 4 to 6 until reach the end of array.
Step 8: Return value k which is the number 1st k unique elements in the array.
1 2 2 3 3 1 2 2 3 3
1 2 3 2 3 | k x i arr[i] arr[k] 1 1 2 2 1 2 2 2 ← Equal arr[x] = arr[i]
3 3 3 2 3 x! = arr[i]
4 ← Equal arr[x] = arr[j] |
Time complexity: O(n) /length of the array
Space complexity: O(1)