LinkedListProblem 22 of 36
Count triplets in a sorted DLL whose sum is equal to given value X
Count Triplets in a Sorted DLL Whose Sum is Equal to Given Value X
Problem Statement
Given a sorted doubly linked list of distinct nodes and a value x, count all triplets in the list whose sum is equal to x.
Example
Input: 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9, x = 15
Output: 3
Explanation: Triplets are (1, 6, 8), (2, 4, 9), (2, 5, 8)
Input: 1 <-> 2 <-> 3 <-> 4, x = 6
Output: 1
Explanation: Triplet is (1, 2, 3)
Brute Force Approach
Intuition
The brute force approach uses three nested loops to check every possible triplet in the list. For each combination of three nodes, we check if their sum equals the target value x.
Algorithm
- Use three nested loops to generate all possible triplets
- For each triplet, calculate the sum
- If sum equals x, increment the count
- Return the total count
Code
java
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class CountTriplets {
public static int countTripletsBruteForce(Node head, int x) {
int count = 0;
if (head == null) return count;
Node first = head;
while (first != null) {
Node second = first.next;
while (second != null) {
Node third = second.next;
while (third != null) {
int sum = first.data + second.data + third.data;
if (sum == x) {
count++;
}
// Optimization: since list is sorted
if (sum > x) {
break;
}
third = third.next;
}
second = second.next;
}
first = first.next;
}
return count;
}
public static void main(String[] args) {
// Create sample list and test
Node head = new Node(1);
head.next = new Node(2);
head.next.prev = head;
// ... continue building list
int x = 15;
System.out.println("Count of triplets: " + countTripletsBruteForce(head, x));
}
}Complexity Analysis
- Time Complexity: O(n³) - Three nested loops
- Space Complexity: O(1) - Only using constant extra space
Optimal Approach
Intuition
We can optimize by fixing one element and using the two-pointer technique to find pairs that sum to (x - fixed element). Since the list is sorted and doubly linked, we can efficiently traverse from both ends.
Algorithm
- Find the tail of the list
- For each node as the first element of triplet:
- Set left pointer to the next node
- Set right pointer to the tail
- Use two-pointer technique to find pairs summing to (x - first element's data)
- Count all valid triplets found
Code
java
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class CountTripletsOptimal {
public static int countTripletsOptimal(Node head, int x) {
int count = 0;
if (head == null || head.next == null || head.next.next == null) {
return count;
}
// Find the tail
Node tail = head;
while (tail.next != null) {
tail = tail.next;
}
// Fix the first element
Node first = head;
while (first != null && first.next != null && first.next.next != null) {
int target = x - first.data;
// Two pointer for remaining elements
Node left = first.next;
Node right = tail;
while (left != right && left.prev != right) {
int sum = left.data + right.data;
if (sum == target) {
count++;
left = left.next;
right = right.prev;
}
else if (sum < target) {
left = left.next;
}
else {
right = right.prev;
}
}
first = first.next;
}
return count;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" <-> ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
// Create sample list: 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9
Node head = new Node(1);
Node curr = head;
int[] values = {2, 4, 5, 6, 8, 9};
for (int val : values) {
Node newNode = new Node(val);
curr.next = newNode;
newNode.prev = curr;
curr = newNode;
}
int x = 15;
System.out.print("List: ");
printList(head);
System.out.println("Count of triplets with sum " + x + ": " + countTripletsOptimal(head, x));
}
}Complexity Analysis
- Time Complexity: O(n²) - One loop for first element, two-pointer technique for the remaining
- Space Complexity: O(1) - Only using constant extra space
Key Takeaways
- Reduce Problem Dimension: Convert 3-sum to 2-sum by fixing one element
- Two Pointer Efficiency: Sorted DLL allows efficient two-pointer traversal in O(n)
- DLL Advantage: The prev pointer enables backward traversal without extra space
- Early Termination: The sorted property allows breaking early when sum exceeds target
- Extension of Pairs Problem: This problem builds on the "find pairs with sum" concept
- Complexity Reduction: We reduced from O(n³) to O(n²) using the two-pointer technique