Question 1
Back to Exercise
Remove duplicates from a sorted int array in place with two pointers, return the number of unique elements, and print the unique part.
Solution
import java.util.Arrays;
public class Main {
static int dedupe(int[] a) {
if (a.length == 0) return 0;
int write = 1;
for (int read = 1; read < a.length; read++) {
if (a[read] != a[write - 1]) a[write++] = a[read];
}
return write;
}
public static void main(String[] args) {
int[][] tests = {{1, 1, 2, 3, 3, 3, 4, 5, 5}, {7, 7, 7}, {}, {1, 2, 3}};
for (int[] t : tests) {
int k = dedupe(t);
System.out.println(k + " " + Arrays.toString(Arrays.copyOf(t, k)));
}
}
}
5 [1, 2, 3, 4, 5] 1 [7] 0 [] 3 [1, 2, 3]
The read pointer scans every element; the write pointer marks where the next new value goes. O(n) time, O(1) extra space.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!