algoadvance

Leetcode 3149. Find the Minimum Cost Array Permutation

Problem Statement

You are given two integer arrays of the same length A and B. Your task is to permute array A such that the sum of the product of corresponding elements of A and B is minimized.

To clarify, given:

• Arrays A and B of length n
• The goal is to find a permutation P of A that minimizes the sum Σ(A'[i] * B[i]) for i from 0 to n-1, where A' is the permuted version of A as per permutation P.

Clarifying Questions

Before jumping into the solution, let’s clarify and confirm understanding of the problem:

1. Constraints on Array Elements:
   • What are the possible ranges of elements in arrays A and B? (e.g., positive/negative, upper/lower limits).
2. Constraints on Array Length:
   • What is the range of the length of arrays A and B? (Is it up to 10^5 or more?)
3. Output:
   • Should we return the minimized sum or the permuted array A'?
4. Unique Elements:
   • Are elements in arrays A and B guaranteed to be unique?

For this example, let’s assume:

• Elements in arrays A and B are integers within the range [-10^4, 10^4].
• The length of arrays A and B is up to 10^5.
• We need to return the minimized sum.
• Elements can be repeated in arrays A and B.

Strategy

To minimize the sum Σ(A'[i] * B[i]), the intuition is to pair the smallest numbers from A with the largest numbers from B and vice versa. This works due to the fact that multiplying a large magnitude number with a small magnitude number will yield a smaller product compared to multiplying two large magnitude numbers.

Steps:

1. Sort array A.
2. Sort array B in descending order.
3. Calculate the sum of the products of corresponding elements from the sorted A and sorted B.

Code

Let’s implement this strategy in Java:

import java.util.Arrays;

public class MinimumCostArrayPermutation {
    public static int minCostPermutation(int[] A, int[] B) {
        // Sort array A in ascending order
        Arrays.sort(A);
        
        // Sort array B in descending order
        Arrays.sort(B);
        for (int i = 0; i < B.length / 2; i++) {
            int temp = B[i];
            B[i] = B[B.length - 1 - i];
            B[B.length - 1 - i] = temp;
        }
        
        // Calculate the minimized sum product
        int minSum = 0;
        for (int i = 0; i < A.length; i++) {
            minSum += A[i] * B[i];
        }
        
        return minSum;
    }

    public static void main(String[] args) {
        int[] A = {1, 3, 5};
        int[] B = {2, 4, 6};
        System.out.println(minCostPermutation(A, B));  // Expected output: 32
    }
}

Time Complexity

• Sorting array A takes (O(n \log n)).
• Sorting array B takes (O(n \log n)).
• The rearrangement of B to descending order takes (O(n)).
• Calculating the sum takes (O(n)).

Hence, the total time complexity is: [ O(n \log n) ]

This is efficient for arrays with lengths up to (10^5).

Conclusion

This solution effectively minimizes the sum of product of corresponding elements from arrays A and B by leveraging sorting techniques, ensuring a time complexity of (O(n \log n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?