Given two arrays find the common elements

Table of Contents Show

C Program to Find Common Elements in Two Arrays
First Method (Naive Approach) – Find Common Elements in Two Arrays using Two For Loops
Second Method -Find Common Elements in Two Arrays of Different Length/Size

Continuing the algorithm practice saga, I bumped into an exercise that illustrates the “brute force/ideal/best” scenarios when solving algorithm exercises. As we know, there are not only multiple ways to reach an answer, but just because our answers work it doesn’t mean they’re optimal.

The problem

Last update on August 19 2022 21:50:53 (UTC/GMT +8 hours)

Write a Java program to find the common elements between two arrays of integers.

Pictorial Presentation:

Sample Solution:

Java Code:

import java.util.Arrays; public class Exercise15 { public static void main(String[] args) { int[] array1 = {1, 2, 5, 5, 8, 9, 7, 10}; int[] array2 = {1, 0, 6, 15, 6, 4, 7, 0}; System.out.println("Array1 : "+Arrays.toString(array1)); System.out.println("Array2 : "+Arrays.toString(array2)); for (int i = 0; i < array1.length; i++) { for (int j = 0; j < array2.length; j++) { if(array1[i] == (array2[j])) { System.out.println("Common element is : "+(array1[i])); } } } } }

Sample Output:

Array1 : [1, 2, 5, 5, 8, 9, 7, 10] Array2 : [1, 0, 6, 15, 6, 4, 7, 0] Common element is : 1 Common element is : 7

Flowchart:

Visualize Java code execution (Python Tutor):

Java Code Editor:

Improve this sample solution and post your code through Disqus

Previous: Write a Java program to find the common elements between two arrays (string values).
Next: Write a Java program to remove duplicate elements from an array.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

tmpDirName

Returns the value of java.io.tmpdir system property. It appends separator if not present at the end.

public static String tmpDirName() { String tmpDirName = System.getProperty("java.io.tmpdir"); if (!tmpDirName.endsWith(File.separator)) { tmpDirName += File.separator; } return tmpDirName; }

Ref: https://bit.ly/3z3jPMl

Sort the arrays. Then iterate through them with two pointers, always advancing the one pointing to the smaller value. When they point to equal values, you have a common value. This will be O(n log n+m log m) where n and m are the sizes of the two lists. It's just like a merge in merge sort, but where you only produce output when the values being pointed to are equal.

def common_elements(a, b): a.sort() b.sort() i, j = 0, 0 common = [] while i < len(a) and j < len(b): if a[i] == b[j]: common.append(a[i]) i += 1 j += 1 elif a[i] < b[j]: i += 1 else: j += 1 return common print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

outputs

Common values: 1, 4

If the elements aren't comparable, throw the elements from one list into a hashmap and check the elements in the second list against the hashmap.

Write a c program to find common elements in two arrays.

Given two positive integer arrays arr1 and arr2 of lengths len1 and len2. We have to write a c code to find intersection of these two arrays. Both the arrays are sorted.

Let’s assume we have following two sorted arrays arr1 and arr2.

int arr1[] = {2, 3, 4, 5, 6};
int arr2[] = {4, 6, 7, 8, 9};

So the common elements in these two arrays is 4 and 6.

C Program to Find Common Elements in Two Arrays

First Method (Naive Approach) – Find Common Elements in Two Arrays using Two For Loops

In this approach, we take each element of a first array and compare with every element of a second array. If it is found in second array then it’s a common element else we move to next element.

The time complexity of this approach is O(mn), Where m and n are the number of elements in array1 and array2.

C Program to Find Missing Number in Array

Java Program to Find Intersection of Two Arrays

Find Common Elements in Three Sorted Arrays

Programming video tutorials

/** * Find Common Elements in Two Sorted Arrays */ #include <stdio.h> int printCommon(int arr1[], int len1, int arr2[],int len2) { int i,j; for(i = 0; i < len1 ;i++) { for(j = 0; j < len2 ;j++) { if(arr1[i] == arr2[j]){ printf("\n Common elements is %d", arr1[i]); } } } } int main(void) { /* * For demostration purpose, i take these values in a code * / int arr1[] = {2,3,4,5,6}; int arr2[] = {4,6,7,8,9}; // Lenght of arr1 and arr2 int len1 = 5; int len2 = 5; printCommon(arr1,len1,arr2,len2); return 0; }

/**

* Find Common Elements in Two Sorted Arrays

#include <stdio.h>

int printCommon(int arr1[], int len1, int arr2[],int len2) {

int i,j;

for(i = 0; i < len1 ;i++) {

for(j = 0; j < len2 ;j++) {

if(arr1[i] == arr2[j]){

printf("\n Common elements is %d", arr1[i]);

}

int main(void) {

* For demostration purpose, i take these values in a code

* /

int arr1[] = {2,3,4,5,6};

int arr2[] = {4,6,7,8,9};

// Lenght of arr1 and arr2

int len1 = 5;

int len2 = 5;

printCommon(arr1,len1,arr2,len2);

return 0;

}

Second Method -Find Common Elements in Two Arrays of Different Length/Size

Implementation Logic:

i) Use two index variables i and j, Initialized them with 0. ii) If arr1[i] is smaller than arr2[j] then increment i. iii) If arr1[i] is greater than arr2[j] then increment j.

iv) If both are same then print any of the array value and increment both i and j.

Program to implement a stack using an array

The time complexity of this approach is O(m+n).

#include <stdio.h> /* Prints intersection of two arrays arr1[] and arr2[] len1 is the number of elements in arr1[] len2 is the number of elements in arr2[] */ int printCommon(int arr1[], int len1, int arr2[], int len2) { int i=0,j=0; while(len1 > i && len2 > j){ if (arr1[i] < arr2[j]) { i++; }else if(arr2[j] < arr1[i]){ j++; } else { printf("\nCommon element is %d",arr1[i]); i++; j++; } } } int main(void) { int arr1[] = {2,3,4,5,6}; int arr2[] = {4,6,7,8,9}; /* Length of first and second array. */ int len1 = 5; int len2 = 5; printCommon(arr1, len1, arr2, len2); return 0; }