What is the time complexity of LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product?

The Python solution on this page runs in O(n), where n is the length of the array.

What is the space complexity of LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product?

The Python solution on this page uses O(1) auxiliary space.

Minimizing Array After Replacing Pairs With Their Product — LeetCode 2892 Python Solution

Q: Is LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product a premium problem?

Yes. LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

MediumLeetCode PremiumGreedyArrayDynamic Programming

Problem: #2892
Pattern: Greedy
Reading time: 3 min
Source: leetcode.com

The 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]).

Example

Input: nums = [2,3,3,7,3,5], k = 20
Output: 3
Explanation: We perform these operations:

Python solution

Python

class Solution:
    def minArrayLength(self, nums: List[int], k: int) -> int:
        ans, y = 1, nums[0]
        for x in nums[1:]:
            if x == 0:
                return 1
            if x * y <= k:
                y *= x
            else:
                y = x
                ans += 1
        return ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array
Space	O(1) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product?: LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product is rated Medium on LeetCode.
What is the time complexity of LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product?: The Python solution on this page runs in O(n), where n is the length of the array.
What is the space complexity of LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product cover?: LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product is tagged Greedy, Array and Dynamic Programming on LeetCode.
Is LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product a premium problem?: Yes. LeetCode 2892. Minimizing Array After Replacing Pairs With Their Product is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.