CareerCup

Since both the array are sorted, traverse both the arrays from the end. If the value of the one of the array index is higher decrement that index.

List<int> FindIntersection(int[] A, int[] B)
{
         int L = A.Length;
         int K = B.Length;

         List<int> intersectionArr = new List<int>();
         int i = L - 1;
         int j = K - 1;
         
          while ((i >= 0) && (j >=  0))
          {
                 if (A[i] > B[j])
                 {
                        i--;
                 }
                 else if (B[j] > A[i])
                 {
                         j--;
                 }
                 else
                 {
                         intersectionArr.Add(A[i]);
                          i--;
                          j--;
                        
                 }
          }
          return intersectionArr;
}

Do a modified version of the merge part of mergesort. Advance through the two arrays the same way you would in mergesort (but don't output a merged array), and at each comparison between an element of A and an element of B, additionally check whether the two elements being compared are equal, and if so, print out one of them.

HashMap should be used

The brute force is O(n+m) as at worst you need to traverse both 1st and 2nd array.

Since the arrays are sorted, you can traverse one array forward if you dont find the element or it's less.

I am wondering - which output is expected for the following 2 arrays:
1,1,1
1,1,1,1,1,1,1,1,1

complexity O(n+m);
Results are stored in the linked list with O(1)




#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *head=NULL;
void create(int d)
{
struct node *n1,*n2,*temp;
n1=head;
if(n1==NULL)
{
n2=(struct node *)malloc(sizeof(struct node));
n2->data=d;
n2->link=NULL;
head=n2;
temp=n2;
}
else
{

n2=(struct node *)malloc(sizeof(struct node));
temp->link=n2;
n2->data=d;
n2->link=NULL;
}
printf("%d\n",d);
}
int main()
{
int i,j,n,m;
n=5;
m=4;
int A[10]={1,2,3,4,5,6};
int B[10]={5,6,7,8,9};
for(i=n,j=m;i>0;)
{
if(A[i]<B[j])
{
j--;
}
else
{
if(A[i]==B[j])
{
create(A[i]);
}
i--;
}
}

}

Beat way is insert first Array into HastSet. when you try to insert second array, the common elements will gets failed to insert.

Set<int> commonElements = new HashSet<int> ();
for(int i=0;i<A.length()-1;i++)
{
commonElements.add(A[i]);
}
for(int i=0;i<B.length()-1;i++)
{
if(commonElements.add(B[i])
{ }
else
{
Sys..("common element"+B[i]);
}

This works

#include<iostream>
#include<map>
int main() {

   int arr1[] = {1,2,3,4,5,6,7};
   int arr2[] = {5,6,7,8,9};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2)/sizeof(arr2[0]);

    std::map<int, int> numbers;

    for(int i = 0; i < n1; i++) {
        numbers[arr1[i]] = 1;
    }
    for(int i = 0; i < n2; i++) {
        if(numbers.find(arr2[i]) != numbers.end()) {
            std::cout << arr2[i] << "\n";
        }
    }
    return 0;
}

Starting at the end of the longer array and moving the ptr to match the size of the samller array seems to be the wrong logic. It doesn't say in the problem that the values are consecutive numbers. What if you have
A={2,10,20,25}
B={2,4,6,8,10,12,14,20,25}
You move ptr of B to point at 8. You just missed 20 and 25.


std::set<int> findCommonElements(const std::set<int>& s1, const std::set<int>& s2)
{
std::set<int> results;

if( s1.size() < s2.size())
{
for( const auto& sItr1 : s1 )
{
const auto& sItr2 = s2.find(sItr1);
if( sItr2 != s2.end())
results.insert(sItr1);
}
}
else
{
for( const auto& sItr2 : s2 )
{
const auto& sItr1 = s1.find(sItr2);
if( sItr1 != s1.end())
results.insert(sItr2);
}
}
return results;
}

import java.util.ArrayList;

public class CommonNumbersInSortedArray {
	
	public static ArrayList<Integer> findCommonNumbersinSortedArray(int[] array1, int[]  array2){
		int count1 = 0;
		int count2 = 0;
		ArrayList<Integer> output = new ArrayList<Integer>();
		while(count1<array1.length && count2<array2.length){
			if(array1[count1] == array2[count2]){
				output.add(array1[count1]);
				count1++;
				count2++;
			}
			else if(array1[count1] < array2[count2])
				count1++;
			else
				count2++;
		}
		for(int i=0; i<output.size(); i++)
			System.out.print(output.get(i)+" ");
		return output;
	}

}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace myProgram
{
    class Program
    {
//        There are 2 sorted sets.Find the common elements of those sets 
//e.g. 
//A={1,2,3,4,5,6} 
//B={5,6,7,8,9} 
//o/p C={5,6} 

        public static List<int> commonElements(int[] a,int[]b) 
        {   
            List<int> l= new List<int>();
            HashSet<int> ha = new HashSet<int>(a);
            for (int i = 0; i < b.Length; i++) 
            { 
                if (ha.Contains(b[i])) 
                {
                    if (!l.Contains(b[i]))
                    { 
                        l.Add(b[i]); 
                    }
                } 
            }
            return l;
        }

        static void Main(string[] args)
        {
            int[] a = { 1,2,3,4,5,6};
            int[] b={5,6,7,5,8,9};
            List<int> result = new List<int>();
            result = commonElements(a, b);
            foreach(int i in result)
            {
                Console.WriteLine(i);
            }
            Console.Read();
        }
    }
}

a = Array.new
b = Array.new
a=[1,2,3]
b=[1,2,3,4,5,6]

l1=a.length
l2=b.length
if(l1 > l2)
 len=l1
else
 len=l2
end
 
c = Array.new
p=0
j=0
for i in 0...len
 if a[i] != b[j]
   i=i+1
 else
   if a[i] == b[j]
    c[p]=a[i]
	p=p+1
	j=j+1
  end
 end 
end 
puts "#{c}"

Python version:

def intersect_sorted_array(arr1, arr2):
	index1 = 0
	index2 = 0
	intersection = set()

	while index1 < len(arr1) and index2 < len(arr2):
		if arr1[index1] > arr2[index2]:
			index2 += 1
		elif arr1[index1] < arr2[index2]:
			index1 += 1
		else:
			intersection.add(arr1[index1])
			index1 += 1
			index2 += 1

	return intersection

Implementing Eugene's Algorithm:

public static void intersectionOfArrays(int []p, int[]q){
	  
	  int i=0,j=0;
	  while(i<p.length && j <q.length){
		  
		  if(p[i] == q[j]){
			  System.out.print( p[i] + " ");
			  i++;
			  j++;
		  }
		  else if(p[i]>q[j])
			  j++;
		  else
			  i++;  
			  
	  }
	  
  }

package com.problems;

import java.util.ArrayList;
import java.util.List;

public class FindCommonElements
{

	public static void main(String[] args)
	{
		testFindCommon();
	}
	
	public static void testFindCommon()
	{
		int[] a = {1,2,4,8,9,10,13,14,16};
		int[] b = {5,7,8,12,14,15};
		
		System.out.println(findCommonElements(a, b));
	}
	public static List<Integer> findCommonElements(int[] a, int[] b)
	{
		List<Integer> commonElements = new ArrayList<Integer>();
		int i = 0, j = 0;
		
		int sizeOfA = a.length;
		int sizeOfB = b.length;
		while(i <  sizeOfA && j < sizeOfB)
		{
			if(a[i] < b[j])
			{
				i++;
			}
			else if(a[i] > b[j])
			{
				j++;
			}
			else
			{
				commonElements.add(a[i]);
				i++;
				j++;	
			}
		}
		return commonElements;
	}
}

O(m+n)

static void Main(string[] args)
        {
            int[] array1 = { 1, 2, 3, 4, 5, 5, 6, 7 };
            int[] array2 = { 5, 5, 6, 7, 8, 9 };

            var result = FindCommonSet(array1, array2);

            foreach (var item in result)
            {
                Console.Write("{0} ", item);
            }

            Console.WriteLine();
        }

        static HashSet<int> FindCommonSet(int[] array1, int[] array2)
        {
            int array1Index = 0;
            int array2Index = 0;

            HashSet<int> result = new HashSet<int>();

            while (array1Index < array1.Length && array2Index < array2.Length)
            {
                if (array1[array1Index] > array2[array2Index])
                {
                    array2Index++;
                }
                else if (array1[array1Index] < array2[array2Index])
                {
                    array1Index++;
                }
                else
                {
                    result.Add(array1[array1Index]);

                    array1Index++;
                    array2Index++;
                }
            }

            return result;
        }

public static ArrayList<Integer> intersection(int a[], int b[]) {
    int n1 = a.length;
    int n2 = b.length;
    int i = 0, j = 0;
    ArrayList<Integer> out = new ArrayList<Integer>();
    while(i < n1 && j < n2) {
        if(a[i] == b[j]) {
            out.add(a[i]);
            i++;
            j++;
        } else if(a[i] > b[j]) {
            j++;
        } else {
            i++;
        }
    }
    return out;
}

this is o(m+n)

public class Hello {
    



public static void main(String args[])
{
 
int a[]= {1,2,3,4,5};
int b[]={3,4,5,6,7};

int n=a.length;
int m =b.length;
int x=Math.min(n,m);


int c[]=new int[x];

int i=0,j=0,k=0;

while (i<n && j <m)
{
    if(a[i]>b[j])
        j++;
    else if(a[i]<b[j])
        i++;
    else
    {       c[k]=a[i];
             k++;i++;
        }
    
}
for(k=0;k<x;k++)
    System.out.println(c[k]);
}
}

//
//  CommonOfSets.c

#include <stdio.h>

int main() {
    int a[] = {1,2,3,4,5,6};
    int b[] = {3,5,6,7};
    
    int i, j, m, n;
    m = 6; //length of array-1
    n = 4; //length of array-2
    
    i = 0;
    j = 0;
    while(i < m && j < n) {
        if(a[i] == b[j]) {
            printf("%d\t", a[i]);
            i++;
            j++;
        }
        else {
            if(a[i] < b[j])
                i++;
            else
                j++;
        }
    }
    printf("\n");
    return 0;
}

/*Inspiration came from the merge routine in merge sort; complexity of following is O(n+m)
*/

import java.util.*;
public class General {

public ArrayList<Integer> findCommonElemsForTwoSortedLists(int[] A, int[] B){
int i = 0; int j = 0;
while ((i < A.length) && (A[i] != B[j])){
i++;
}
if (i == A.length)
return null;
else{
ArrayList<Integer> commonElems = new ArrayList<Integer>();
while ((i < A.length) && (j < B.length) && (A[i] == B[j])){
commonElems.add(A[i]);
i++;
j++;
}
return commonElems;
}
}

public static void main (String[] args){
General gen = new General();
int[] A = {1, 2, 3, 4, 5, 6};
int[] B = {5, 6, 7, 8, 9};
ArrayList<Integer> commonElems = gen.findCommonElemsForTwoSortedLists(A, B);
StringBuffer buffer = new StringBuffer();
boolean first = true;
for (Integer elem : commonElems){
if (first){
first = false;
}else{
buffer.append(',');
}
buffer.append(elem);
}
System.out.println(buffer.toString());

}
}

This is very simple in python

def intersect(a,b):
list(set(a) & set(b))

can be done in log(m)*log(n) time with recursion.

public static Set<Integer> intersect(int[] a, int[] b, int a0, int a1, int b0, int b1, Set<Integer> set) {
		int la = a1-a0, lb = b1-b0;
		//base case
		if (la<=2 && lb<=2) {
			for (int i=a0; i<a1; i++) for (int j=b0; j<b1; j++) if (a[i]==b[j]) set.add(a[i]);
			return set;
		}
		else if (la<=lb) {
			set.addAll(intersect(a, b, a0, a1, b0, (b0+b1)/2, set));
			set.addAll(intersect(a, b, a0, a1, (b0+b1)/2, b1, set));
		}
		else {
			set.addAll(intersect(a, b, a0, (a0+a1)/2, b0, b1, set));
			set.addAll(intersect(a, b, (a0+a1)/2, a1, b0, b1, set));
		}
		return set;
	}
	
	public static void main(String[] args) {
		int[] a = new int[100];
		int[] b = new int[50];
		for (int i=0; i<a.length; i++) a[i] = 4*i-30;
		for (int i=0; i<b.length; i++) b[i] = 3*i-7;
		for (int d:a) System.out.printf("%d, ", d);

		System.out.println();
		for (int d:b) System.out.printf("%d, ", d);
		System.out.println();
		
		Set<Integer> intersect = new TreeSet<Integer>();
		intersect = intersect(a, b, 0, 100, 0, 50, intersect);
		for (int d:intersect) System.out.printf("%d, ", d);
		
	}

import java.util.TreeMap;


public class CommonIntegers {
	
	static void commonInt(int[] first,int[] second){
		TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
		TreeMap<Integer,Integer> answer = new TreeMap<Integer,Integer>();
		for(int i:first){
			if(map.get(i)==null){
				map.put(i, 1);
			}
			else{
				map.put(i, map.get(i)+1);
			}
		}
		for(int i:second){
			if(map.get(i)!=null){
				answer.put(i, map.get(i)+1);
			}
		}
		
		System.out.println(answer.keySet());
		
	}
	
	public static void main(String[] args){
		int[] A={1,2,3,4,5,6,9} ;
		int[] B={5,6,7,8,9} ;
		commonInt(A, B);
	}

}