Remove Duplicates
Given a sorted list of numbers with length at least 1, remove duplicates and return the new length. You must do this in-place and without using extra memory.
Input: [0, 0, 1, 1, 1, 2, 2].
Output: 3.
Your function should modify the list in place so that the first three elements become 0, 1, 2. Return 3 because the new length is 3.
Try it yourself
Explanation
Intuition
If we could use extra memory, we could easily solve this by going through the list once and using a hash set to record elements we have seen. But we are not allowed extra memory so we have to look at the conditions and see if there's anything we could use. An important condition is that the numbers are sorted, which means the same numbers are next to each other. This means as we go through the list, once we see a number A, we will see all occurrences of A together, and will not see A again after we see B. Using this key observation, we can devise a fast/slow pointer solution.
Time Complexity: O(n)
We simply traverse the array once, moving from left to right.
Space Complexity: O(1)
Draw a figure
1def remove_duplicates(arr: list[int]) -> int:
2 slow = 0
3 for fast in range(len(arr)):
4 if arr[fast] != arr[slow]:
5 slow += 1
6 arr[slow] = arr[fast]
7 return slow + 1
8
9if __name__ == "__main__":
10 arr = [int(x) for x in input().split()]
11 res = remove_duplicates(arr)
12 print(" ".join(map(str, arr[:res])))
131import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int removeDuplicates(List<Integer> arr) {
8 int slow = 0;
9 for (int fast = 0; fast < arr.size(); fast++) {
10 if (!arr.get(fast).equals(arr.get(slow))) {
11 slow++;
12 arr.set(slow, arr.get(fast));
13 }
14 }
15 return slow + 1;
16 }
17
18 public static List<String> splitWords(String s) {
19 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
20 }
21
22 public static void main(String[] args) {
23 Scanner scanner = new Scanner(System.in);
24 List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
25 scanner.close();
26 int res = removeDuplicates(arr);
27 System.out.println(arr.stream().limit(res).map(String::valueOf).collect(Collectors.joining(" ")));
28 }
29}
301using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7 public static int RemoveDuplicates(List<int> arr)
8 {
9 if (arr == null || arr.Count == 0)
10 {
11 return 0;
12 }
13
14 int slow = 0;
15 for (int fast = 0; fast < arr.Count; fast++)
16 {
17 if (arr[fast] != arr[slow])
18 {
19 slow++;
20 arr[slow] = arr[fast];
21 }
22 }
23 return slow + 1;
24 }
25
26 public static List<string> SplitWords(string s)
27 {
28 return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
29 }
30
31 public static void Main()
32 {
33 List<int> arr = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
34 int res = RemoveDuplicates(arr);
35 Console.WriteLine(string.Join(" ", arr.Take(res)));
36 }
37}
381"use strict";
2
3function removeDuplicates(arr) {
4 let slow = 0;
5 for (let fast = 0; fast < arr.length; fast++) {
6 if (arr[fast] !== arr[slow]) {
7 slow++;
8 arr[slow] = arr[fast];
9 }
10 }
11 return slow + 1;
12}
13
14function splitWords(s) {
15 return s === "" ? [] : s.split(" ");
16}
17
18function* main() {
19 const arr = splitWords(yield).map((v) => parseInt(v));
20 const res = removeDuplicates(arr);
21 console.log(arr.slice(0, res).join(" "));
22}
23
24class EOFError extends Error {}
25{
26 const gen = main();
27 const next = (line) => gen.next(line).done && process.exit();
28 let buf = "";
29 next();
30 process.stdin.setEncoding("utf8");
31 process.stdin.on("data", (data) => {
32 const lines = (buf + data).split("\n");
33 buf = lines.pop();
34 lines.forEach(next);
35 });
36 process.stdin.on("end", () => {
37 buf && next(buf);
38 gen.throw(new EOFError());
39 });
40}
411function removeDuplicates(arr: number[]): number {
2 let slow = 0;
3 for (let fast = 0; fast < arr.length; fast++) {
4 if (arr[fast] !== arr[slow]) {
5 slow++;
6 arr[slow] = arr[fast];
7 }
8 }
9 return slow + 1;
10}
11
12function splitWords(s: string): string[] {
13 return s === "" ? [] : s.split(" ");
14}
15
16function* main() {
17 const arr = splitWords(yield).map((v) => parseInt(v));
18 const res = removeDuplicates(arr);
19 console.log(arr.slice(0, res).join(" "));
20}
21
22class EOFError extends Error {}
23{
24 const gen = main();
25 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
26 let buf = "";
27 next();
28 process.stdin.setEncoding("utf8");
29 process.stdin.on("data", (data) => {
30 const lines = (buf + data).split("\n");
31 buf = lines.pop() ?? "";
32 lines.forEach(next);
33 });
34 process.stdin.on("end", () => {
35 buf && next(buf);
36 gen.throw(new EOFError());
37 });
38}
391#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int remove_duplicates(std::vector<int>& arr) {
9 int slow = 0;
10 for (int fast = 0; fast < arr.size(); fast++) {
11 if (arr.at(fast) != arr.at(slow)) {
12 slow++;
13 arr.at(slow) = arr.at(fast);
14 }
15 }
16 return slow + 1;
17}
18
19template<typename T>
20std::vector<T> get_words() {
21 std::string line;
22 std::getline(std::cin, line);
23 std::istringstream ss{line};
24 ss >> std::boolalpha;
25 std::vector<T> v;
26 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
27 return v;
28}
29
30template<typename T>
31void put_words(const std::vector<T>& v) {
32 if (!v.empty()) {
33 std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
34 std::cout << v.back();
35 }
36 std::cout << '\n';
37}
38
39int main() {
40 std::vector<int> arr = get_words<int>();
41 int res = remove_duplicates(arr);
42 arr.resize(res);
43 put_words(arr);
44}
451use std::error;
2use std::io;
3use std::str::FromStr;
4
5fn remove_duplicates(arr: &mut Vec<i32>) -> usize {
6 if arr.is_empty() {
7 return 0;
8 }
9
10 let mut write_index = 1;
11 for i in 1..arr.len() {
12 if arr[i] != arr[i - 1] {
13 arr[write_index] = arr[i];
14 write_index += 1;
15 }
16 }
17
18 write_index
19}
20
21fn main() -> Result<(), Box<dyn error::Error>> {
22 let mut line = String::new();
23 io::stdin().read_line(&mut line)?;
24 let mut arr = line
25 .split_whitespace()
26 .map(i32::from_str)
27 .collect::<Result<Vec<_>, _>>()?;
28
29 let res = remove_duplicates(&mut arr);
30 println!("{}", arr.iter().take(res).map(|x| x.to_string()).collect::<Vec<String>>().join(" "));
31 Ok(())
32}
33Visualizer quick tour. Use the interactive visualizer below to step through the slow/fast pointer updates: pick a preset (e.g., "Example 1"), hit Play to watch the algorithm run, or tap Step to advance one pointer movement at a time. You can also edit the input array to test your own cases and see how the visual states change in real time.