Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Remove Duplicates from Sorted Array

Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

The array is sorted in non-decreasing order. Remove the duplicates in place and print how many unique values remain, then the unique values.

Input

First line: n. Second line: n space-separated integers.

Output

First line: k, the number of unique values. Second line: the k unique values in order.

Constraints

Two pointers: one walks the array, the other marks where the next unique value goes.

Example 1

Input

3
1 1 2

Output

2
1 2

Example 2

Input

10
0 0 1 1 1 2 2 3 3 4

Output

5
0 1 2 3 4

Hints

  1. Because the array is sorted, duplicates sit next to each other.
  2. Keep a write pointer k: copy a[i] to a[k] only when a[i] differs from a[k - 1].

Approach

Two pointers. k is the length of the unique prefix built so far (starting at 1). Walk i from 1 to n-1; when a[i] != a[k - 1], write it to a[k] and increase k. The first k elements are the answer, and only O(1) extra memory is used.

Complexity: O(n) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    int k = 1;
    for (int i = 1; i < n; i++)
        if (a[i] != a[k - 1]) a[k++] = a[i];
    cout << k << "\n";
    for (int i = 0; i < k; i++) cout << a[i] << (i + 1 < k ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1 : data[0] + 1]
k = 1
for i in range(1, n):
    if a[i] != a[k - 1]:
        a[k] = a[i]
        k += 1
print(k)
print(*a[:k])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        int k = 1;
        for (int i = 1; i < n; i++)
            if (a[i] != a[k - 1]) a[k++] = a[i];
        StringBuilder sb = new StringBuilder().append(k).append("\n");
        for (int i = 0; i < k; i++) sb.append(i > 0 ? " " : "").append(a[i]);
        System.out.println(sb);
    }
}

Solve Remove Duplicates from Sorted Array online · All practice problems