Number Only Underneath

Medium

Cards lie on a table, each with a positive number on both sides: card i shows tops[i] on top and has bottoms[i] underneath. You may flip any cards you like, possibly none. After flipping, call a number *hidden* if it is underneath at least one card and visible on top of none. Return the smallest number that can be made hidden. If nothing can be hidden, return 0.

Example 1

tops=[3, 5, 2, 6], bottoms=[3, 1, 7, 2] → 1

1 is on the underside of the second card and nowhere else, so it is already hidden and not visible on top. Nothing can be smaller than 1.

Example 2

tops=[4, 4, 9], bottoms=[4, 8, 6] → 6

4 is on both sides of the first card, so it is always visible. 6 is under the third card and no card shows 6 on top, so 6 is hidden. Neither 4 nor anything smaller works, so the answer is 6.

Example 3

tops=[2], bottoms=[2] → 0

The only card has 2 on both sides, nothing can be hidden, so the answer is 0.

Constraints

1 ≤ len(tops) = len(bottoms) ≤ 10⁵
1 ≤ tops[i], bottoms[i] ≤ 2000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table

Similar problems

Sudoku Board Without Clashes Medium Anagram Buckets Medium Zero Out the Crosses Medium Tree From Pre-Order and In-Order Walks Medium Tree From In-Order and Post-Order Walks Medium

Input

tops=[3, 5, 2, 6], bottoms=[3, 1, 7, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.