Minimizing Array After Replacing Pairs With Their Product

Problem

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 _theminimum possible length of _nums after any number of operations.

Examples

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 <= 10^5
• 0 <= nums[i] <= 10^9
• 1 <= k <= 10^9

Solution

Method 1 – Greedy Dynamic Programming

Intuition

To minimize the array length, we want to merge as many adjacent pairs as possible, but only if their product does not exceed k. This is similar to interval merging, and can be solved using dynamic programming: for each subarray, compute the minimum length after all possible merges.

Approach

1. Use DP where dp[l][r] is the minimum length for subarray nums[l:r+1].
2. For each interval, try all possible splits, and if adjacent elements can be merged (product ≤ k), merge them and update the DP.
3. Use memoization to avoid recomputation.
4. The answer is dp[0][n-1].

Code

C++

class Solution {
public:
    int minimizeArrayLength(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, n));
        for (int i = 0; i < n; ++i) dp[i][i] = 1;
        for (int len = 2; len <= n; ++len) {
            for (int l = 0; l + len - 1 < n; ++l) {
                int r = l + len - 1;
                for (int m = l; m < r; ++m) {
                    dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r]);
                    if (m+1 == r && nums[m] * nums[r] <= k) dp[l][r] = min(dp[l][r], dp[l][m]);
                }
            }
        }
        return dp[0][n-1];
    }
};

Go

func minimizeArrayLength(nums []int, k int) int {
    n := len(nums)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = n
        }
        dp[i][i] = 1
    }
    for l := 2; l <= n; l++ {
        for i := 0; i+l-1 < n; i++ {
            j := i + l - 1
            for m := i; m < j; m++ {
                if m+1 == j && nums[m]*nums[j] <= k {
                    if dp[i][j] > dp[i][m] {
                        dp[i][j] = dp[i][m]
                    }
                } else if dp[i][j] > dp[i][m]+dp[m+1][j] {
                    dp[i][j] = dp[i][m]+dp[m+1][j]
                }
            }
        }
    }
    return dp[0][n-1]
}

Java

class Solution {
    public int minimizeArrayLength(int[] nums, int k) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(dp[i], n);
            dp[i][i] = 1;
        }
        for (int len = 2; len <= n; ++len) {
            for (int l = 0; l + len - 1 < n; ++l) {
                int r = l + len - 1;
                for (int m = l; m < r; ++m) {
                    dp[l][r] = Math.min(dp[l][r], dp[l][m] + dp[m+1][r]);
                    if (m+1 == r && nums[m] * nums[r] <= k) dp[l][r] = Math.min(dp[l][r], dp[l][m]);
                }
            }
        }
        return dp[0][n-1];
    }
}

Kotlin

class Solution {
    fun minimizeArrayLength(nums: IntArray, k: Int): Int {
        val n = nums.size
        val dp = Array(n) { IntArray(n) { n } }
        for (i in 0 until n) dp[i][i] = 1
        for (len in 2..n) {
            for (l in 0..n-len) {
                val r = l + len - 1
                for (m in l until r) {
                    dp[l][r] = minOf(dp[l][r], dp[l][m] + dp[m+1][r])
                    if (m+1 == r && nums[m] * nums[r] <= k) dp[l][r] = minOf(dp[l][r], dp[l][m])
                }
            }
        }
        return dp[0][n-1]
    }
}

Python

def minimize_array_length(nums: list[int], k: int) -> int:
    n = len(nums)
    dp = [[n]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            for m in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j])
                if m+1 == j and nums[m]*nums[j] <= k:
                    dp[i][j] = min(dp[i][j], dp[i][m])
    return dp[0][n-1]

Rust

impl Solution {
    pub fn minimize_array_length(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut dp = vec![vec![n as i32; n]; n];
        for i in 0..n { dp[i][i] = 1; }
        for len in 2..=n {
            for l in 0..=n-len {
                let r = l + len - 1;
                for m in l..r {
                    dp[l][r] = dp[l][r].min(dp[l][m] + dp[m+1][r]);
                    if m+1 == r && (nums[m] * nums[r] <= k) {
                        dp[l][r] = dp[l][r].min(dp[l][m]);
                    }
                }
            }
        }
        dp[0][n-1]
    }
}

TypeScript

class Solution {
    minimizeArrayLength(nums: number[], k: number): number {
        const n = nums.length;
        const dp = Array.from({length: n}, () => Array(n).fill(n));
        for (let i = 0; i < n; ++i) dp[i][i] = 1;
        for (let len = 2; len <= n; ++len) {
            for (let l = 0; l + len - 1 < n; ++l) {
                const r = l + len - 1;
                for (let m = l; m < r; ++m) {
                    dp[l][r] = Math.min(dp[l][r], dp[l][m] + dp[m+1][r]);
                    if (m+1 === r && nums[m] * nums[r] <= k) dp[l][r] = Math.min(dp[l][r], dp[l][m]);
                }
            }
        }
        return dp[0][n-1];
    }
}

Complexity

• ⏰ Time complexity: O(n^3)
  • Triple nested loop for DP.
• 🧺 Space complexity: O(n^2)
  • For DP table.