Problem

You are given two integer arrays poly1 and poly2, where the element at index i in each array represents the coefficient of xi in a polynomial.

Let A(x) and B(x) be the polynomials represented by poly1 and poly2, respectively.

Return an integer array result of length (poly1.length + poly2.length - 1) representing the coefficients of the product polynomial R(x) = A(x) * B(x), where result[i] denotes the coefficient of xi in R(x).

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: poly1 = [3,2,5], poly2 = [1,4]

Output: [3,14,13,20]

Explanation:

A(x) = 3 + 2x + 5x2 and B(x) = 1 + 4x
R(x) = (3 + 2x + 5x2) * (1 + 4x)
R(x) = 3 * 1 + (3 * 4 + 2 * 1)x + (2 * 4 + 5 * 1)x2 + (5 * 4)x3
R(x) = 3 + 14x + 13x2 + 20x3
Thus, result = [3, 14, 13, 20].

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Output: [-1,0,2]

Explanation:

A(x) = 1 + 0x - 2x2 and B(x) = -1
R(x) = (1 + 0x - 2x2) * (-1)
R(x) = -1 + 0x + 2x2
Thus, result = [-1, 0, 2].

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: poly1 = [1,5,-3], poly2 = [-4,2,0]

Output: [-4,-18,22,-6,0]

Explanation:

A(x) = 1 + 5x - 3x2 and B(x) = -4 + 2x + 0x2
R(x) = (1 + 5x - 3x2) * (-4 + 2x + 0x2)
R(x) = 1 * -4 + (1 * 2 + 5 * -4)x + (5 * 2 + -3 * -4)x2 + (-3 * 2)x3 + 0x4
R(x) = -4 -18x + 22x2 -6x3 + 0x4
Thus, result = [-4, -18, 22, -6, 0].

Constraints

  • 1 <= poly1.length, poly2.length <= 5 * 10^4
  • -10^3 <= poly1[i], poly2[i] <= 10^3
  • poly1 and poly2 contain at least one non-zero coefficient.

Solution

Method 1 -

Intuition

Multiplying two polynomials is similar to multiplying two numbers: for each term in the first polynomial, multiply it by each term in the second, and sum coefficients for like powers.

Approach

Assume each polynomial is represented as a list of [coefficient, power] pairs. For each pair in poly1, multiply by each pair in poly2, sum coefficients for matching powers using a map/dictionary, and return the result as a list of [coefficient, power] pairs sorted by descending power.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

vector<vector<int>> multiplyPoly(vector<vector<int>>& poly1, vector<vector<int>>& poly2) {
    unordered_map<int, int> coeffs;
    for (auto& a : poly1) {
        for (auto& b : poly2) {
            int coef = a[0] * b[0];
            int pow = a[1] + b[1];
            coeffs[pow] += coef;
        }
    }
    vector<vector<int>> res;
    for (auto& [pow, coef] : coeffs) {
        if (coef != 0) res.push_back({coef, pow});
    }
    sort(res.begin(), res.end(), [](auto& x, auto& y){ return x[1] > y[1]; });
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public List<List<Integer>> multiplyPoly(List<List<Integer>> poly1, List<List<Integer>> poly2) {
    Map<Integer, Integer> coeffs = new HashMap<>();
    for (List<Integer> a : poly1) {
        for (List<Integer> b : poly2) {
            int coef = a.get(0) * b.get(0);
            int pow = a.get(1) + b.get(1);
            coeffs.put(pow, coeffs.getOrDefault(pow, 0) + coef);
        }
    }
    List<List<Integer>> res = new ArrayList<>();
    for (int pow : coeffs.keySet()) {
        int coef = coeffs.get(pow);
        if (coef != 0) res.add(Arrays.asList(coef, pow));
    }
    res.sort((x, y) -> y.get(1) - x.get(1));
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def multiplyPoly(poly1, poly2):
    from collections import defaultdict
    coeffs = defaultdict(int)
    for a in poly1:
        for b in poly2:
            coef = a[0] * b[0]
            pow = a[1] + b[1]
            coeffs[pow] += coef
    res = [[coef, pow] for pow, coef in coeffs.items() if coef != 0]
    res.sort(key=lambda x: -x[1])
    return res

Complexity

  • ⏰ Time complexity: O(M*N) where M, N are the lengths of the two polynomials.
  • 🧺 Space complexity: O(M+N) for the result.