Find the Difference of Two Arrays - Practice Coding Problems

Find the Difference of Two Arrays - Problem

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Input & Output

Example 1 — Basic Case

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

› Output: [[1,3],[4,6]]

💡 Note: Elements 1 and 3 are in nums1 but not nums2. Elements 4 and 6 are in nums2 but not nums1.

Example 2 — With Duplicates

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

› Output: [[3],[]]

💡 Note: Element 3 is in nums1 but not nums2. All elements of nums2 exist in nums1, so second array is empty.

Example 3 — No Common Elements

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

› Output: [[1,2],[3,4]]

💡 Note: No elements are common between arrays, so each array contains all its unique elements.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums1 = [1,2,3] and nums2 = [2,4,6]

Find Differences

Elements in nums1 not in nums2: [1,3]. Elements in nums2 not in nums1: [4,6]

Output

Return [[1,3], [4,6]] as the answer

Key Takeaway

🎯 Key Insight: Use hash sets to convert O(n×m) linear searches into O(1) lookups

Asked in

A Amazon 15 G Google 12

The key insight is using hash sets for O(1) membership checking instead of linear search. Best approach is Two-Pass Hash Set: convert arrays to sets, then check each element's membership in the other set. Time: O(n+m), Space: O(n+m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Nested Loops	O(n×m)	O(k)	Check each element against every element in the other array
Two-Pass Hash Set	O(n+m)	O(n+m)	Convert arrays to hash sets for O(1) lookups

Brute Force - Nested Loops — Algorithm Steps

Create sets to store unique differences for both arrays
For each element in nums1, check if it exists in nums2 using linear search
For each element in nums2, check if it exists in nums1 using linear search
Convert sets to lists and return as answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare nums1[0]=1

Check 1 against all elements in nums2 [2,3] - not found, add to diff1

Compare nums1[1]=2

Check 2 against all elements in nums2 [2,3] - found, skip

Compare nums2 elements

Repeat process for nums2 against nums1

Result

Return [[1], [3]] - unique elements in each array

Code -

solution.c — C

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

typedef struct {
    int* data;
    int size;
    int capacity;
} IntList;

IntList* createList() {
    IntList* list = malloc(sizeof(IntList));
    list->capacity = 10;
    list->data = malloc(list->capacity * sizeof(int));
    list->size = 0;
    return list;
}

void addToList(IntList* list, int value) {
    // Check if value already exists
    for (int i = 0; i < list->size; i++) {
        if (list->data[i] == value) return;
    }
    
    if (list->size >= list->capacity) {
        list->capacity *= 2;
        list->data = realloc(list->data, list->capacity * sizeof(int));
    }
    list->data[list->size++] = value;
}

int* parseArray(char* str, int* size) {
    int* arr = malloc(1000 * sizeof(int));
    *size = 0;
    
    char* token = strtok(str, "[],");
    while (token != NULL) {
        arr[(*size)++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    return arr;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int size1, size2;
    int* nums1 = parseArray(line1, &size1);
    int* nums2 = parseArray(line2, &size2);
    
    IntList* diff1 = createList();
    IntList* diff2 = createList();
    
    // Find elements in nums1 but not in nums2
    for (int i = 0; i < size1; i++) {
        int found = 0;
        for (int j = 0; j < size2; j++) {
            if (nums1[i] == nums2[j]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            addToList(diff1, nums1[i]);
        }
    }
    
    // Find elements in nums2 but not in nums1
    for (int i = 0; i < size2; i++) {
        int found = 0;
        for (int j = 0; j < size1; j++) {
            if (nums2[i] == nums1[j]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            addToList(diff2, nums2[i]);
        }
    }
    
    printf("[[");
    for (int i = 0; i < diff1->size; i++) {
        if (i > 0) printf(",");
        printf("%d", diff1->data[i]);
    }
    printf("],[");
    for (int i = 0; i < diff2->size; i++) {
        if (i > 0) printf(",");
        printf("%d", diff2->data[i]);
    }
    printf("]]\n");
    
    free(nums1);
    free(nums2);
    free(diff1->data);
    free(diff1);
    free(diff2->data);
    free(diff2);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each of n elements in nums1, we search through m elements in nums2, and vice versa

✓ Linear Growth

Space Complexity

O(k)

Only space for result sets containing at most n+m unique elements

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

950 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

Brute Force - Nested Loops — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler