Find pairs with given sum in Doubly Linked List

101.5k
0

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the first value of each pair.

A doubly linked list node contains a value, a next pointer, and a previous pointer. Sorted order enables movement from both ends during the optimal solution.

Example 1

Input: DLL = [1, 2, 4, 5, 6, 8], target = 7

Output: [[1, 6], [2, 5]]

Explanation: Values 1 and 6 form sum 7. Values 2 and 5 also form sum 7.

Example 2

Input: DLL = [1, 3, 5, 7, 9], target = 10

Output: [[1, 9], [3, 7]]

Explanation: Values 1 and 9 form sum 10. Values 3 and 7 also form sum 10.

Brute Force Approach

A complement lookup can detect pair values during a single forward traversal. For every node value, target minus current value gives the needed partner. A hash set stores previously visited values, so a matching complement proves a valid pair.

Sorted output order still matters. Since complement matches can be discovered based on traversal order, collected pairs are sorted before returning. Knowledge of hash sets and pair sorting is enough for the hashing approach.

Algorithm

  • Initialize an empty answer list and a hash set, where the hash set stores previously visited values and the answer list stores the valid pairs.

  • Traverse the doubly linked list from head to tail, as every node value can potentially form a pair with a previously visited value.

  • Calculate complement = target - current->data, since this is the value required to make the current value sum to the target.

  • If the complement already exists in the hash set, append the pair {complement, current->data} to answer, as both values have now been encountered and together satisfy the target sum.

  • Insert current->data into the hash set, so it becomes available as a possible complement for subsequent nodes.

  • Continue until the entire list has been traversed, ensuring all possible pairs are considered.

  • Sort answer by the first value, as the pairs need to be returned in the required sorted order.

  • Return answer after sorting, since it now contains all valid pairs in the expected order.

Dry Run

pair sum

pair sum

Solution

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node* prev;
// Constructor for a doubly linked list node.
Node(int value) {
data = value;
next = nullptr;
prev = nullptr;
}
};
class Solution {
public:
// Finds all pairs whose sum equals the target.
vector<pair<int, int>> findPairsWithGivenSum(Node* head, int target) {
vector<pair<int, int>> answer;
unordered_set<int> seen;
Node* current = head;
// Traverse the list and search for the required complement.
while (current != nullptr) {
int complement = target - current->data;
// Add the pair if its complement was already visited.
if (seen.find(complement) != seen.end()) {
answer.push_back({complement, current->data});
}
seen.insert(current->data);
current = current->next;
}
// Arrange pairs in increasing order.
sort(answer.begin(), answer.end());
return answer;
}
};
// Builds a doubly linked list from the given array.
Node* buildList(vector<int>& values) {
if (values.empty()) {
return nullptr;
}
Node* head = new Node(values[0]);
Node* tail = head;
for (int index = 1; index < (int)values.size(); index++) {
Node* node = new Node(values[index]);
tail->next = node;
node->prev = tail;
tail = node;
}
return head;
}
// Driver code.
int main() {
vector<int> values = {1, 2, 4, 5, 6, 8};
int target = 7;
Node* head = buildList(values);
Solution solution;
vector<pair<int, int>> result =
solution.findPairsWithGivenSum(head, target);
for (auto pairValue : result) {
cout << pairValue.first << " "
<< pairValue.second << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), traversal costs O(N) and sorting collected pairs costs up to O(N log N).

Space Complexity: O(N), hash set storage can contain every list value.

Optimal Approach

The sorted doubly linked list allows pair search from both ends. A left pointer starts at the head and a right pointer starts at the tail. Current sum decides the next movement because increasing the smaller side raises the sum and decreasing the larger side lowers the sum.

The previous pointer gives direct movement from tail toward head, so no extra container is required. The process naturally returns pairs in increasing first-value order because the left pointer only moves forward.

Algorithm

  • Return an empty list when head is NULL, as there are no nodes available to form a pair.

  • Initialize left at head and move right to the tail node, as the sorted list allows the pair search to begin from both extremes.

  • Traverse while left and right have not met or crossed, since a valid pair requires two distinct nodes.

  • Calculate sum using the values of left and right, as their combined value determines whether the current pair can satisfy the target.

  • If sum equals the target, add the pair to the answer and move both pointers inward, since the current pair is valid and neither node needs to be considered again.

  • If sum is smaller than the target, move left forward, as increasing the smaller value is what can raise the sum toward the target.

  • If sum is greater than the target, move right backward, as decreasing the larger value is what can bring the sum down toward the target.

  • Continue until the pointers meet or cross, ensuring all possible valid pairs have been considered.

  • Return the collected pairs, which naturally appear in increasing order of their first value because left moves only forward.

Dry Run

pair sum by two pointers

pair sum by two pointers

Solution

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) {
data = value;
next = nullptr;
prev = nullptr;
}
};
class Solution {
public:
// Find all pairs with target sum using two pointers.
vector<pair<int, int>> findPairsWithGivenSum(Node* head, int target) {
vector<pair<int, int>> answer;
if (head == nullptr) {
return answer;
}
Node* left = head;
Node* right = head;
// Move right pointer to final node.
while (right->next != nullptr) {
right = right->next;
}
// Move pointers inward until meeting or crossing.
while (left != right && right->next != left) {
int sum = left->data + right->data;
if (sum == target) {
answer.push_back({left->data, right->data});
left = left->next;
right = right->prev;
} else if (sum < target) {
left = left->next;
} else {
right = right->prev;
}
}
return answer;
}
};
// Build a doubly linked list from array values.
Node* buildList(vector<int>& values) {
if (values.empty()) {
return nullptr;
}
Node* head = new Node(values[0]);
Node* tail = head;
for (int index = 1; index < (int)values.size(); index++) {
Node* node = new Node(values[index]);
tail->next = node;
node->prev = tail;
tail = node;
}
return head;
}
// Driver code with a fixed sample.
int main() {
vector<int> values = {1, 2, 4, 5, 6, 8};
int target = 7;
Node* head = buildList(values);
Solution solution;
vector<pair<int, int>> result = solution.findPairsWithGivenSum(head, target);
for (auto pairValue : result) {
cout << pairValue.first << " " << pairValue.second << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), tail discovery and inward pointer traversal visit nodes linearly.

Space Complexity: O(1), only pointer variables and answer storage are used.

Interview follow-up Questions

No. The two pointer movement depends on sorted order. An unsorted list needs hashing or sorting before two pointer usage.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.9k
Linked List

Merge Two Sorted Linked Lists

Given heads of two sorted linked lists, merge both lists into one sorted linked list and return the head of the merged list. Every node stores an integer value and a pointer to the next node. The f...

114.6k
Linked List

Remove Duplicates from a Sorted Doubly Linked List

Given the head of a sorted doubly linked list, remove duplicate nodes so every value appears exactly once and return the head of the modified list. Each node stores an integer value, a next pointer...

87.2k
Comments0