Show problems as
Classic problem #2657MediumArrayHash TableBit Manipulation

Find the Prefix Common Array of Two Arrays

Real-world version: Crates Handled by Both Crews
Tracked in this browser only
Read Find the Prefix Common Array of Two Arrays on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two crews unload the same n crates, tagged 1 through n. Each crew works through all the crates in its own order: crewA[i] is the crate the first crew handles in minute i, and crewB[i] is the crate the second crew handles in that same minute. Both lists are permutations of 1 through n.

At the end of every minute the yard manager writes down how many crates have by then been handled by both crews, counting everything either crew touched from minute 0 up to and including the current minute.

Return the manager's log as a list of n numbers, where entry i is the figure recorded at the end of minute i.

Examples

Example 1

Input
crewA = [4, 1, 2, 3], crewB = [1, 4, 3, 2]
Output
[0, 2, 2, 4]

After minute 0 the crews have handled crates {4} and {1}, with nothing in common. After minute 1 they hold {4, 1} and {1, 4}, so both crates count. Minute 2 adds crate 2 for the first crew and crate 3 for the second, neither of which the other crew has yet. Minute 3 finishes every crate.

Example 2

Input
crewA = [2, 1, 5, 3, 4], crewB = [2, 5, 1, 4, 3]
Output
[1, 1, 3, 3, 5]

Both crews start on crate 2, so the first figure is 1. Minute 1 adds crate 1 and crate 5, still leaving only crate 2 shared. Minute 2 gives the first crew crate 5 and the second crew crate 1, so crates 1, 2 and 5 are now shared.

Example 3

Input
crewA = [3, 2, 1, 4], crewB = [4, 1, 2, 3]
Output
[0, 0, 2, 4]

Nothing overlaps for the first two minutes. After minute 2 the crews hold {3, 2, 1} and {4, 1, 2}, sharing crates 1 and 2.

Example 4

Input
crewA = [1], crewB = [1]
Output
[1]

With one crate, both crews handle it in minute 0.

Constraints

  • 1 <= crewA.length == crewB.length == n <= 50
  • 1 <= crewA[i], crewB[i] <= n
  • crewA and crewB are both permutations of the integers 1 through n.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shared_progress(crewA: list[int], crewB: list[int]) -> list[int]:
Java
public int[] sharedProgress(int[] crewA, int[] crewB)

More on the same topics