Link:: https://leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/727/
up:: [[Leetcode MOC]]
# Remove Duplicates From Sorted Array
## Problem
Given an integer array `nums` sorted in **non-decreasing order**, remove the duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that each unique element appears only **once**. The **relative order** of the elements should be kept the **same**.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are `k` elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.
Return `k` _after placing the final result in the first_ `k` _slots of_ `nums`.
Do **not** allocate extra space for another array. You must do this by **modifying the input array [in-place](https://en.wikipedia.org/wiki/In-place_algorithm)** with O(1) extra memory.
**Custom Judge:**
The judge will test your solution with the following code:
```java
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
```
If all assertions pass, then your solution will be **accepted**.
## Solution
### My Solutions
#### Python
```python
def removeDuplicates(self, nums: List[int]) -> int:
size = 0
i = 0
j = 1
while(j < len(nums)):
if nums[i] != nums[j]:
i += 1 # Only increment slow mover once we hit unique with fast-mover
nums[i] = nums[j]
else:
j += 1
return i + 1
```
#### Rust
```rust
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
let size = 0;
let mut i = 0;
let mut j = 1;
while j < nums.len() {
if nums[i] != nums[j] {
i += 1;
nums[i] = nums[j];
}
else {
j += 1;
}
}
i as i32 + 1
}
```
### LC's
### Java
Since the array is already sorted, we can keep two pointers `i` and `j`, where `i` is the slow-runner while `j` is the fast-runner. As long as $nums[i]=nums[j]$, we increment `j` to skip the duplicate.
When we encounter $nums[j]≠nums[i]$, the duplicate run has ended so we must copy its value to $nums[i+1]$. `i` is then incremented and we repeat the same process again until `j` reaches the end of array.
```java
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
```
## Things I Learned
The two pointer technique is used when working with sorted arrays or lists. Take two pointers, one representing the first element of the array and one representing the last element, then operate on them and increment or decrement as needed. Note: the two pointers don't *need* to start at opposite ends of the array.
- [Source](https://www.geeksforgeeks.org/two-pointers-technique/)
```python
def isPairSum(A, N, X):
# represents first pointer
i = 0
# represents second pointer
j = N - 1
while(i < j):
# If we find a pair
if (A[i] + A[j] == X):
return True
# If sum of elements at current
# pointers is less, we move towards
# higher values by doing i += 1
elif(A[i] + A[j] < X):
i += 1
# If sum of elements at current
# pointers is more, we move towards
# lower values by doing j -= 1
else:
j -= 1
return 0
# array declaration
arr = [2, 3, 5, 8, 9, 10, 11]
# value to search
val = 17
print(isPairSum(arr, len(arr), val))
```
^ymwuzy
## Scratchpad
Using the #Concepts/programming/techniques/two-pointer-technique for this one. Since the array is sorted, we can use this technique, where one pointer starts at the beginning of the array, and one at the end.
In this case, however, we want to have two pointers that start at the same point. A fast runner and a slow runner. Once we finish finding duplicates with the fast runner, we update the slow runner to the fast runner's position and continue.