LC-2025 Hard LeetCode

2025. Maximum Number of Ways to Partition an Array

Array Hash Table Counting Enumeration Prefix Sum

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 35% Topics: Array, Hash Table, Counting, Enumeration, Prefix Sum

Reading material

Arrays & Hashing 12 min Backtracking 14 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections


class Solution(object):
    def waysToPartition(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        total = sum(nums)
        right = collections.Counter()
        prefix = 0
        for i in xrange(len(nums)-1):
            prefix += nums[i]
            right[prefix-(total-prefix)] += 1
        result = right[0]
        left = collections.Counter()
        prefix = 0
        for x in nums:
            result = max(result, left[k-x]+right[-(k-x)])
            prefix += x
            left[prefix-(total-prefix)] += 1
            right[prefix-(total-prefix)] -= 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT