Squeeze out the duplicates
EasyStuck?
Show a hintHide the hint
The list is sorted, so a value is new exactly when it differs from the one immediately before it. One pass, one comparison each.
The ideas behind this problem
Next in this lesson
Reads the same backwardsA sorted list may repeat values. Return how many distinct values it holds.
Because the list is sorted, equal values sit next to each other, so a value is new exactly when it differs from the one before it.
Worked example#
For [0, 0, 1, 1, 1, 2, 2, 3, 3, 4], walk once and count only the values that differ from their left neighbour:
| position | value | same as previous? | distinct so far |
|---|---|---|---|
| 0 | 0 | first one | 1 |
| 1 | 0 | yes, skip | 1 |
| 2 | 1 | no, count it | 2 |
| 3 | 1 | yes, skip | 2 |
| 4 | 1 | yes, skip | 2 |
| 5 | 2 | no, count it | 3 |
| 6 | 2 | yes, skip | 3 |
| 7 | 3 | no, count it | 4 |
| 8 | 3 | yes, skip | 4 |
| 9 | 4 | no, count it | 5 |
The answer is 5.
The same walk is what actually removes the duplicates in place: keep a second index for where the next distinct value should be written, and advance it only when you count one. That is the two pointer idea, one reading and one writing.
Constraints#
1 <= n <= 200000- The values are given in non-decreasing order
Input
nums is a count then that many integers, in non-decreasing order.
Output
The number of distinct values.
Examples
Input
3 1 1 2
Output
2
Only 1 and 2 appear, so two distinct values.
Input
10 0 0 1 1 1 2 2 3 3 4
Output
5
The distinct values are 0, 1, 2, 3 and 4.
Input
1 7
Output
1
A single value is one distinct value.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.