Skip to main content
Talentd

Maximum Score Using Exactly K Pairs - Solution & Explanation

HardArrayDynamic Programming11 min read
Practice this problem

Problem Statement

You are given two integer arrays nums1 and nums2 of lengths n and m respectively, and an integer k.

You must choose exactly k pairs of indices (i1, j1), (i2, j2), ..., (ik, jk) such that:

  • 0 <= i1 < i2 < ... < ik < n
  • 0 <= j1 < j2 < ... < jk < m

For each chosen pair (i, j), you gain a score of nums1[i] * nums2[j].

The total score is the sum of the products of all selected pairs.

Return an integer representing the maximum achievable total score.

 

Example 1:

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

Output: 22

Explanation:

One optimal choice of index pairs is:

  • (i1, j1) = (1, 0) which scores 3 * 4 = 12
  • (i2, j2) = (2, 1) which scores 2 * 5 = 10

This gives a total score of 12 + 10 = 22.

Example 2:

Input: nums1 = [-2,0,5], nums2 = [-3,4,-1,2], k = 2

Output: 26

Explanation:

One optimal choice of index pairs is:

  • (i1, j1) = (0, 0) which scores -2 * -3 = 6
  • (i2, j2) = (2, 1) which scores 5 * 4 = 20

The total score is 6 + 20 = 26.

Example 3:

Input: nums1 = [-3,-2], nums2 = [1,2], k = 2

Output: -7

Explanation:

The optimal choice of index pairs is:

  • (i1, j1) = (0, 0) which scores -3 * 1 = -3
  • (i2, j2) = (1, 1) which scores -2 * 2 = -4

The total score is -3 + (-4) = -7.

 

Constraints:

  • 1 <= n == nums1.length <= 100
  • 1 <= m == nums2.length <= 100
  • -106 <= nums1[i], nums2[i] <= 106
  • 1 <= k <= min(n, m)

Approach Overview

Problem Overview: You are given an array and must form exactly k disjoint pairs. Each pair contributes a score based on the two selected elements. The goal is to maximize the total score while ensuring every element is used at most once.

Approach 1: Brute Force Pair Enumeration (Exponential Time, O(n^(2k)) time, O(k) space)

The most direct strategy tries every possible way to choose k disjoint pairs. You recursively pick two unused elements, add their score, and continue forming the remaining pairs. This guarantees the optimal answer because every configuration is explored. However, the number of pair combinations grows extremely fast as n increases, making this approach impractical beyond small inputs. It is mainly useful for understanding the search space before optimizing.

Approach 2: Dynamic Programming with Prefix Decisions (O(nĀ² Ā· k) time, O(n Ā· k) space)

The efficient solution uses dynamic programming to avoid recomputing overlapping subproblems. First process the array from left to right and define dp[i][p] as the maximum score achievable using the first i elements while forming exactly p pairs. For each position i, you have two choices: skip the element (carry forward dp[i-1][p]) or pair it with a previous element j. If you pair j and i, add their pair score and transition from dp[j-1][p-1]. Iterating over possible partners ensures all valid pairings are considered while maintaining disjoint usage of elements.

This DP effectively converts an exponential pairing problem into a structured state transition. The outer loop iterates through the array, the inner loop checks potential pairing partners, and the pair count dimension ensures exactly k pairs are formed. Because states reuse previously computed results, the total complexity becomes manageable even for large inputs.

Recommended for interviews: Start by explaining the brute force pairing idea to demonstrate understanding of the constraints and why the search space explodes. Then move to the dynamic programming formulation with dp[i][p]. Interviewers typically expect the DP optimization because it shows you can convert a combinatorial pairing problem into a structured state transition with clear time and space bounds.

Solution

We denote the lengths of arrays nums1 and nums2 as n and m respectively, and denote k in the problem as K.

We define a three-dimensional array f, where f[i][j][k] represents the maximum score of selecting exactly k index pairs from the first i elements of nums1 and the first j elements of nums2. Initially, f[0][0][0] = 0, and all other values of f[i][j][k] are negative infinity.

We can calculate f[i][j][k] through the following state transition equation:

$ f[i][j][k] = max\begin{cases} f[i-1][j][k], \ f[i][j-1][k], \ f[i-1][j-1][k-1] + nums1[i-1] * nums2[j-1] \end{cases}

The first case represents not selecting the i-th element of nums1, the second case represents not selecting the j-th element of nums2, and the third case represents selecting the i-th element of nums1 and the j-th element of nums2 as a pair of indices.

Finally, we need to return f[n][m][K].

The time complexity is O(m times n times K) and the space complexity is O(m times n times K), where n and m are the lengths of arrays nums1 and nums2 respectively, and K is k$ in the problem.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair EnumerationO(n^(2k))O(k)Useful for understanding the search space or validating small test cases
Dynamic Programming (Prefix States)O(n^2 * k)O(n * k)General optimal approach for large arrays and interview settings

Video Solution

Maximum Score Using Exactly K Pairs šŸ”„ LeetCode 3836 | Weekly Contest 488 Q4 | DP + Recursion + Memo ā€¢ Study Placement ā€¢ 391 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Maximum Score Using Exactly K Pairs easy or hard?
Maximum Score Using Exactly K Pairs is categorized as a hard problem because it requires recognizing overlapping subproblems and designing a correct DP state for pair selection. Managing pair counts and avoiding reuse of elements adds additional complexity.
Maximum Score Using Exactly K Pairs Python/Java solution
The implementation uses a 2D DP array where rows represent processed elements and columns represent the number of formed pairs. The same logic works across Python, Java, C++, Go, and TypeScript by iterating through indices and updating dp states based on pairing decisions.
How to solve Maximum Score Using Exactly K Pairs in O(n^2 * k)?
Use a DP table where dp[i][p] stores the best score using the first i elements and exactly p pairs. For each index i, either skip it or pair it with a previous index j and add the pair score to dp[j-1][p-1]. Iterating through possible partners builds the optimal solution incrementally.
What is the best approach for Maximum Score Using Exactly K Pairs?
Dynamic programming is the most effective approach. Define dp[i][p] as the maximum score using the first i elements while forming p pairs. At each step you either skip the current element or pair it with a previous one and update the state. This reduces the exponential pairing search to O(n^2 * k) time.
Is Maximum Score Using Exactly K Pairs asked at Google/Amazon/Meta?
Pair selection and DP optimization problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving pairing elements, maximizing scores, or forming exactly k groups are common dynamic programming patterns.
What data structure is used in Maximum Score Using Exactly K Pairs?
The main structure is a 2D dynamic programming table that stores intermediate results for prefixes of the array and pair counts. The problem primarily combines array traversal with dynamic programming state transitions.
What is the time complexity of Maximum Score Using Exactly K Pairs?
The optimized dynamic programming solution runs in O(n^2 * k) time and uses O(n * k) space. The algorithm iterates through the array and checks potential pairing partners for each element while tracking how many pairs have been formed.

Ready to solve this problem?

Practice Maximum Score Using Exactly K Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays