CareerCup

what about space complexity? It can be solved using hash tables for linear time -> first iterate the second array and insert, then iterate the first and check and check it's values in the hash table

1. Use Hashtable to store the values of second array.
2. Now check if values of first array exists in Hashtable. If no, print the values.

We need to calculate array A minus array B i.e. A-B

Steps:
1-Sort(A) and Sort(B)
2-Traverse for max of two arrays size and create 2 new arrays AIndex and BIndex such that AIndex[i] element key and value both equals to A[i] , VV for BIndex
3- Check ifexists AIndex[A[i]] and BIndex[A[i]] then unset Aindex[A[i]]
4- In the end Aindex will have all elements in A but not in B

PHP Code is --

// Say Arrays are
$a = array('18', '1', '2', '38', '0', '7', '16', '3');
$b = array('8', '2', '1', '7', '9', '38');
sort($a);
sort($b);

for ($i = 0; $i <  max(array(sizeof($a),sizeof($b))); $i++) {    
    if (isset($a[$i])) {
        $aIndex[$a[$i]] = $a[$i];
    }    
    if (isset($b[$i])) {
        $bIndex[$b[$i]] = $b[$i];
    }
    if (isset($aIndex[$a[$i]]) && isset($bIndex[$a[$i]])) {
        unset($aIndex[$a[$i]]);
    }
}



Result is Aindex=  [0,3,16,18]

Time complexity is O(nlogn)

Hi this is Bala, Working as Sr. Software Engineer, I have written a code for you on this just copy and paste it, It will work;

public class TestEx {
public static void main(String[] args) {
int arr[] = { 2, 9, 1, 5, 1, 4, 9, 7, 2, 1, 4 };
int mid = arr.length / 2;
System.out.println("midle:: " + mid);
sortArray(arr);
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if(arr[j] == arr[i]){
for(int k = j+1; k < arr.length; k++ ){
int jTemp = arr[j];
if(arr[k] > jTemp){
arr[j] = arr[k];
arr[k] = jTemp;
break;
}
}
}
}
}
System.out.println("Equal Sort after:::: ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
for(int z = 0; z < arr.length; z++){
if(arr[z] >= arr[z+1]){
for(int x = z+1; x<arr.length; x++){
for(int y=x+1; y<arr.length; y++){
if(arr[x] > arr[y]){
int xTemp = arr[x];
arr[x] = arr[y];
arr[y] = xTemp;
}
}
}
break;
}
}
System.out.println("Array Data::After ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
public static void sortArray(int arr[]){
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] != arr[j]) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
System.out.println("Afeter sorting ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
}

Seems like extra space would be required , to optimize the solution without extra space we can convert second array to BST in O(nlogn) and then print values in another O(nlogn) time.
Or simply sort the other array and then print values.