This is a very general class of problem with many variations. The premise however stays the same. The input array consists of integers, some of which maybe duplicates. We are supposed to print all the unique numbers present in that array.
Eg, int a[] = {23, 56, 56, 7, -19, 23, -19} Expected output : {23, 56, 7, -19}
Solution : The naive solution would be to have two nested for loops. The first loop will scan the array from left to right. At each step, we'll keep track of all the elements seen till that point. The second loop will check if we've already seen this number before. While method gives the correct answer, it is really slow.
Time complexity : O(n^2)
Space complexity : O(n)
public static void printDistinct(int a[]){ if(a==null || a.length==0) return; int seen[] = new int[a.length]; for(int j=0;j<seen.length;j++) seen[j] = Integer.MIN_VALUE; int k=0; for(int i=0;i<a.length;i++){ int j; for(j=0;j<=k;j++){ if(a[i]==seen[j]) break; } if(j>k) seen[k++] = a[i]; } for(int j=0;j<k;j++) System.out.print(seen[j] + " "); }
Note that the lookup step can be made faster. Let's use a boolean array where if we have seen a number we'll mark the cooresponding index as 'true'. This enables us to have a constant time lookup at the expense of added space complexity. We have to make sure that this array is big enough to hold the entire range of numbers present in our input array.
Time complexity : O(n)
Space complexity : O(m) where m = range of the numbers in the input array.
public static void printDistinct(int a[]){ if(a==null || a.length==0) return; int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i=0;i<a.length;i++){ if(a[i] > max) max = a[i]; if(a[i] < min) min = a[i]; } boolean seen[] = new boolean[max-min+1]; for(int i=0;i<a.length;i++) seen[a[i] - min] = true; for(int i=0;i<seen.length;i++) if(seen[i]) System.out.println(i+min); }
While this method is fast, it uses too much space. A better approach would be to use a set. Since a set can not have duplicate elements, we can put all the numbers in a set and then iterate through the set to get all the unique numbers.
Time complexity : O(n)
Space complexity : O(n)
public static void printDistinct(int a[]){ if(a==null || a.length==0) return; Set<Integer> set = new HashSet<Integer>(); for(int i=0;i<a.length;i++) set.add(a[i]); Iterator<Integer> itr = set.iterator(); while(itr.hasNext()) System.out.print(itr.next() + " "); }
The methods described above will work for all inputs. However, some variations of this problem allow us to make additional optimizations. For example,
1. The input array only has numbers from 0 to n-1. Print the repeating elements.
Eg, int a[] = {1, 2, 3, 1, 3, 6, 6} Expected output : {1, 2, 3, 6}
Solution : Since the input array only has numbers from 0 to n-1, we can get rid of the auxillary array used to keep track of the numbers seen till now. Instead, we can directly manipulate the numbers in the array for this purpose.
For each number, check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // i.e., A[abs(A[i])] is negative this element (ith element of list) is a repetition
Time complexity : O(n)
Space complexity : O(1)
public static void printRepeating(int a[]){ if(a==null || a.length==0) return; for(int i=0;i<a.length;i++){ if(a[Math.abs(a[i])] > 0) a[Math.abs(a[i])] = -a[Math.abs(a[i])]; else System.out.print(Math.abs(a[i]) + " "); } }
2. The input array is sorted
Eg, int a[] = {-3, -3, -2, 0, 0, 0, 11, 11, 18, 18} Expected output : {-3, -2, 0, 11, 18}
Solution : Let's make use of the fact that the input array is sorted. This means that all the duplicate elements will be present next to each other. Therefore to find the distinct elements, we scan the array from left to right. Every time we come across a new number, we print it, otherwise we keep scanning till the end of the array.
Time complexity : O(n)
Space complexity : O(1)
public static void printDistinct(int a[]){ if(a==null || a.length==0) return; int prev = a[0]; System.out.print(prev + " "); for(int i=1;i<a.length;i++){ if(a[i]!=prev){ System.out.print(a[i] + " "); prev = a[i]; } } }
3. The input array is made up solely of small prime numbers
Eg, int a[] = {3, 7, 7, 3, 3, 2, 5, 2, 23, 2}
Expected output : {2, 3, 5, 7, 23}
The idea is to leverage the prime factorization of numbers. Let's multiply all the numbers.
Product = 3 * 7 * 7 * 3 * 3 * 2 * 5 * 2 * 23 * 2 = 2^3 * 3^3 * 5 * 7^2 * 23 = 1217160
Every time we come across a number, we'll eliminate that number from the prime factorization of the product by repeatedly dividing the product by that number. For eg the when we come across 3 for the first time, we print it and then keep diving the product by 3 till its no longer divisible by 3.
1217160/3 = 405720/3 = 135240/3 = 45080.
Next time we come across 3, the product won't be divisible and we'll ignore it. Thus we get all the numbers exactly once.
Time complexity : O(n)
Space complexity : O(1)
public static void printDistinct(int a[]){ if(a==null || a.length==0) return; long product = 1; for(int i=0;i<a.length;i++) product = product * a[i]; System.out.println(product); for(int i=0;i<a.length;i++){ if(product % a[i] == 0){ System.out.println(a[i] + " "); while(product % a[i] == 0) product = product / a[i]; } } }
Algorithm 12 Arrays 12 Amazon 12
COMMENTS