Remove Duplicates From Sorted Array
Keep each value of a sorted array once, at the front of the same array, and count them.
You are given an array of integers numsnumskknums
Example 1
Output: k = 2, nums = [1, 2, _]
Example 2
Output: k = 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
The Idea
Picture the second example as a row of ten cards, in slots numbered 0 to 9: 0, 0, 1, 1, 1, 2, 2, 3, 3, 4. You want the different values, 0, 1, 2, 3 and 4, at the front of that same row. There is no second row to copy them into, and whatever ends up after them can stay.
Because the row is sorted, all copies of a value sit together. So to tell whether a card is a repeat, you only compare it with the last value you kept, not with every value kept so far. The 1 in slot 3 is a repeat because the last value kept is also 1.
But where do the kept values go, without a second array? They go into the same row, from the front. You can never have kept more cards than you have read, so writing stays at or behind reading. A slot is only written after its own card has been read.
So two markers move through the array in the same direction. One, fastslowslow
In the top row, labelled "partway", fastslowslowfast
The bottom row is the array at the end. The first five slots hold 0, 1, 2, 3, 4, so k
Solution Approach
Turning that idea into code means settling three things: where the two markers start, when the number at fastk
Shifting compared with two markers
What is the simplest way to remove a repeat in place? Move every number after it one slot left, the way deleting a letter in a text editor moves the rest of the line. Each shift can move almost the whole array, so with many repeats the work grows with the square of the array length. The two markers never shift: each number is read once and written at most once.
Where the markers start
Where should slowfastslowfastk
Keeping or skipping a number
How does fastnums[fast]nums[slow]slownums[fast]
The count to return
How do we get kslowslowslow + 1
Java Solution
The method removeDuplicates
- First, if
is empty, return 0, since there is nothing to keep.nums - Set
to 0, so the first number is kept where it is.slow - Move
along the array with a loop, from slot 1 to the last slot.fast - Inside the loop, compare
withnums[fast] . When they differ, movenums[slow] one slot right and copyslow intonums[fast] . When they are equal, do nothing, and the loop movesnums[slow] on.fast - After the loop, return
.slow + 1
The maink
import java.util.Arrays;
public class RemoveDuplicatesFromSortedArray {
public static int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0; // nothing to keep
}
int slow = 0; // nums[0..slow] holds the values kept so far
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) { // a value not kept yet
slow++;
nums[slow] = nums[fast]; // write it into the next free slot
}
}
return slow + 1;
}
static void run(int[] nums) {
int k = removeDuplicates(nums);
System.out.println("k = " + k + ", kept " + Arrays.toString(Arrays.copyOf(nums, k))
+ ", whole array " + Arrays.toString(nums));
}
public static void main(String[] args) {
run(new int[] {1, 1, 2});
run(new int[] {0, 0, 1, 1, 1, 2, 2, 3, 3, 4});
run(new int[] {2, 2, 2});
run(new int[] {-3, -1, 0, 5});
run(new int[] {7});
run(new int[] {});
}
}
Running it prints:
k = 2, kept [1, 2], whole array [1, 2, 2]
k = 5, kept [0, 1, 2, 3, 4], whole array [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
k = 1, kept [2], whole array [2, 2, 2]
k = 4, kept [-3, -1, 0, 5], whole array [-3, -1, 0, 5]
k = 1, kept [7], whole array [7]
k = 0, kept [], whole array []
Look at the second line: the kept slots are [0, 1, 2, 3, 4][1, 1, 2][1, 2, 2]
For [2, 2, 2]slowk[-3, -1, 0, 5]kk
The last line is the empty array, with k = 0slow + 1
The original implementation,
Complexity
The method reads each number once and keeps only two slot numbers besides the array.
- Time: O(n), for an array of n numbers, because
walks over the n numbers once, and each step does one comparison and at most one write.fast - Space: O(1). The repeats are removed inside
itself, and the only extra values arenums andslow .fast
When each value may appear up to twice, the same two markers work with a different check: see