Two Sum Smaller Than Target

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.

Example 1:
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
def twoSumSmaller(A, B, target): """ :type A: List[int] :type B: List[int] :type target: int :rtype: List[List[int]] """





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.