Compact a Sorted Array into Its Distinct Prefix
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
The integer array `nums` is sorted in nondecreasing order. Modify it in place so that each distinct value appears once in the beginning of the same array, retaining the original relative order. Return the number `k` of distinct values.
After the call, `nums[0]` through `nums[k - 1]` must contain those values in sorted order. Positions after this prefix are ignored. Return only the integer `k`; the required prefix is an observable change to the argument, not a replacement array returned by the function.
Preserve the original interface:
```cpp
int removeDuplicates(vector<int>& nums);
```
### Examples
```text
Input: nums = [-4,-4,-1,2,2,2,7]
Returned k: 4
Required first k values: [-4,-1,2,7]
```
The values left after the first four positions do not affect correctness.
```text
Input: nums = [6,6,6]
Returned k: 1
Required first k values: [6]
```
### Constraints
- `1 <= nums.length <= 30000`.
- Every input value is between -100 and 100, inclusive.
- The input is already sorted in nondecreasing order.
- The change is in place; the retained prefix preserves the distinct values' original order.
Overview: Compact a sorted array in place into its distinct-value prefix and return that prefix length, preserving relative order.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution
{
public:
int removeDuplicates(vector& nums)
{
int n = nums.size();
if (n == 0)
{
return 0;
}
int i = 0;
for (int j = 1; j < n; j++)
{
if (nums[j] != nums[i])
{
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
};