DSA SheetEasy
EditorialPractice

HASHING › IMPLEMENTARY PROBLEMS

Find Common Elements Between Two Arrays

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 12

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionmembership is checked per index, so duplicates must count

The first answer asks you to inspect every index of nums1 and ask one question: does this value appear at least once in nums2? The second answer asks the same question in the opposite direction. The value can appear many times in the array being counted, and every such index contributes separately.

A set stores whether a value appears, without storing how many times it appears. That is exactly the information each membership question needs. Build one set for each array, then scan nums1 against nums2's set and nums2 against nums1's set. The sets answer presence; the scans preserve duplicate occurrences.

Approach

  1. Build set1 from every value in nums1, because the second answer needs to test membership in nums1 without rescanning it for every element.
  2. Build set2 from every value in nums2, because the first answer needs the symmetric fast membership test and one set alone would not answer both directions cleanly.
  3. Initialize answer1 and answer2 to zero, because each counter represents indices from a different source array and they must not share accumulated work.
  4. Scan nums1 and increment answer1 when set2 contains the current value, because the definition counts this index even when the same value occurred earlier in nums1.
  5. Scan nums2 and increment answer2 when set1 contains the current value, because duplicates in nums2 are separate indices and each matching occurrence must be counted.
  6. Return the two counters in the order [answer1, answer2], because swapping them changes which input array each count describes.

Complexityexpected cost with hash-set membership

MEASUREBOUNDWHY
TimeExpected O(n + m), worst-case O(nm)Building the two sets processes n + m inserted values, and the two scans perform n + m membership checks. With expected constant-time hashing, no array is rescanned for an individual element. If every lookup is forced into long collision chains, a lookup can cost linear time, making the worst case O(nm).
SpaceExpected O(n + m) extra, worst-case O(n + m)The two sets keep at most n and m distinct values combined; the returned two-element vector is required output and is excluded. The extra space is largest when the arrays contain as many distinct values as possible, although the value range here caps each set at 100 entries.
Here n is nums1.length and m is nums2.length. Hash-set operations are expected O(1); the worst-case hashing bound is included explicitly.

Annotated solutionC++ · two sets and two directional scans

CPPStore presence in both arrays, then count matching occurrences in each original array.
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());

        int answer1 = 0;
        int answer2 = 0;

        for (int x : nums1) {
            if (set2.count(x)) {
                answer1++;
            }
        }

        for (int x : nums2) {
            if (set1.count(x)) {
                answer2++;
            }
        }

        return {answer1, answer2};
    }
};

The important distinction is between constructing a set and performing the count. The set removes duplicate information because it only answers whether a value exists. The range-based loops deliberately read the original arrays, not the sets, so a value repeated three times contributes three times when it is present in the other array.

The bounded-value alternativea fixed presence table avoids hashing, but depends on the value range

Because every value is between 1 and 100, you can replace each hash set with a boolean presence table indexed by the value. This is a different arrangement, not a better asymptotic time bound: it keeps the same O(n + m) scans, uses O(1) extra space under this fixed constraint, and avoids hash overhead. If the allowed value range grows to U, the tables require O(U) space and should be sized or replaced accordingly.

CPPUse the stated value range as two direct-address presence tables.
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
        vector<bool> presentInFirst(101, false);
        vector<bool> presentInSecond(101, false);

        for (int x : nums1) {
            presentInFirst[x] = true;
        }
        for (int x : nums2) {
            presentInSecond[x] = true;
        }

        int answer1 = 0;
        int answer2 = 0;

        for (int x : nums1) {
            if (presentInSecond[x]) {
                answer1++;
            }
        }
        for (int x : nums2) {
            if (presentInFirst[x]) {
                answer2++;
            }
        }

        return {answer1, answer2};
    }
};

Common mistakesthe two lines of reasoning that most often get mixed up