Count triplets in a sorted DLL with a given sum

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}