Count triplets in a sorted DLL with a given sum
Problem
Given a sorted doubly linked list of distinct values and a target x, count the triplets of nodes whose values sum to x.
Example 1
Input: 1 ⇄ 2 ⇄ 4 ⇄ 5 ⇄ 6 ⇄ 8 ⇄ 9, x = 17 Output: 2
(2, 6, 9) and (4, 5, 8).
Also asked as: Count triplets in a sorted DLL whose sum is equal to given value “X”
Test cases
Case 1
Input: [1,2,4,5,6,8,9], 17 Expected: 2
Case 2
Input: [1,2,4,5,6,8,9], 15 Expected: 5
Case 3
Input: [1,2,3], 6 Expected: 1
Case 4
Input: [1,2], 3 Expected: 0
View solutionHide solution1 approach
1. Fix one node, two-pointer the rest
Time O(n²)Space O(1)
For each node as the smallest of the triplet, run the "pair with sum (X − node.val)" two-pointer scan on the remainder.
function countTriplets(head, x) { let tail = head; while (tail && tail.next) tail = tail.next; let count = 0; for (let cur = head; cur; cur = cur.next) { let lo = cur.next, hi = tail; while (lo && hi && lo !== hi && hi.next !== lo) { const s = cur.val + lo.val + hi.val; if (s === x) { count++; lo = lo.next; hi = hi.prev; } else if (s < x) lo = lo.next; else hi = hi.prev; } } return count;}