MediumLinked ListsAI interview only
Count Pairs From Two Linked Lists With Sum
Asked atamazonmicrosoftadobe
01 · Problem
You are given two singly linked lists list1 and list2 and an integer x. Within each list, all values are distinct (a value may appear in both lists, though). Neither list is guaranteed to be sorted.
Return the number of pairs (a, b) such that a is a node of list1, b is a node of list2, and a.val + b.val == x. If no such pair exists, return 0.
02 · Examples
Example 01
Input
list1 = [1,2,3,4,5,6], list2 = [11,12,13], x = 15
Output
3
The valid pairs are (2, 13), (3, 12) and (4, 11).
Example 02
Input
list1 = [7,5,1,3], list2 = [3,5,2,8], x = 10
Output
2
The valid pairs are (7, 3) and (5, 5). The same value may be used once from each list.
Example 03
Input
list1 = [1], list2 = [2], x = 5
Output
0
1 + 2 = 3, so no pair sums to 5.
03 · Constraints
- 01The number of nodes in each list is in the range [1, 104].
- 02-105 <= Node.val <= 105
- 03-2 * 105 <= x <= 2 * 105
- 04All values within list1 are distinct, and all values within list2 are distinct.
04 · Optimal complexity
- Time
- O(n + m)
- Space
- O(m)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.