Add Two Polynomials Represented as Linked Lists

Medium

Asked by:

9 views

Topics:

Linked Lists

A polynomial can be represented as a linked list where each node contains two attributes: coefficient and power. The coefficient is an integer representing the coefficient of the term, while the power is an integer representing the power of the variable 'x'.

For example, the polynomial 5x^3 + 4x - 7 can be represented as the following linked list:

You are given two polynomial linked lists, poly1 and poly2, represented as linked lists. Add the two polynomials and return the head of the new polynomial linked list. The head of the new linked list should point to a node with the highest power, and each node should represent a term in the polynomial.

You may assume that the input polynomials are sorted in decreasing order of power. You are not allowed to use extra space other than the new linked list itself. Merge the two lists into one.

Example 1:

Input: poly1 = [[1,1],[2,2]], poly2 = [[3,1],[4,2]]
Output: [[4,2],[4,1]]
Explanation: 2x² + 1x¹ + 4x² + 3x¹ = 4x² + 4x¹

Example 2:

Input: poly1 = [[1,2]], poly2 = [[-1,2]]
Output: []
Explanation: 1x² + -1x² = 0. The resulting polynomial is 0, so return an empty list.

Example 3:

Input: poly1 = [[1,2],[2,1]], poly2 = [[-1,2],[-2,1]]
Output: []

Constraints:

The number of nodes in poly1 and poly2 is in the range [1, 1000].
-1000 <= Node.coefficient <= 1000
0 <= Node.power <= 1000
Node.power is strictly greater than the power of the next node in the same list.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible exponents and coefficients in the polynomials? Can exponents or coefficients be negative or zero?
Are the polynomial linked lists guaranteed to be sorted by exponent in descending order, and can there be duplicate exponents within a single polynomial?
Should I return a new linked list representing the sum, or can I modify one of the input lists in-place?
If the sum of coefficients for a specific exponent is zero, should I omit that term from the resulting polynomial?
What should be returned if both input polynomials are null or empty?

Brute Force Solution

Approach

We want to add two polynomials together, where each polynomial is represented as a list of terms. The brute force method involves directly comparing and combining each term from the first polynomial with every term from the second polynomial.

Here's how the algorithm would work step-by-step:

Take the first term from the first polynomial.
Compare its exponent to the exponent of every term in the second polynomial.
If you find a term in the second polynomial with the same exponent, add their coefficients together and create a new term with that coefficient and exponent.
If you don't find a term with the same exponent, just keep the original term from the first polynomial.
Repeat this process for every term in the first polynomial, checking against all terms in the second polynomial each time.
After doing this, you will likely have a new list of terms. Check this list for terms with the same exponent, and if there are any, combine their coefficients into a single term.
Finally, arrange the remaining terms from largest exponent to smallest exponent, giving you the sum of the two polynomials.

Code Implementation

class Term:
    def __init__(self, coefficient, exponent):
        self.coefficient = coefficient
        self.exponent = exponent

    def __repr__(self):
        return f'({self.coefficient}x^{self.exponent})'

def add_polynomials_brute_force(polynomial1, polynomial2):
    added_terms = []

    for term1 in polynomial1:
        for term2 in polynomial2:
            if term1.exponent == term2.exponent:
                # Combine coefficients if exponents match.
                added_terms.append(Term(term1.coefficient + term2.coefficient, term1.exponent))
                break
        else:
            # Keep the original term if no matching exponent is found.
            added_terms.append(term1)

    for term2 in polynomial2:
        exponent_found = False
        for term1 in polynomial1:
            if term1.exponent == term2.exponent:
                exponent_found = True
                break
        if not exponent_found:
            added_terms.append(term2)

    combined_terms = []
    for term in added_terms:
        exponent_exists = False
        for combined_term in combined_terms:
            if term.exponent == combined_term.exponent:
                combined_term.coefficient += term.coefficient
                exponent_exists = True
                break
        if not exponent_exists:
            combined_terms.append(Term(term.coefficient, term.exponent))

    # Sort terms by exponent in descending order.
    combined_terms.sort(key=lambda term: term.exponent, reverse=True)

    return combined_terms

Big(O) Analysis

Time Complexity

O(n²) – The provided algorithm iterates through each term of the first polynomial (let's say it has n terms) and compares it with every term of the second polynomial (also assumed to have approximately n terms for simplicity). This involves a nested loop structure where for each of the n terms in the first polynomial, we iterate through approximately n terms in the second polynomial. This results in roughly n * n comparisons and potential additions. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The algorithm creates a new list to store the resulting polynomial, which in the worst case could contain a number of terms proportional to the sum of the number of terms in the input polynomials. Let N be the total number of terms in both input polynomials. The new list requires space proportional to N to store the combined polynomial. The temporary list potentially holds intermediate terms before the combination and sorting steps, contributing to O(N) space as well. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The best way to add two polynomials represented as linked lists is to go through both lists at the same time. We combine terms that have the same power, creating a new linked list to store the result.

Here's how the algorithm would work step-by-step:

Start by looking at the first terms in both polynomial lists.
If the terms have the same power, add their coefficients together and create a new term with that combined coefficient and the power. Then, move to the next terms in both lists.
If the terms have different powers, take the term with the higher power and add it to the result list without any changes. Then, move to the next term in that list only.
Keep doing this until you reach the end of both lists.
If one list is longer than the other, simply add the remaining terms from the longer list to the result list, since there's nothing to combine them with.
The result list will now contain the sum of the two polynomials.

Code Implementation

class PolynomialNode:
    def __init__(self, coefficient, power, next_node=None):
        self.coefficient = coefficient
        self.power = power
        self.next_node = next_node

def add_polynomials(polynomial_one_head, polynomial_two_head):
    result_head = None
    result_tail = None

    while polynomial_one_head and polynomial_two_head:
        if polynomial_one_head.power > polynomial_two_head.power:
            # The power in poly1 is greater, so add its term to result.
            new_node = PolynomialNode(polynomial_one_head.coefficient, polynomial_one_head.power)
            polynomial_one_head = polynomial_one_head.next_node

        elif polynomial_one_head.power < polynomial_two_head.power:
            # The power in poly2 is greater, so add its term to result.
            new_node = PolynomialNode(polynomial_two_head.coefficient, polynomial_two_head.power)
            polynomial_two_head = polynomial_two_head.next_node

        else:
            # Powers are equal, combine coefficients.
            sum_coefficient = polynomial_one_head.coefficient + polynomial_two_head.coefficient

            # Only add to the result if the combined coefficient is non-zero.
            if sum_coefficient != 0:
                new_node = PolynomialNode(sum_coefficient, polynomial_one_head.power)
            else:
                new_node = None

            polynomial_one_head = polynomial_one_head.next_node
            polynomial_two_head = polynomial_two_head.next_node

        if new_node:
            if not result_head:
                result_head = new_node
                result_tail = new_node
            else:
                result_tail.next_node = new_node
                result_tail = new_node

    # Add remaining terms from polynomial_one_head, if any
    while polynomial_one_head:
        new_node = PolynomialNode(polynomial_one_head.coefficient, polynomial_one_head.power)
        if not result_head:
            # Initialize result list if it's empty.
            result_head = new_node
            result_tail = new_node
        else:
            result_tail.next_node = new_node
            result_tail = new_node
        polynomial_one_head = polynomial_one_head.next_node

    # Add remaining terms from polynomial_two_head, if any
    while polynomial_two_head:
        new_node = PolynomialNode(polynomial_two_head.coefficient, polynomial_two_head.power)
        if not result_head:
            # Initialize result list if it's empty.
            result_head = new_node
            result_tail = new_node
        else:
            result_tail.next_node = new_node
            result_tail = new_node
        polynomial_two_head = polynomial_two_head.next_node

    return result_head

Big(O) Analysis

Time Complexity

O(n) – We iterate through both linked lists, which represent the polynomials, at most once. Let 'n' be the total number of terms in both polynomial lists combined. In each step, we either add coefficients of terms with the same power, or add a term directly to the result if its power is unique. Therefore, the time complexity is directly proportional to the number of terms in the input, making it O(n).

Space Complexity

O(N) – The primary space complexity comes from creating a new linked list to store the result of the polynomial addition. In the worst-case scenario, where no terms have the same power, the resulting linked list will contain all terms from both input polynomial lists. Therefore, if N is the total number of terms in both input polynomials, the auxiliary space used for the new linked list will be proportional to N. This results in O(N) space complexity.

Edge Cases

Case	How to Handle
Both polynomials are null/empty	Return null/empty list to indicate a zero polynomial result.
One polynomial is null/empty, the other is not	Return the non-null polynomial as the result.
Polynomials have terms with the same exponent	Sum the coefficients of terms with the same exponent to combine them into a single term.
Polynomials have terms with exponents in reverse order	The algorithm should correctly traverse and add terms irrespective of exponent order.
Coefficients are very large (potential overflow)	Use a data type that can accommodate large numbers, or implement overflow detection and handling.
Resulting polynomial has a zero coefficient term	The zero coefficient term should be removed from the resulting linked list.
Polynomial represented by one node with coefficient and exponent zero	Return null/empty list.
Large exponents (potential memory issues if exponent used as array index)	Linked list structure avoids memory issues associated with large exponents, ensuring scalability.

Both polynomials are null/empty

How to Handle:

Return null/empty list to indicate a zero polynomial result.

One polynomial is null/empty, the other is not

How to Handle:

Return the non-null polynomial as the result.

Polynomials have terms with the same exponent

How to Handle:

Sum the coefficients of terms with the same exponent to combine them into a single term.

Polynomials have terms with exponents in reverse order

How to Handle:

The algorithm should correctly traverse and add terms irrespective of exponent order.

Coefficients are very large (potential overflow)

How to Handle:

Use a data type that can accommodate large numbers, or implement overflow detection and handling.

Resulting polynomial has a zero coefficient term

How to Handle:

The zero coefficient term should be removed from the resulting linked list.

Polynomial represented by one node with coefficient and exponent zero

How to Handle:

Return null/empty list.

Large exponents (potential memory issues if exponent used as array index)

How to Handle:

Linked list structure avoids memory issues associated with large exponents, ensuring scalability.