Leetcode # 2369. Check if There is a Valid Partition For The Array

https://leetcode.com/problems/check-if-there-is-a-valid-partition-for-the-array

Solution

n := len(nums)

Time Complexity: O(3 ** n)O(n) (due to memoization)
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def validPartition(self, nums: List[int]) -> bool:
    @lru_cache(maxsize=len(nums))
    def valid_partition(start=0):
      match (len(nums) - start):
        case 0: return True
        case 1: return False
        case 2: return nums[start] == nums[start + 1]
        case _:
          result1 = result2 = False
          if nums[start] == nums[start + 1]:
            result1 = valid_partition(start + 2)
          if nums[start] == nums[start + 1] == nums[start + 2] \
             or nums[start] == nums[start + 1] - 1 == nums[start + 2] - 2:
            result2 = valid_partition(start + 3)
          return result1 or result2
    return valid_partition(0)

Last Updated on 2023/08/16 by A1go