Problem statement

https://binarysearch.com/problems/Max-Multiplied-Pairings/

Solution

First, if we have different sizes, add zeroes to the smaller one. Then we can use Rearrangement inequality: sum will be maximum if we sort both arrays and take products of corresponding elements.

Complexity

It is O(n log n) for time, where n = max(len(A), len(B)) and O(n) for space.

Code

class Solution:
    def solve(self, A, B):
        if len(A) > len(B): A, B = B, A
        n = len(B)
        A = [0]*(n - len(A)) + A
        A, B = sorted(A), sorted(B)
        return sum(x*y for x, y in zip(A, B))