Minimize Product Sum of Two Arrays - Practice Coding Problems

Minimize Product Sum of Two Arrays - Problem

The product sum of two equal-length arrays a and b is equal to the sum of a[i] * b[i] for all 0 <= i < a.length (0-indexed).

For example, if a = [1,2,3,4] and b = [5,2,3,1], the product sum would be 1*5 + 2*2 + 3*3 + 4*1 = 22.

Given two arrays nums1 and nums2 of length n, return the minimum product sum if you are allowed to rearrange the order of the elements in nums1.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [5,3,2,4], nums2 = [2,1,4,5]

› Output: 35

💡 Note: Sort nums1 ascending [2,3,4,5] and nums2 descending [5,4,2,1]. Product sum: 2×5 + 3×4 + 4×2 + 5×1 = 10 + 12 + 8 + 5 = 35

Example 2 — Minimum Size

$ Input: nums1 = [3,1], nums2 = [2,5]

› Output: 11

💡 Note: Sort nums1 [1,3] and nums2 descending [5,2]. Product sum: 1×5 + 3×2 = 5 + 6 = 11

Example 3 — All Same Values

$ Input: nums1 = [2,2,2], nums2 = [3,3,3]

› Output: 18

💡 Note: All elements are same, so any arrangement gives: 2×3 + 2×3 + 2×3 = 6 + 6 + 6 = 18

Constraints

n == nums1.length == nums2.length
1 ≤ n ≤ 1000
-100 ≤ nums1[i], nums2[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays nums1=[5,3,2,4] and nums2=[2,1,4,5]

Strategy

Pair smallest from nums1 with largest from nums2

Output

Minimum product sum = 35

Key Takeaway

🎯 Key Insight: Pair smallest elements with largest elements to minimize product sum

Asked in

G Google 15 a Amazon 12 M Microsoft 8

Brief HTML summary: The key insight is to pair smallest elements from nums1 with largest elements from nums2 to minimize the product sum. Best approach is greedy sorting: sort nums1 ascending and nums2 descending, then multiply corresponding pairs. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Try All Permutations	O(n! × n)	O(n!)	Generate all possible arrangements of nums1 and find minimum product sum
Greedy Sorting Approach	O(n log n)	O(1)	Sort nums1 ascending and nums2 descending, then pair elements

Try All Permutations — Algorithm Steps

Generate all permutations of nums1
Calculate product sum for each permutation
Return minimum sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of nums1

Calculate Each Sum

Compute product sum for each arrangement

Find Minimum

Return the smallest sum found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int calculateSum(int* nums1, int* nums2, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += nums1[i] * nums2[i];
    }
    return sum;
}

void permute(int* nums1, int start, int n, int* nums2, int* minSum) {
    if (start == n) {
        int sum = calculateSum(nums1, nums2, n);
        if (sum < *minSum) {
            *minSum = sum;
        }
        return;
    }
    
    for (int i = start; i < n; i++) {
        swap(&nums1[start], &nums1[i]);
        permute(nums1, start + 1, n, nums2, minSum);
        swap(&nums1[start], &nums1[i]);
    }
}

int solution(int* nums1, int* nums2, int n) {
    int minSum = INT_MAX;
    permute(nums1, 0, n, nums2, &minSum);
    return minSum;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple parsing for arrays
    int nums1[100], nums2[100];
    int n1 = 0, n2 = 0;
    
    char* token = strtok(line1, "[,]\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            nums1[n1++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    token = strtok(line2, "[,]\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            nums2[n2++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    int result = solution(nums1, nums2, n1);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Generate n! permutations, each taking O(n) time to calculate product sum

⚠ Quadratic Growth

Space Complexity

O(n!)

Store all n! permutations in memory

⚠ Quadratic Space

34.8K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler