Skip to main content
Talentd

Minimizing Array After Replacing Pairs With Their Product - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic ProgrammingGreedy8 min readAsked at: Adobe
Practice this problem

Problem Statement

Given an integer array nums and an integer k, you can perform the following operation on the array any number of times:

  • Select two adjacent elements of the array like 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 <= 105
  • 0 <= nums[i] <= 109
  • 1 <= k <= 109

Approach Overview

Problem 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.

Solution

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:

  • If 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.
  • If x times y \le k, then we can merge x and y, that is, y = x times y.
  • If 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 SegmentationO(n)O(1)Best choice for interviews and production solutions. Processes the array once while maintaining a running product.

Video Solution

2892. Minimizing Array After Replacing Pairs With Their Product (Leetcode Medium) • Programming Live with Larry • 278 views views

Frequently Asked Questions

Is Minimizing Array After Replacing Pairs With Their Product easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 40%. The challenge is recognizing that the array can be partitioned into maximal segments whose product never exceeds k. Once that greedy insight is identified, the implementation becomes straightforward.
Minimizing Array After Replacing Pairs With Their Product Python/Java solution
Most implementations follow the same greedy pattern: iterate through nums, track a running product, and start a new segment whenever multiplying would exceed k. The logic translates directly across Python, Java, C++, Go, and TypeScript with O(n) time complexity.
How to solve Minimizing Array After Replacing Pairs With Their Product in O(n)?
Scan the array and maintain a running product of the current segment. If currentProduct × nums[i] ≤ k, multiply and continue the segment. If it exceeds k, finalize the current segment and start a new one. Counting how many segments remain gives the minimum possible array length.
What is the best approach for Minimizing Array After Replacing Pairs With Their Product?
The optimal approach is a greedy segmentation strategy. Iterate through the array while maintaining a running product. If multiplying the next element keeps the product ≤ k, continue the segment; otherwise close the segment and start a new one. This runs in O(n) time and O(1) space.
Is Minimizing Array After Replacing Pairs With Their Product asked at Google/Amazon/Meta?
Problems combining greedy segmentation and array product constraints appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test whether candidates recognize when a running product or prefix constraint breaks and requires starting a new segment.
What data structure is used in Minimizing Array After Replacing Pairs With Their Product?
The core solution primarily uses simple array traversal with a few variables to track the running product and segment count. No complex data structures are required. Conceptually it relies on greedy decision-making over the array.
What is the time complexity of Minimizing Array After Replacing Pairs With Their Product?
The optimal greedy solution runs in O(n) time because each element is processed exactly once while maintaining a running product. Space complexity is O(1) since only a few variables are used. A dynamic programming approach can take O(n²) time if every starting index explores multiple segment extensions.

Ready to solve this problem?

Practice Minimizing Array After Replacing Pairs With Their Product with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays