Watch the video solution for Minimizing Array After Replacing Pairs With Their Product, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by Programming Live with Larry has 260 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums and an integer k, you can perform the following operation on the array any number of times:
x and y, such that x * y <= k, and replace both of them with a single element with value x * y (e.g. in one operation the array [1, 2, 2, 3] with k = 5 can become [1, 4, 3] or [2, 2, 3], but can't become [1, 2, 6]).Return the minimum possible length of nums after any number of operations.
Example 1:
Input: nums = [2,3,3,7,3,5], k = 20 Output: 3 Explanation: We perform these operations: 1. [2,3,3,7,3,5] -> [6,3,7,3,5] 2. [6,3,7,3,5] -> [18,7,3,5] 3. [18,7,3,5] -> [18,7,15] It can be shown that 3 is the minimum length possible to achieve with the given operation.
Example 2:
Input: nums = [3,3,3,3], k = 6 Output: 4 Explanation: We can't perform any operations since the product of every two adjacent elements is greater than 6. Hence, the answer is 4.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1091 <= k <= 109Problem Overview: You are given an integer array nums and a limit k. You may repeatedly replace two adjacent numbers with their product if the product is ≤ k. After performing operations optimally, return the minimum possible array length.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
Think of the problem as partitioning the array into segments where every segment can collapse into a single value through valid pair multiplications. For each index i, try extending the segment to the right while maintaining a running product ≤ k. If the product remains valid, that segment can reduce to one element. Use DP where dp[i] stores the minimum length achievable starting from index i. This approach systematically checks all valid segment boundaries but becomes expensive because every starting index may scan many elements.
Approach 2: Greedy Product Segmentation (O(n) time, O(1) space)
The key observation: if the running product of a segment ever exceeds k, that segment cannot be merged further. Once that happens, you must start a new segment. Iterate through the array while maintaining a running product. If currentProduct * nums[i] ≤ k, extend the current segment because those values can still collapse into one element. If it exceeds k, finalize the current segment and start a new one from the current element.
Edge case: when nums[i] > k, it can never merge with neighbors. Treat it as a standalone segment and reset the running product. This greedy segmentation works because merging earlier elements never hurts future choices—the only constraint is keeping the product ≤ k.
The algorithm scans the array once, tracking segment boundaries and counting how many final elements remain after all valid merges.
Recommended for interviews: The greedy solution is the expected approach. Brute-force or dynamic programming demonstrates understanding of segment choices, but interviewers typically look for the linear greedy insight. It leverages simple iteration over the array and a running product check, making it both optimal and easy to implement. Conceptually it behaves like forming maximal valid segments using a greedy strategy.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Segment Partition) | O(n²) | O(n) | Useful for reasoning about all possible valid merge segments or when exploring brute-force optimization ideas. |
| Greedy Product Segmentation | O(n) | O(1) | Best choice for interviews and production solutions. Processes the array once while maintaining a running product. |