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.
We use a variable ans to record the current length of the array, and a variable y to record the current product of the array. Initially, ans = 1 and y = nums[0].
We start traversing from the second element of the array. Let the current element be x:
x = 0, then the product of the entire array is 0 \le k, so the minimum length of the answer array is 1, and we can return directly.x times y \le k, then we can merge x and y, that is, y = x times y.x times y \gt k, then we cannot merge x and y, so we need to treat x as a separate element, that is, ans = ans + 1, and y = x.The final answer is ans.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| 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. |
2892. Minimizing Array After Replacing Pairs With Their Product (Leetcode Medium) • Programming Live with Larry • 260 views views
Practice Minimizing Array After Replacing Pairs With Their Product with our built-in code editor and test cases.
Practice on FleetCode