Remove Duplicates from an Array: flowchart, algorithm and program
This program reads n numbers and prints them with duplicates removed, keeping only the first time each value appears. It builds a second array, result, and adds a number to it only if it is not already there.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read n.
- Step 3: Set i = 0.
- Step 4: If i < n, go to step 5; otherwise go to step 7.
- Step 5: Read arr[i].
- Step 6: Increase i by 1. Go to step 4.
- Step 7: Set k = 0, i = 0.
- Step 8: If i < n, go to step 9; otherwise go to step 17.
- Step 9: Set found = 0, j = 0.
- Step 10: If j < k, go to step 11; otherwise go to step 14.
- Step 11: If arr[i] == result[j], go to step 12; otherwise go to step 13.
- Step 12: Set found = 1. Go to step 14.
- Step 13: Increase j by 1. Go to step 10.
- Step 14: If found == 0, go to step 15; otherwise go to step 16.
- Step 15: Set result[k] = arr[i]; k++.
- Step 16: Increase i by 1. Go to step 8.
- Step 17: Set i = 0.
- Step 18: If i < k, go to step 19; otherwise go to step 21.
- Step 19: Print result[i].
- Step 20: Increase i by 1. Go to step 18.
- Step 21: Stop.
Program in C, Python and Java
Remove Duplicates from an Array program in C
#include <stdio.h>
int main() {
int n, i, j, k, found;
int arr[100], result[100];
printf("Enter n: ");
scanf("%d", &n);
printf("Enter %d numbers: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
k = 0;
for (i = 0; i < n; i++) {
found = 0;
for (j = 0; j < k; j++) {
if (arr[i] == result[j]) {
found = 1;
break;
}
}
if (found == 0) {
result[k] = arr[i];
k++;
}
}
printf("Array without duplicates: ");
for (i = 0; i < k; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}Remove Duplicates from an Array program in Python
n = int(input("Enter n: "))
arr = list(map(int, input("Enter " + str(n) + " numbers: ").split()))
result = []
for i in range(n):
found = False
for j in range(len(result)):
if arr[i] == result[j]:
found = True
break
if not found:
result.append(arr[i])
print("Array without duplicates:", end=" ")
for x in result:
print(x, end=" ")
print()Remove Duplicates from an Array program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
int[] arr = new int[n];
int[] result = new int[n];
System.out.print("Enter " + n + " numbers: ");
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int k = 0;
for (int i = 0; i < n; i++) {
boolean found = false;
for (int j = 0; j < k; j++) {
if (arr[i] == result[j]) {
found = true;
break;
}
}
if (!found) {
result[k] = arr[i];
k++;
}
}
System.out.print("Array without duplicates: ");
for (int i = 0; i < k; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
}
}
Sample input: n = 7, numbers = 4 2 4 5 2 7 5
Output: Array without duplicates: 4 2 5 7
How it works
- k is the count of items stored in result so far. It starts at 0, so result is empty at the beginning.
- The outer loop picks each arr[i] in order, and found is reset to 0 for every new element.
- The inner loop compares arr[i] with result[0] to result[k-1]. If it matches one, found becomes 1 and break stops the search early.
- If found is still 0 after the inner loop, the number is new, so it goes into result[k] and k increases by 1.
- Because we go left to right and only add unseen values, the first occurrence is always the one kept, and the original order is preserved.
- At the end, only the first k items of result are printed. For 4 2 4 5 2 7 5 the output is 4 2 5 7.
Dry run (trace table)
| Step | Line | Box | n | i | arr | k | found | j | result | Output |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||||||
| 2 | 8 | Read n | 7 | |||||||
| 3 | 11 | i = 0 | 7 | 0 | ||||||
| 4 | 11 | i < n? | 7 | 0 | ||||||
| 5 | 12 | Read arr[i] | 7 | 0 | [4] | |||||
| 6 | 11 | i++ | 7 | 1 | [4] | |||||
| 7 | 11 | i < n? | 7 | 1 | [4] | |||||
| 8 | 12 | Read arr[i] | 7 | 1 | [4,2] | |||||
| 9 | 11 | i++ | 7 | 2 | [4,2] | |||||
| 10 | 11 | i < n? | 7 | 2 | [4,2] | |||||
| 11 | 12 | Read arr[i] | 7 | 2 | [4,2,4] | |||||
| 12 | 11 | i++ | 7 | 3 | [4,2,4] | |||||
| 13 | 11 | i < n? | 7 | 3 | [4,2,4] | |||||
| 14 | 12 | Read arr[i] | 7 | 3 | [4,2,4,5] | |||||
| 15 | 11 | i++ | 7 | 4 | [4,2,4,5] | |||||
| 16 | 11 | i < n? | 7 | 4 | [4,2,4,5] | |||||
| 17 | 12 | Read arr[i] | 7 | 4 | [4,2,4,5,2] | |||||
| 18 | 11 | i++ | 7 | 5 | [4,2,4,5,2] | |||||
| 19 | 11 | i < n? | 7 | 5 | [4,2,4,5,2] | |||||
| 20 | 12 | Read arr[i] | 7 | 5 | [4,2,4,5,2,7] |
Time and space complexity
Time: O(n²) · Space: O(n). Each of the n elements is compared with up to k unique results collected so far, and a result array of size n is stored.
Common mistakes
- Not resetting found = 0 inside the outer loop, so after one duplicate every later number looks like a duplicate too.
- Running the inner loop up to n instead of k, which compares against result slots that have no values yet.
- Printing n elements of result instead of k, which shows garbage values after the unique ones.
Viva questions
Q1. What is the purpose of the variable k in this program?
k counts how many unique values are stored in result so far. It is also the index where the next unique value will be placed, and the inner loop uses it as the limit so only filled positions are checked.
Q2. Why is found set to 0 at the start of each outer loop iteration (line 17)?
Each element of arr needs a fresh check. If found kept the value 1 from an earlier element, the next element would be wrongly treated as a duplicate and skipped.
Q3. Why does the inner loop run j from 0 to k-1 and not to n-1?
Only the first k positions of result hold real values; the rest are uninitialised garbage. Comparing against them could give false matches, so the loop stops at k.
Q4. What does the break on line 21 do, and is the program still correct without it?
It leaves the inner loop as soon as a match is found, since there is no need to keep searching. Without it the output is still correct, just slightly slower because the loop continues to the end of the unique values.
Q5. What happens if the user enters n = 0 or n = 1?
With n = 0 both loops are skipped, k stays 0, and the program prints only the message with no numbers. With n = 1 the single element is added to result, so it is printed as is. The program does not check that n is at most 100, so a larger n would overflow the arrays.
Q6. Trace the input 4 numbers: 2 3 2 5. What is the output and what is k at the end?
2 is added (k=1), 3 is added (k=2), the second 2 is found in result so it is skipped, and 5 is added (k=3). The output is '2 3 5' and k is 3. The first-occurrence order is preserved.
Q7. What is the time complexity of this algorithm, and when is the worst case?
It is O(n²), because each of the n elements may be compared with up to k stored values. The worst case is when all elements are distinct, giving about n(n-1)/2 comparisons. The best case is when all are the same, which gives O(n). Extra space is O(n) for result.
Q8. What would you change to make this faster than O(n²)?
Sort the array first and then skip neighbours that are equal, which gives O(n log n), but the original order is lost. Alternatively use a hash table or a boolean lookup array to check 'seen before' in O(1), giving O(n) overall.
Frequently asked questions
Does this program keep the first or the last occurrence of a duplicate?
It keeps the first occurrence. Elements are checked left to right, and a number is added to result only if it is not already there, so later copies are skipped.
What is the time complexity of removing duplicates this way?
It is O(n^2) in the worst case, because each of the n elements may be compared with up to k items already in result. It uses O(n) extra space for the result array.
Why do we need the found variable and break?
found tells us after the inner loop whether arr[i] was already in result. break stops the inner loop as soon as a match is seen, which saves needless comparisons.