Scale Engineer

Find the Difference of Two Arrays

Easy
#2018Time: O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. For each of the `n` elements in `nums1`, we iterate through all `m` elements of `nums2`. The same happens for `nums2` against `nums1`.Space: O(n + m) in the worst case, to store the result sets. If all elements in `nums1` are unique and not in `nums2`, and vice-versa, the sets will store `n` and `m` elements respectively.1 company
Data structures
ArrayHash Table
Companies
Yandex

Prompt

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.

 

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums1. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. We iterate through each element of the first array and, for each element, we scan the entire second array to see if a match exists. We repeat the process for the second array against the first. To handle the requirement for distinct elements in the output, we use sets to store our results before converting them to lists.

Algorithm

  • Initialize two empty sets, resultSet1 and resultSet2, to store the unique differences.
  • For each element num1 in nums1:
    • Set a boolean flag is_present to false.
    • Iterate through each element num2 in nums2.
    • If num1 equals num2, set is_present to true and break the inner loop.
    • If the inner loop completes and is_present is false, add num1 to resultSet1.
  • Repeat the process, swapping the roles of nums1 and nums2 to populate resultSet2.
  • Convert resultSet1 and resultSet2 to lists.
  • Return a list containing the two result lists.

Walkthrough

We need to find two lists: diff1 (elements in nums1 but not nums2) and diff2 (elements in nums2 but not nums1).

To find diff1, we iterate through each number num1 in nums1. For each num1, we perform a linear search through nums2. If after checking all elements of nums2, we don't find num1, we add it to a result set to ensure uniqueness.

Similarly, to find diff2, we iterate through each number num2 in nums2 and search for it in nums1. If not found, it's added to another result set.

Using sets (HashSet in Java) for the results is crucial to automatically handle duplicates from the input arrays (e.g., [1,2,3,3]) and ensure the final output lists contain only distinct integers.

Finally, the two sets are converted into lists and returned.

import java.util.*; class Solution {    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {        Set<Integer> diff1 = new HashSet<>();        Set<Integer> diff2 = new HashSet<>();         // Find elements in nums1 but not in nums2        for (int num1 : nums1) {            boolean found = false;            for (int num2 : nums2) {                if (num1 == num2) {                    found = true;                    break;                }            }            if (!found) {                diff1.add(num1);            }        }         // Find elements in nums2 but not in nums1        for (int num2 : nums2) {            boolean found = false;            for (int num1 : nums1) {                if (num2 == num1) {                    found = true;                    break;                }            }            if (!found) {                diff2.add(num2);            }        }         List<List<Integer>> answer = new ArrayList<>();        answer.add(new ArrayList<>(diff1));        answer.add(new ArrayList<>(diff2));        return answer;    }}

Complexity

Time

O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. For each of the `n` elements in `nums1`, we iterate through all `m` elements of `nums2`. The same happens for `nums2` against `nums1`.

Space

O(n + m) in the worst case, to store the result sets. If all elements in `nums1` are unique and not in `nums2`, and vice-versa, the sets will store `n` and `m` elements respectively.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Highly inefficient for large arrays, likely resulting in a 'Time Limit Exceeded' error on most coding platforms.

Solutions

class Solution {public  List<List<Integer>> findDifference(int[] nums1, int[] nums2) {    Set<Integer> s1 = convert(nums1);    Set<Integer> s2 = convert(nums2);    List<List<Integer>> ans = new ArrayList<>();    List<Integer> l1 = new ArrayList<>();    List<Integer> l2 = new ArrayList<>();    for (int v : s1) {      if (!s2.contains(v)) {        l1.add(v);      }    }    for (int v : s2) {      if (!s1.contains(v)) {        l2.add(v);      }    }    ans.add(l1);    ans.add(l2);    return ans;  }private  Set<Integer> convert(int[] nums) {    Set<Integer> s = new HashSet<>();    for (int v : nums) {      s.add(v);    }    return s;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem