Find Common Elements Between Two Arrays

Easy
1809.

Find Common Elements Between Two Arrays

Find Common Elements Between Two Arrays is an easy coding problem on arrays and hash table, asked in Amazon interviews.

You are given two integer arrays nums1 and nums2.

Return an array [answer1, answer2] where:

  • answer1 is the number of indices i such that nums1[i] occurs somewhere in nums2;
  • answer2 is the number of indices i such that nums2[i] occurs somewhere in nums1.

Repeated values are counted once per index.

Example 1

Input
nums1 = [2,3,2], nums2 = [1,2]
Output
[2,1]
Explanation
Both 2s of `nums1` occur in `nums2`; in `nums2` only the 2 occurs in `nums1`.

Example 2

Input
nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
Output
[3,4]

Example 3

Input
nums1 = [3,4,2,3], nums2 = [1,5]
Output
[0,0]

Constraints

  • 1 <= nums1.length, nums2.length <= 100
  • 1 <= nums1[i], nums2[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var findIntersectionValues = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Common Elements Between Two Arrays — Problem & Solution

Find Common Elements Between Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Common Elements Between Two Arrays is an easy coding problem on arrays and hash table, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given two integer arrays nums1 and nums2.

Return an array [answer1, answer2] where:

  • answer1 is the number of indices i such that nums1[i] occurs somewhere in nums2;
  • answer2 is the number of indices i such that nums2[i] occurs somewhere in nums1.

Repeated values are counted once per index.

Example 1

Input: nums1 = [2,3,2], nums2 = [1,2]
Output: [2,1]
Explanation: Both 2s of `nums1` occur in `nums2`; in `nums2` only the 2 occurs in `nums1`.

Example 2

Input: nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
Output: [3,4]

Example 3

Input: nums1 = [3,4,2,3], nums2 = [1,5]
Output: [0,0]

Constraints

  • 1 <= nums1.length, nums2.length <= 100
  • 1 <= nums1[i], nums2[i] <= 100

Hints for Find Common Elements Between Two Arrays

  1. Hint 1

    For each element you only need a yes/no answer: does its value appear in the other array?

  2. Hint 2

    Build a membership table (a set, or a boolean array since values are at most 100) for each array.

  3. Hint 3

    Then count the indices of each array whose value is marked in the other array's table.

How to solve Find Common Elements Between Two Arrays

Membership is all that matters, so precompute which values each array contains and count the indices whose value the other array contains.

Approach

  1. Mark in1[v] = true for every v in nums1, and in2[v] = true for every v in nums2.
  2. answer1 = number of i with in2[nums1[i]]; answer2 = number of i with in1[nums2[i]].
  3. Return [answer1, answer2].

Why it works

Each index is checked once against the exact set of values of the other array, so it is counted precisely when its value occurs there; duplicates are separate indices and are counted separately, as required.

Complexity

  • Time — O(n + m)
  • Space — O(V) with V = 100

Pitfalls

  • Counting distinct common values instead of indices undercounts repeated values.
  • The two answers are not symmetric — compute each against the other array.

Reference solution

Python

from typing import List

def findIntersectionValues(nums1: List[int], nums2: List[int]) -> List[int]:
    s1, s2 = set(nums1), set(nums2)
    return [sum(1 for x in nums1 if x in s2), sum(1 for x in nums2 if x in s1)]

Java

public static int[] findIntersectionValues(int[] nums1, int[] nums2) {
    boolean[] in1 = new boolean[101], in2 = new boolean[101];
    for (int v : nums1) in1[v] = true;
    for (int v : nums2) in2[v] = true;
    int a = 0, b = 0;
    for (int v : nums1) if (in2[v]) a++;
    for (int v : nums2) if (in1[v]) b++;
    return new int[]{a, b};
}

C++

vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
    bool in1[101] = {false}, in2[101] = {false};
    for (int v : nums1) in1[v] = true;
    for (int v : nums2) in2[v] = true;
    int a = 0, b = 0;
    for (int v : nums1) if (in2[v]) a++;
    for (int v : nums2) if (in1[v]) b++;
    return {a, b};
}

JavaScript

var findIntersectionValues = function(nums1, nums2) {
    var in1 = new Uint8Array(101), in2 = new Uint8Array(101);
    for (var i = 0; i < nums1.length; i++) in1[nums1[i]] = 1;
    for (var j = 0; j < nums2.length; j++) in2[nums2[j]] = 1;
    var a = 0, b = 0;
    for (var p = 0; p < nums1.length; p++) if (in2[nums1[p]]) a++;
    for (var q = 0; q < nums2.length; q++) if (in1[nums2[q]]) b++;
    return [a, b];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets