Find a pair of entries from two lists that yield a sum that is as close to a target number as possible, without exceeding it.

Each entry in a list is a key-value pair, where the key is a number identifier and the value is also a number. The output must be a list containing the pairs of numbers representing the identifiers that yield the result.

If a solution is not possible, return an empty list.

Notice the input could be not sorted.

Input:

a = [12, 14, 16], b = [2], target = 17,

Output: [[1, 0]]

Explanation:

There are only three possible pairs, [0, 0], [1, 0], and [2, 0]. They yield the sum values of 12 + 2 = 14, 14 + 2 = 16 and 16 + 2 = 18 respectively.

16 is the largest number that does not exceed 17, therefore [1, 0] is the optimal pair.

Example 2:

Input:

a = [3, 5, 7, 10], b = [2, 3, 4, 5], target = 10,

Output: [[1, 3], [2, 1]]

Explanation:

There are two pairs possible. The element with id = 1 from list a has a value of 5, and the element with id = 3 from list b also has a value of 5. Combined, they add up to 10.

Likewise, the element with id = 2 from a has a value of 7, and the element with id = 1 from b has a value of 3. These also add up to 10.

Therefore, the optimal pairs are [1, 3] and [2, 1].

Example 3:

Input:

a = [8, 7, 14], b = [5, 10, 14], target = 20,

Output: [[2, 0]]

Example 4:

Input:

a = [8, 15, 9], b = [8, 11, 12], target = 20,

Output: [[0, 2], [2, 1]]

##### Solve the problem:

Python3#### Get one-to-one training from Google Facebook engineers

##### Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

##### Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before interview? - Focus on most important problems in target company question bank.