Count Pairs whose sum is equal to X

Slug: count-pairs-whose-sum-is-equal-to-x Difficulty: Easy Id: 700607 Topic Tags: Linked List, Data Structures Company Tags: Amazon

Summary

Given a sorted linked list and an integer X, the problem requires you to find the number of pairs in the linked list whose sum is equal to X. This problem involves basic concepts of data structures and algorithms.

Detailed Explanation

To solve this problem, we can iterate through the linked list and for each node, try to find a pair that sums up to X by iterating backwards from the current node. If such a pair is found, increment the count. We also keep track of the previous node to avoid duplicate pairs.

Here's the step-by-step breakdown:

1. Initialize a counter variable count to 0.
2. Iterate through the linked list. For each node:
   • Initialize two pointers, prev and curr, to the current node and the previous node respectively.
   • While curr is not null:
     • If the sum of curr's value and prev's value equals X, increment the count.
     • Move prev one step forward.
     • Decrement curr until it becomes null or the sum exceeds X.
3. Return the count.

Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1).

Optimized Solutions

Java

java
public int countPairs(SinglyLinkedListNode node, int X) {
    int count = 0;
    SinglyLinkedListNode prev = null;
    for (SinglyLinkedListNode curr = node; curr != null; curr = curr.next) {
        while (prev != null && curr.value + prev.value > X) {
            prev = prev.next;
        }
        if (prev != null && curr.value + prev.value == X) {
            count++;
        }
        prev = curr;
    }
    return count;
}

Python