FunctionRacerProblemsRace

Shared Items of Two Sorted Lists

EasyTwo pointersPython, JavaScript, TypeScript, Java, C++

a and b are both sorted in non-decreasing order and may contain repeats. Return the items that appear in both lists, as a list in non-decreasing order. A value that appears x times in a and y times in b appears min(x, y) times in the answer.

Walk the two lists together with one index each: when the two current items are equal, record one and advance both; otherwise advance the list whose current item is smaller. Either list may be empty, and the answer is empty when nothing is shared.

Example 1

a [1,2,2,3,5]
b [2,2,3,3,6]
returns [2,2,3]

2 appears twice in both, 3 appears once in a and twice in b, so once; 1, 5 and 6 are not shared.

Example 2

a [1,2,3]
b [4,5]
returns []

The two lists have no value in common.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Two pointers problems