Problem

Example 1:

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.