Program to Find Duplicate Elements in Linear Time and Constant Space

  • Write a program to find duplicate elements of array using linear time algorithm and using constant extra memory.

Given an array of integers of size N, which contains elements from 0 to N-1. Input array may contain duplicate elements. We have to print all duplicate elements using linear time and using constant anount of extra space.
For Example :
Input Array : 2 5 3 6 7 1 8 3 4 2
Duplicate Elements : 2, 3

Algorithm to find duplicate elements in O(n) time and O(1) space
Let inputArray be an integer array of size N containing elements from 0 to N-1.
In this method, we are going to use input array as hash table to keep track of whether we found an element earlier or not. We know that array elements are from 0 to N-1, hence always positive. For an array element K, we will modify element at inputArray[K] by multiplying it by -1. Later, If we found a negative element at index K, it means we have earlier modified it and K is a duplicate element. Here is the step by step explanation of this algorithm.
  • Using a loop, traverse inputArray from index 0 to N-1.
  • For every element inputArray[i], if inputArray[inputArray[i]] is positive then multiply it with -1 to make it negative number and continue.
  • If inputArray[inputArray[i]] is negative then inputArray[i] is duplicate element.
Time Complexity : O(n)
Space Complexity : O(1)

C program to find duplicate elements in linear line and without using any extra memory.

#include <stdio.h>
#include <stdlib.h>
 
void printDuplicateNumbers(int *array, int size) {
    int i;
    for (i = 0; i < size; i++) {
        if (array[abs(array[i])] >= 0) {
        /* First occurence of array[i] found, mark the 
 element at index array[i] as negative */
            array[abs(array[i])] = -1 * array[abs(array[i])];
        } else {
        /*If element at index array[i] is negative(array[abs(array[i]) < 0),
  that means we are revisiting element array[i]*/
            printf("%d ", abs(array[i])); 
        }
    }
}
 
int main() {
    int array[500], i, size;
    
    printf("Enter the number of elements in Array\n");
    scanf("%d", &size);
    
    printf("Enter %d numbers\n", size);
    for(i = 0; i < size; i++){
 scanf("%d", &array[i]);
    }
    
    printf("Duplicate Elements\n");
    printDuplicateNumbers(array, size);

    return 0;
}
Output
Enter the number of elements in Array
10
Enter 10 numbers
1 4 3 7 5 3 2 4 9 8
Duplicate Elements
3 4
Posted by
Labels: ,