1062EasyArrayHash Table

What Each List Holds Alone

Tracked in this browser only

Trains the technique from

LeetCode 2215Find the Difference of Two Arrays

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two lists of whole numbers are given, left and right. Either list may hold repeats.

Return a list of two lists. The first holds every value that appears in left but nowhere in right, and the second holds every value that appears in right but nowhere in left. Each value appears once in its list, however often it appeared in the input, and both lists come out in increasing order.

Examples

Example 1

Input: left = [4, 5, 6], right = [5, 7]
Output: [[4, 6], [7]]

The 5 sits in both lists, so it appears in neither answer. That leaves 4 and 6 held only on the left, and 7 only on the right.

Example 2

Input: left = [1, 1, 1], right = [1]
Output: [[], []]

The only value either list holds is 1, and both hold it, so both answers come out empty however many times it was repeated.

Example 3

Input: left = [9], right = [8]
Output: [[9], [8]]

The lists share nothing, so each reports its own single value.

Constraints

1 <= left.length <= 1000
1 <= right.length <= 1000
-1000 <= left[i] <= 1000
-1000 <= right[i] <= 1000

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_difference(left: list[int], right: list[int]) -> list[list[int]]:

Java

public List<List<Integer>> findDifference(int[] left, int[] right)

The intended approach

Time O(a + b + k log k) for lists of length a and b and k distinct values reported.Space O(a + b) for the two sets.

Repeats never matter to the question, so reduce each list to the set of values it holds. That takes one pass apiece and makes membership a constant-time question. Then each answer is one set with the other taken away. Sorting the two results puts them in the order asked for. Reducing to sets first is what avoids comparing every value of one list against every value of the other.

Pythonentry point: find_difference

def find_difference(left, right):
    here = set(left)
    there = set(right)
    only_left = []
    for value in here:
        if value not in there:
            only_left.append(value)
    only_right = []
    for value in there:
        if value not in here:
            only_right.append(value)
    only_left.sort()
    only_right.sort()
    return [only_left, only_right]

The obvious version

Walk each list and, for every value, scan the other list from end to end looking for it, keeping the value when the scan finds nothing and it has not already been kept. Sort the two results at the end. Costs the two lengths multiplied together rather than a pair of sets.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_difference(left, right):
    only_left = []
    for value in left:
        found = False
        for other in right:
            if other == value:
                found = True
                break
        if not found:
            already = False
            for kept in only_left:
                if kept == value:
                    already = True
                    break
            if not already:
                only_left.append(value)
    only_right = []
    for value in right:
        found = False
        for other in left:
            if other == value:
                found = True
                break
        if not found:
            already = False
            for kept in only_right:
                if kept == value:
                    already = True
                    break
            if not already:
                only_right.append(value)
    only_left.sort()
    only_right.sort()
    return [only_left, only_right]

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in