256. Count Triplets in a Sorted Doubly Linked List With a Given Sum

A doubly linked list contains n values sorted in ascending order. Given a target sum X, count how many triplets of positions i < j < k have values summing to exactly X. Print that count.

Input: The first line contains an integer n. The second line contains n space-separated integers already sorted ascending, the doubly linked list's values. The third line contains the target sum X. Output: Print a single integer - the count of triplets (i < j < k) whose values sum to X.

1 <= n <= 10^5

This is the linked-list version of the classic 'count triplets with given sum' array problem, made practical here specifically because the DOUBLY linked list supports walking backward from the tail just as easily as forward from the head - something a plain singly linked list could not do efficiently.

In a sorted doubly linked list, count how many triplets of positions have values summing to exactly a target. Brute force: Check every possible triplet of positions directly - this costs O(n³), too slow for larger lists. Optimised: Fixing the first element and using a two-pointer sweep (moving from both ends toward the middle) on the REMAINING values reduces the search from checking every triplet combination to a linear scan per fixed first element - the doubly linked list's backward pointers make walking from the back just as efficient as from the front, which a singly linked list couldn't support directly.

Copy the sorted list's values into an array for O(1) random access, then fix each position i in turn and run the classic sorted two-pointer scan (one pointer just after i moving right, one at the array's end moving left) to count pairs after i that sum to X minus the fixed value, adding their count to the running total. Fixing one element and two-pointering the remaining sorted range turns an O(n) inner search into an O(n) linear scan per fixed element instead of an O(n^2) nested search, bringing the whole algorithm down to quadratic - but it requires copying the list into an array first since arrays support jumping to both ends. Time: O(n^2) Space: O(n)

Skip the array copy entirely and exploit the fact that it's specifically a doubly linked list: for each fixed node i moving forward from the head, start one pointer at i's next node and another at the list's tail node (reachable directly because it's doubly linked, unlike a singly linked list), and move them toward each other based on how the current triplet sum compares to X, counting matches along the way. This gets the same quadratic time as the array-based version but needs no auxiliary array at all, since the list's own backward links provide the 'walk from the end' capability - which is exactly why this classic problem specifies a doubly linked list in the first place. Time: O(n^2) Space: O(1)

Directly check every combination of three positions i < j < k by walking the doubly linked list (or nested pointer advances) and testing whether their values sum to X, counting every triplet that matches. This directly implements the problem's definition and needs no extra structure, but examining every one of the roughly n^3/6 triplets makes it far too slow for the given constraints. Time: O(n^3) Space: O(1)

1. Fix the FIRST element of the triplet by walking forward one position at a time. 2. For each fixed first element, use the two-pointer technique (front and back pointers) on the REMAINING values to count pairs completing the needed sum - just like the two-sum-pairs version, but counting matches instead of just finding one. 3. Sum up the counts found for every choice of fixed first element.

Time: O(n²) - fixing each of the n elements as the first, with an O(n) two-pointer sweep for each. Space: O(1) extra space beyond the pointers used for the sweep.

n as small as 1 or 2, where no i<j<k triplet can exist at all (answer 0); runs of several equal consecutive values, which the two-pointer sweep must count exactly rather than assume distinct (per the hints); n = 10^5 for performance.

Be careful with REPEATED values - when several consecutive nodes share the same value, a naive 'move by one' two-pointer step can undercount how many equal-value pairs actually complete a valid triplet; counting matching runs explicitly (rather than assuming each occurrence is distinct) avoids this subtle bug.