Minimizing Array After Replacing Pairs With Their Product

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.

For example, in one operation the array [1, 2, 2, 3] with k = 5 can become [1, 4, 3] or [2, 2, 3], but cannot become [1, 2, 6] because 2 * 3 = 6 > 5.

Return the minimum possible length of nums after any number of operations.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,5,4], k = 10

› Output: 3

💡 Note: We can merge 2×3=6 to get [6,5,4]. Cannot merge 6×5=30 > 10 or 5×4=20 > 10. Final length is 3.

Example 2 — Multiple Merges

$ Input: nums = [1,2,2,3], k = 5

› Output: 2

💡 Note: Merge 1×2=2 to get [2,2,3]. Then merge 2×2=4 to get [4,3]. Cannot merge 4×3=12 > 5. Final length is 2.

Example 3 — No Merges Possible

$ Input: nums = [7,8,9], k = 10

› Output: 3

💡 Note: 7×8=56 > 10 and 8×9=72 > 10. No adjacent pairs can be merged. Original length 3 remains.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we can use a greedy approach to merge adjacent elements from left to right when their product is ≤ k. This works because merging earlier elements doesn't prevent optimal merges later. Best approach is greedy left-to-right merging. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Left to Right Merging	O(n)	O(1)	Process array from left to right, greedily merge adjacent elements when possible
Brute Force - Try All Combinations	O(2^n)	O(n)	Recursively try all possible adjacent merges and return minimum length
Memoization - Cache Subproblems	O(2^n)	O(2^n)	Use dynamic programming with memoization to avoid recalculating same subarrays

Greedy - Left to Right Merging — Algorithm Steps

Start from leftmost position
Check if current and next element can merge
If yes, merge them and continue
If no, move to next position

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Left

Begin at leftmost position

Check & Merge

If adjacent pair product <= k, merge them

Continue Right

Move right if can't merge, stay if merged

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int i = 0;
    int currentSize = numsSize;
    
    while (i < currentSize - 1) {
        if ((long long)nums[i] * nums[i + 1] <= k) {
            nums[i] *= nums[i + 1];
            for (int j = i + 1; j < currentSize - 1; j++) {
                nums[j] = nums[j + 1];
            }
            currentSize--;
        } else {
            i++;
        }
    }
    
    return currentSize;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[],");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array, each element processed at most once

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, modifying array in-place

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Left to Right Merging — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler