0% completed
Problem Statement
Given an array of sorted numbers, move all nonduplicate number instances at the beginning of the array inplace. The nonduplicate numbers should be sorted and you should not use any extra space so that the solution has constant space complexity i.e., O(1).
Move all the unique number instances at the beginning of the array and after moving return the length of the subarray that has no duplicate in it.
Example 1:
Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: The first four elements after moving element will be [2, 3, 6, 9].
Example 2:
Input: [2, 2, 2, 11]
Output: 2
Explanation: The first two elements after moving elements will be [2, 11].
Constraints:
 1 <= nums.length <= 3 * 10<sup>4</sup>
100 <= nums[i] <= 100
nums
is sorted in nondecreasing order.
Solution
In this problem, we need to separate the duplicate elements inplace such that the resultant length of the array remains sorted. As the input array is sorted, one way to do this is to shift the elements left whenever we encounter duplicates. In other words, we will keep one pointer for iterating the array and one pointer for placing the next nonduplicate number. So our algorithm will be to iterate the array and whenever we see a nonduplicate number we move it next to the last nonduplicate number we’ve seen.
StepbyStep Algorithm
 Initialize the Index: Start by initializing a variable
nextNonDuplicate
to 1. This variable will keep track of the position where the next unique element should be placed.  Iterate Through the Array: Loop through the array starting from the second element (index 1) to the end of the array.
 Compare Elements: For each element, check if it is different from the element at the position
nextNonDuplicate  1
. If Different: If the current element is different from the element at
nextNonDuplicate  1
, copy the current element to the positionnextNonDuplicate
.  Increment Index: Increase the
nextNonDuplicate
index by 1 to point to the next position for a unique element.
 If Different: If the current element is different from the element at
 Return Result: After completing the iteration, return the value of
nextNonDuplicate
, which represents the number of unique elements in the array.
Algorithm Walkthrough
Let's walk through the algorithm with the array [2, 3, 3, 3, 6, 9, 9]
:

Initialization: Set
nextNonDuplicate
to 1. Initial Array:
[2, 3, 3, 3, 6, 9, 9]
nextNonDuplicate
= 1
 Initial Array:

Iteration:
 i = 1:
 Compare
arr[0]
(2) witharr[1]
(3)  They are different, so copy
arr[1]
toarr[1]
(no actual change)  Increment
nextNonDuplicate
to 2  Array:
[2, 3, 3, 3, 6, 9, 9]
 Compare
 i = 2:
 Compare
arr[1]
(3) witharr[2]
(3)  They are the same, do nothing
nextNonDuplicate
remains 2
 Compare
 i = 3:
 Compare
arr[1]
(3) witharr[3]
(3)  They are the same, do nothing
nextNonDuplicate
remains 2
 Compare
 i = 4:
 Compare
arr[1]
(3) witharr[4]
(6)  They are different, so copy
arr[4]
toarr[2]
 Increment
nextNonDuplicate
to 3  Array:
[2, 3, 6, 3, 6, 9, 9]
 Compare
 i = 5:
 Compare
arr[2]
(6) witharr[5]
(9)  They are different, so copy
arr[5]
toarr[3]
 Increment
nextNonDuplicate
to 4  Array:
[2, 3, 6, 9, 6, 9, 9]
 Compare
 i = 6:
 Compare
arr[3]
(9) witharr[6]
(9)  They are the same, do nothing
nextNonDuplicate
remains 4
 Compare
 i = 1:

Result: The number of unique elements is
nextNonDuplicate
, which is 4. The modified array is[2, 3, 6, 9, 6, 9, 9]
, and the first four elements[2, 3, 6, 9]
are the unique elements.
Here is the visual representation of this algorithm for Example1:
Code
Here is what our algorithm will look like:
Time Complexity
The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.
Space Complexity
The algorithm runs in constant space O(1).
Similar Questions
Problem 1: Given an unsorted array of numbers and a target ‘key’, remove all instances of ‘key’ inplace and return the new length of the array.
Example 1:
Input: [3, 2, 3, 6, 3, 10, 9, 3], Key=3
Output: 4
Explanation: The first four elements after removing every 'Key' will be [2, 6, 10, 9].
Example 2:
Input: [2, 11, 2, 2, 1], Key=2
Output: 2
Explanation: The first two elements after removing every 'Key' will be [11, 1].
Solution:
This problem is quite similar to our parent problem. We can follow a twopointer approach and shift numbers left upon encountering the ‘key’. Here is what the code will look like:
Time and Space Complexity: The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.
The algorithm runs in constant space O(1).