We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimizing Array After Replacing Pairs With Their Product

Number: 3177

Difficulty: Medium

Paid? Yes

Companies: Wells Fargo, Adobe

Problem Description

Given an integer array nums and an integer k, you are allowed to perform the following operation any number of times: select two adjacent elements x and y such that x * y <= k, and replace them with a single element equal to x * y. The task is to determine the minimum possible length of the array that can be obtained after performing these operations.

Key Insights

  • The operation is only valid if the product of two adjacent numbers does not exceed k.
  • Merging two numbers reduces the array length by one.
  • The merged result is the product of the merged numbers, and further merging is only possible if this new product, when multiplied by its neighbor, remains <= k.
  • A greedy strategy using a stack can simulate the merge operations optimally: always try to merge the current number with the previous merged segment if allowed.
  • The final number of segments in the stack corresponds to the minimal possible array length after all valid merges.

Space and Time Complexity

Time Complexity: O(n) amortized, where n is the length of the array. Space Complexity: O(n), for the stack used to store intermediate results.

Solution

The idea is to use a stack to simulate the merging process. For each number in the array, attempt to merge it with the number at the top of the stack. If the product of the number on the top of the stack and the current number is <= k, merge them (i.e., multiply them) and update the current number. Continue this process until the top of the stack can no longer be merged with the current number. Finally, push the current (possibly merged) number onto the stack. The number of elements in the stack at the end is the minimum possible length of the array after performing all operations.

Code Solutions

# Python solution
def minimizeArray(nums, k):
    # Initialize an empty stack to simulate the merging process.
    stack = []
    for num in nums:
        # Start with the current number.
        current = num
        # While there is a number on the stack and merging is possible
        while stack and stack[-1] * current <= k:
            # Pop the top element and merge it with current.
            current = stack.pop() * current
        # Push the (merged) number onto the stack.
        stack.append(current)
    # The final stack length is the minimum possible length.
    return len(stack)

# Example usage:
if __name__ == "__main__":
    nums = [2, 3, 3, 7, 3, 5]
    k = 20
    print(minimizeArray(nums, k))  # Expected output: 3
← Back to All Questions