Number Of Great Partitions - Leetcode Solution

Number of Great Partitions is a problem on LeetCode which requires the count of such partitions of an array that satisfy the given conditions.

Problem statement

Given an array of positive integers nums, and a threshold value target. You can split the array into multiple subarrays such that each subarray sums to at least target. The minimum number of subarrays you need to make to split the array is called the great partitioning.

Return the number of ways you can partition the array into great subarrays.

Example:

Input: nums = [2,3,5,10,6], target = 5 Output: 3 Explanation: There are three ways to form great subarrays. [2,3], [5], [10,6] [2,3], [5, 10], [6] [2,3,5], [10], [6]

Solution

Approach: Dynamic Programming

Let's define dp[i] as the number of great subarrays of the suffix nums[i: ].

The base case would be for i = N where N is length(nums), and in this case, the answer is zero.

For the general case (i < N), dp[i] would be the sum of values dp[j] (i < j < N) such that nums[i:j] sums to at least target.

The reason we take the sum of the values dp[j]'s is that all of them will create valid partitions when appended with the suffix nums[i: ].

We can memoize the values using a dictionary.

Let's look at the code implementation:

class Solution: def init(self): self.memo = {}

def numsSumsToTarget(self, nums, target):
    N = len(nums)
    dp = [0] * (N+1)
    for i in range(N-1, -1, -1):
        if nums[i] >= target:
            dp[i] = 1 + dp[i+1]
        else:
            s = 0
            for j in range(i+1, N+1):
                s += nums[j-1]
                if s >= target:
                    dp[i] = max(dp[i], 1 + dp[j])
    return dp[0]

def countGreatPartitions(self, nums, target):
    N = len(nums)
    for i in range(N):
        self.memo[i] = {}
    def dp(i):
        if i == N:
            return 0
        if i in self.memo:
            return self.memo[i]
        res = 0
        for j in range(i+1, N):
            if sum(nums[i:j]) >= target:
                res += dp(j)
        self.memo[i] = res
        return res
    return dp(0)

def numOfGreatPartitions(self, nums, target):
    N = len(nums)
    numsSum = self.numsSumsToTarget(nums, target)
    greatPartitions = self.countGreatPartitions(nums, target)
    return greatPartitions

Explanation:

We define two helper functions.

numsSumsToTarget: This function will find the minimum number of subarrays required to make great partitions for the prefix nums[:i], i.e., it calculates dp[i] for i < N. We implement it using DP, and it returns the value of dp[0].

countGreatPartitions: This function calculates the number of great partitions for the suffix nums[i: ], i.e., it calculates dp[i] for i < N. We implement it using DP and memoization. For each i, we memoize the result so that we can avoid computing it again.

numOfGreatPartitions: This function simply calls the above two helper functions and returns the total number of great partitions.

Time Complexity:

The time complexity of this approach is O(N^2) because we have to calculate dp[i] for i < N twice. We can optimize this by adding another memo for dp[i] in the countGreatPartitions function which bypasses the second call to dp(i).

Space Complexity:

The space complexity of this approach is O(N^2) because we are memoizing dp[i] for i < N.

Summary:

In this problem, we saw how to compute great partitions for an array of positive integers. We used dynamic programming and memoization to solve this problem and achieve a time complexity of O(N^2).

1