810. Uncrossed Connections
Two rows of numbered pegs hang side by side: the top row holds the values of a from left to right and the bottom row holds the values of b. You may stretch a string between a top peg and a bottom peg only if they carry the same value, and each peg can hold at most one string.
Strings are not allowed to cross each other. Return the largest number of strings that can be stretched at the same time. If no value appears in both rows the answer is 0.
Aim for time O(n*m) and extra space O(m), where n and m are the row lengths.
Example 1
- Input:
- a = [7,2,9,2,5], b = [2,9,7,5,2,2]
- Output:
- 3
- Explanation:
The values 2, 9 and the later 2 can be joined by three lines that never cross.
Example 2
- Input:
- a = [4,8,6,6], b = [6,4,6,8,6]
- Output:
- 3
- Explanation:
Joining 4, 8 and one of the 6 values gives three lines in order, and no fourth line fits.
Constraints
1 ≤ a.length, b.length ≤ 700
1 ≤ a[i], b[j] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(n*m)
- Space
- O(m)