Find the Pair of Nodes with the Smallest Product in a Doubly Linked List - Coding

Given a doubly linked list, the task is to find the pair of nodes whose product is the smallest among all possible pairs. Each node in the list contains an integer value, and you need to find the two nodes whose multiplication results in the minimum product.

Examples:

Input: 4 <-> 6 <-> 3 <-> 1 <-> 2 -> NULL
Output: 1 and 2
Explanation: The pair (1, 2) has the smallest product, which is 1 * 2 = 2.

Input: 5 <-> 2 <-> 1 <-> 1 <-> 3 <-> 4 -> NULL
Output: 1 and 1
Explanation: The pair (1, 1) has the smallest product, which is 1 * 1 = 1.

Approach: To solve the problem follow the below idea:

The problem is to find the pair of nodes in a doubly linked list with the smallest product. To achieve this, we iterate through the list, keeping track of the minimum product and the corresponding pair of nodes. We start with a large initial minimum product value and then compare the product of each pair of nodes. If we find a smaller product, we update our minimum product and record the current pair. This way, we guarantee that we find the pair with the smallest product by the end of the iteration.

Steps of the approach:

Initialize minProduct to a large value and firstNode and secondNode to NULL to store the pair with the minimum product.
Traverse the doubly linked list from the beginning to the end.
For each node, iterate through the remaining nodes in the list.
Calculate the product of the current node’s value with the value of each subsequent node.
Compare the calculated product with the current minimum product.
If the calculated product is smaller, update minProduct, firstNode, and secondNode accordingly.
Continue this process for all nodes in the list, considering all possible pairs.
Once the iteration is complete, firstNode and secondNode will contain the nodes with the smallest product, and minProduct will store the minimum product value.

Below is the code for the above approach:

C++

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
 
// Doubly linked list node structure
struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int val)
        : data(val)
        , next(NULL)
        , prev(NULL)
    {
    }
};
 
// Function to find the pair of nodes
// with the smallest product
pair<int, int> findSmallestProductPair(Node* head)
{
 
    // Initialize the minimum
    // product to a large value
    int minProduct = INT_MAX;
 
    // Initialize pointers to track the nodes
    // with the smallest product
    Node* firstNode = NULL;
    Node* secondNode = NULL;
 
    // Start iterating from the head
    // of the linked list
    Node* current = head;
 
    // Create a temporary pointer
    // to iterate through the
    // remaining nodes
    while (current) {
        Node* temp = current->next;
 
        // Calculate the product of
        // current node and temp
        // node
        while (temp) {
            int product = current->data * temp->data;
 
            // Update the minimum product
            // and the corresponding
            // nodes if needed
            if (product < minProduct) {
                minProduct = product;
                firstNode = current;
                secondNode = temp;
            }
 
            // Move to the next node
            temp = temp->next;
        }
 
        // Move to the next node
        // for the outer loop
        current = current->next;
    }
 
    // Return the pair with the
    // smallest product
    return make_pair(firstNode->data, secondNode->data);
}
 
// Function to display the
// doubly linked list
void displayList(Node* head)
{
    Node* current = head;
    while (current) {
        cout << current->data;
 
        // Print a separator between
        // nodes
        if (current->next) {
            cout << " <-> ";
        }
        current = current->next;
    }
 
    // Print "NULL" at the end to signify
    // the end of the list
    cout << " -> NULL" << endl;
}
 
// Drivers code
int main()
{
 
    // Create a doubly linked
    // list for testing
    Node* head = new Node(4);
    head->next = new Node(6);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;
    head->next->next->next = new Node(1);
    head->next->next->next->prev = head->next->next;
    head->next->next->next->next = new Node(2);
    head->next->next->next->next->prev
        = head->next->next->next;
 
    // Find and display the pair with
    // the smallest product
    pair<int, int> result = findSmallestProductPair(head);
    cout << "Output: " << result.first << " and "
         << result.second << endl;
 
    return 0;
}

Java

class Node {
    int data;
    Node next;
    Node prev;
 
    Node(int val) {
        data = val;
        next = null;
        prev = null;
    }
}
 
public class Main {
    // Function to find the pair of nodes with the smallest product
    static int[] findSmallestProductPair(Node head) {
        // Initialize the minimum product to a large value
        int minProduct = Integer.MAX_VALUE;
 
        // Initialize pointers to track the nodes with the smallest product
        Node firstNode = null;
        Node secondNode = null;
 
        // Start iterating from the head of the linked list
        Node current = head;
 
        // Iterate through the remaining nodes
        while (current != null) {
            Node temp = current.next; // Create a temporary pointer to iterate through the remaining nodes
 
            // Calculate the product of the current node and temp node
            while (temp != null) {
                int product = current.data * temp.data;
 
                // Update the minimum product and the corresponding nodes if needed
                if (product < minProduct) {
                    minProduct = product;
                    firstNode = current;
                    secondNode = temp;
                }
 
                // Move to the next node
                temp = temp.next;
            }
 
            // Move to the next node for the outer loop
            current = current.next;
        }
 
        // Return the pair with the smallest product
        return new int[]{firstNode.data, secondNode.data};
    }
 
    // Function to display the doubly linked list
    static void displayList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data);
 
            // Print a separator between nodes
            if (current.next != null) {
                System.out.print(" <-> ");
            }
            current = current.next;
        }
 
        // Print "None" at the end to signify the end of the list
        System.out.println(" -> NULL");
    }
 
    public static void main(String[] args) {
        // Create a doubly linked list for testing
        Node head = new Node(4);
        head.next = new Node(6);
        head.next.prev = head;
        head.next.next = new Node(3);
        head.next.next.prev = head.next;
        head.next.next.next = new Node(1);
        head.next.next.next.prev = head.next.next;
        head.next.next.next.next = new Node(2);
        head.next.next.next.next.prev = head.next.next.next;
 
        // Find and display the pair with the smallest product
        int[] result = findSmallestProductPair(head);
        System.out.println("Output: " + result[0] + " and " + result[1]);
    }
}

Python3

# Python code for finding the pair of nodes with the smallest product
 
# Doubly linked list node structure
class Node:
    def __init__(self, val):
        self.data = val
        self.next = None
        self.prev = None
 
# Function to find the pair of nodes with the smallest product
def find_smallest_product_pair(head):
    # Initialize the minimum product to a large value
    min_product = float('inf')
 
    # Initialize pointers to track the nodes with the smallest product
    first_node = None
    second_node = None
 
    # Start iterating from the head of the linked list
    current = head
 
    # Iterate through the remaining nodes
    while current:
        temp = current.next  # Create a temporary pointer to iterate through the remaining nodes
 
        # Calculate the product of the current node and temp node
        while temp:
            product = current.data * temp.data
 
            # Update the minimum product and the corresponding nodes if needed
            if product < min_product:
                min_product = product
                first_node = current
                second_node = temp
 
            # Move to the next node
            temp = temp.next
 
        # Move to the next node for the outer loop
        current = current.next
 
    # Return the pair with the smallest product
    return (first_node.data, second_node.data)
 
# Function to display the doubly linked list
def display_list(head):
    current = head
    while current:
        print(current.data, end="")
 
        # Print a separator between nodes
        if current.next:
            print(" <-> ", end="")
        current = current.next
 
    # Print "None" at the end to signify the end of the list
    print(" -> None")
 
# Drivers code
if __name__ == "__main__":
    # Create a doubly linked list for testing
    head = Node(4)
    head.next = Node(6)
    head.next.prev = head
    head.next.next = Node(3)
    head.next.next.prev = head.next
    head.next.next.next = Node(1)
    head.next.next.next.prev = head.next.next
    head.next.next.next.next = Node(2)
    head.next.next.next.next.prev = head.next.next.next
 
    # Find and display the pair with the smallest product
    result = find_smallest_product_pair(head)
    print("Output:", result[0], "and", result[1])

C#

using System;
 
// Doubly linked list node structure
public class Node
{
    public int data;
    public Node next;
    public Node prev;
 
    public Node(int val)
    {
        data = val;
        next = null;
        prev = null;
    }
}
 
class Program
{
    // Function to find the pair of nodes with the smallest product
    static Tuple<int, int> FindSmallestProductPair(Node head)
    {
        // Initialize the minimum product to a large value
        int minProduct = int.MaxValue;
 
        // Initialize pointers to track the nodes with the smallest product
        Node firstNode = null;
        Node secondNode = null;
 
        // Start iterating from the head of the linked list
        Node current = head;
 
        // Create a temporary pointer to iterate through the remaining nodes
        while (current != null)
        {
            Node temp = current.next;
 
            // Calculate the product of current node and temp node
            while (temp != null)
            {
                int product = current.data * temp.data;
 
                // Update the minimum product and the corresponding nodes if needed
                if (product < minProduct)
                {
                    minProduct = product;
                    firstNode = current;
                    secondNode = temp;
                }
 
                // Move to the next node
                temp = temp.next;
            }
 
            // Move to the next node for the outer loop
            current = current.next;
        }
 
        // Return the pair with the smallest product
        return Tuple.Create(firstNode.data, secondNode.data);
    }
 
    // Function to display the doubly linked list
    static void DisplayList(Node head)
    {
        Node current = head;
        while (current != null)
        {
            Console.Write(current.data);
 
            // Print a separator between nodes
            if (current.next != null)
            {
                Console.Write(" <-> ");
            }
            current = current.next;
        }
 
        // Print "NULL" at the end to signify the end of the list
        Console.WriteLine(" -> NULL");
    }
 
    // Main method
    static void Main()
    {
        // Create a doubly linked list for testing
        Node head = new Node(4);
        head.next = new Node(6);
        head.next.prev = head;
        head.next.next = new Node(3);
        head.next.next.prev = head.next;
        head.next.next.next = new Node(1);
        head.next.next.next.prev = head.next.next;
        head.next.next.next.next = new Node(2);
        head.next.next.next.next.prev = head.next.next.next;
 
        // Find and display the pair with the smallest product
        Tuple<int, int> result = FindSmallestProductPair(head);
        Console.WriteLine("Output: " + result.Item1 + " and " + result.Item2);
    }
}

Javascript

// Doubly linked list node structure
class Node {
    constructor(val) {
        this.data = val;
        this.next = null;
        this.prev = null;
    }
}
 
// Function to find the pair of nodes with the smallest product
function findSmallestProductPair(head) {
    // Initialize the minimum product to a large value
    let minProduct = Infinity;
 
    // Initialize pointers to track the nodes with the smallest product
    let firstNode = null;
    let secondNode = null;
 
    // Start iterating from the head of the linked list
    let current = head;
 
    // Create a temporary pointer to iterate through the remaining nodes
    while (current) {
        let temp = current.next;
 
        // Calculate the product of current node and temp node
        while (temp) {
            let product = current.data * temp.data;
 
            // Update the minimum product and the corresponding nodes if needed
            if (product < minProduct) {
                minProduct = product;
                firstNode = current;
                secondNode = temp;
            }
 
            // Move to the next node
            temp = temp.next;
        }
 
        // Move to the next node for the outer loop
        current = current.next;
    }
 
    // Return the pair with the smallest product
    return [firstNode.data, secondNode.data];
}
 
// Function to display the doubly linked list
function displayList(head) {
    let current = head;
    while (current) {
        console.log(current.data);
 
        // Print a separator between nodes
        if (current.next) {
            console.log(" <-> ");
        }
        current = current.next;
    }
 
    // Print "NULL" at the end to signify the end of the list
    console.log(" -> NULL");
}
 
// Drivers code
function main() {
    // Create a doubly linked list for testing
    let head = new Node(4);
    head.next = new Node(6);
    head.next.prev = head;
    head.next.next = new Node(3);
    head.next.next.prev = head.next;
    head.next.next.next = new Node(1);
    head.next.next.next.prev = head.next.next;
    head.next.next.next.next = new Node(2);
    head.next.next.next.next.prev = head.next.next.next;
 
    // Find and display the pair with the smallest product
    let result = findSmallestProductPair(head);
    console.log("Output: " + result[0] + " and " + result[1]);
}
 
// Run the main function
main();

Output

Output: 1 and 2

Time Complexity: O(n), where n is the number of nodes in the doubly linked list.
Auxiliary Space: O(1) because we use a constant amount of extra space.

Reffered: https://www.geeksforgeeks.org

DSA

Related
Fill the Matrix by following the given conditions
Move the Kth Element in a Doubly Linked List to the End
Move the Kth element to the Front of a Doubly Linked List
Minimizing Infection Time in a Directed Graph
Maximum Distance with Blocked Edges from Vertex 0

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13