Find Common Elements Between Two Arrays - Practice Coding Problems

Find Common Elements Between Two Arrays - Problem

You are given two integer arrays nums1 and nums2 of sizes n and m, respectively.

Calculate the following values:

answer1: the number of indices i such that nums1[i] exists in nums2
answer2: the number of indices i such that nums2[i] exists in nums1

Return [answer1, answer2].

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [4,3,2,3,1], nums2 = [2,3,1,4,7]

› Output: [4,4]

💡 Note: For nums1: all elements 4,3,2,3,1 exist in nums2, so answer1=4. For nums2: elements 2,3,1,4 exist in nums1 (7 doesn't), so answer2=4.

Example 2 — Partial Matches

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

› Output: [0,0]

💡 Note: No elements from nums1 exist in nums2, and no elements from nums2 exist in nums1, so both counts are 0.

Example 3 — All Different Sizes

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

› Output: [2,2]

💡 Note: From nums1: elements 2,4 exist in nums2 (answer1=2). From nums2: elements 2,4 exist in nums1 (answer2=2).

Constraints

1 ≤ nums1.length, nums2.length ≤ 1000
1 ≤ nums1[i], nums2[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two integer arrays nums1 and nums2 with potentially overlapping elements

Count Common Elements

Count how many elements from nums1 exist in nums2, and vice versa

Return Counts

Return [answer1, answer2] representing both counts

Key Takeaway

🎯 Key Insight: Use hash sets to transform slow O(n) searches into fast O(1) lookups for efficient element comparison

Asked in

a Amazon 35 G Google 28

The key insight is using hash sets to convert O(n) linear searches into O(1) constant-time lookups. Best approach is the Hash Set method which creates sets from both arrays and counts elements efficiently. Time: O(n+m), Space: O(n+m).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(n+m)	O(n+m)	Convert one array to a hash set for O(1) lookup, then check each element of the other array
Brute Force - Nested Loops	O(n×m)	O(1)	For each element in one array, scan the entire other array to check if it exists

Hash Set Optimization — Algorithm Steps

Convert nums2 to a hash set for fast lookups
Count elements in nums1 that exist in nums2 set
Count elements in nums2 that exist in nums1 (convert to set if needed)
Return both counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Hash Sets

Convert both arrays to hash sets

Fast Lookups

Check each element against the other set in O(1) time

Count Matches

Sum up all the matches found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_VAL 10000

int* solution(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int* result = (int*)malloc(2 * sizeof(int));
    bool set1[MAX_VAL * 2] = {false}; // Handle negative numbers
    bool set2[MAX_VAL * 2] = {false};
    
    // Create sets (offset by MAX_VAL for negative numbers)
    for (int i = 0; i < nums1Size; i++) {
        set1[nums1[i] + MAX_VAL] = true;
    }
    for (int i = 0; i < nums2Size; i++) {
        set2[nums2[i] + MAX_VAL] = true;
    }
    
    int answer1 = 0;
    int answer2 = 0;
    
    // Count elements in nums1 that exist in nums2
    for (int i = 0; i < nums1Size; i++) {
        if (set2[nums1[i] + MAX_VAL]) {
            answer1++;
        }
    }
    
    // Count elements in nums2 that exist in nums1
    for (int i = 0; i < nums2Size; i++) {
        if (set1[nums2[i] + MAX_VAL]) {
            answer2++;
        }
    }
    
    result[0] = answer1;
    result[1] = answer2;
    return result;
}

int main() {
    char line[1000];
    int nums1[100], nums2[100];
    int nums1Size = 0, nums2Size = 0;
    
    // Parse first array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            nums1[nums1Size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse second array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            nums2[nums2Size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int* result = solution(nums1, nums1Size, nums2, nums2Size);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n+m)

Creating sets takes O(n+m) time, then we iterate once through each array

✓ Linear Growth

Space Complexity

O(n+m)

Hash sets store all unique elements from both arrays

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler