0730EasyArrayHash Table

Tokens Shared By Two Crates

Tracked in this browser only

Trains the technique from

LeetCode 2956Find Common Elements Between 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 crates of tokens have been logged. left lists the colour code of each token in the first crate and right does the same for the second crate.

Return a two-entry array [a, b], where

a is the number of positions i in left whose code appears somewhere in right, and
b is the number of positions j in right whose code appears somewhere in left.

How often a code is repeated in the other crate does not matter, only whether it is there at all. Positions are counted one by one, so a crate that holds the same code three times can contribute three to its tally.

Examples

Example 1

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

Code 1 sits at two positions of the first crate and appears in the second, so the first tally is 2. Code 2 does not appear in the second crate. Looking the other way, only the single 1 in the second crate has a match, so the second tally is 1.

Example 2

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

Both crates hold codes 5 and 6, so every position of both crates counts: three in the first crate and four in the second.

Example 3

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

The crates have no code in common, so both tallies are 0.

Constraints

1 <= left.length <= 100
1 <= right.length <= 100
1 <= left[i] <= 100
1 <= right[i] <= 100

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 shared_tallies(left: list[int], right: list[int]) -> list[int]:

Java

public int[] sharedTallies(int[] left, int[] right)

The intended approach

Time O(n + m) for crates of n and m tokens.Space O(n + m) for the two code sets.

Whether a code appears in the other crate is a membership question, so build the set of codes for each crate. Then walk the first crate counting the positions whose code is in the second crate's set, and walk the second crate counting the positions whose code is in the first crate's set. Counting positions rather than set entries is what keeps a repeated code contributing more than once.

Pythonentry point: shared_tallies

def shared_tallies(left, right):
    # Collect the distinct codes of each crate once, then walk each crate and count
    # the positions whose code turns up in the other crate's set of codes.
    # Time O(n + m).  Space O(n + m) for the two code sets.
    left_codes = set(left)
    right_codes = set(right)
    first = 0
    for code in left:
        if code in right_codes:
            first += 1
    second = 0
    for code in right:
        if code in left_codes:
            second += 1
    return [first, second]

The obvious version

For each token of one crate, scan the other crate from the start and stop at the first token with an equal code, counting that position as shared. Done once in each direction.

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_shared_tallies(left, right):
    first = 0
    for a in left:
        for b in right:
            if a == b:
                first += 1
                break
    second = 0
    for b in right:
        for a in left:
            if a == b:
                second += 1
                break
    return [first, second]

How this problem was checked

Reference solution executed against 11 test cases — 11 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