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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if There is a Valid Partition For The Array

Number: 2443

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given a 0-indexed integer array, the goal is to determine whether the array can be partitioned into one or more contiguous subarrays such that each subarray satisfies one of the following conditions:

  • It consists of exactly 2 equal elements.
  • It consists of exactly 3 equal elements.
  • It consists of exactly 3 consecutive increasing elements (i.e., each adjacent pair differs by 1).

Return true if there is at least one valid partition; otherwise, return false.

Key Insights

  • Use dynamic programming to determine if a valid partition exists starting at each index.
  • Explore partitions of size 2 and size 3.
  • For partitions of size 3, check both the condition for equal elements and the condition for consecutive increasing elements.
  • The DP solution builds on whether a valid partition from a subsequent index exists.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) due to the DP array used for storing intermediate results.

Solution

We can solve this problem by using a bottom-up dynamic programming approach. We define dp[i] to be true if the subarray from index i to the end can be partitioned into valid subarrays. The recurrence checks:

  1. If two consecutive elements are equal and dp[i+2] is true.
  2. If three consecutive elements are either all equal or form a strictly increasing sequence (each adjacent difference is 1) and dp[i+3] is true. We initialize dp[n] = true (base case when no elements remain), then iterate backwards from the end to the beginning. Finally, dp[0] indicates if the entire array can be partitioned validly.

Code Solutions

# Define a function to check valid partition
def validPartition(nums):
    n = len(nums)
    # dp[i] will be True if the subarray starting from i can form a valid partition
    dp = [False] * (n + 1)
    dp[n] = True  # Base case: empty subarray is valid

    # Iterate backwards through the list
    for i in range(n - 1, -1, -1):
        # Check for partition of length 2: two equal elements
        if i + 1 < n and nums[i] == nums[i + 1] and dp[i + 2]:
            dp[i] = True
        # Check for partition of length 3: either three equal or three consecutive increasing elements
        if i + 2 < n:
            # Check if three elements are equal
            if nums[i] == nums[i + 1] == nums[i + 2] and dp[i + 3]:
                dp[i] = True
            # Check if three elements are consecutive increasing
            if nums[i + 2] - nums[i + 1] == 1 and nums[i + 1] - nums[i] == 1 and dp[i + 3]:
                dp[i] = True
    return dp[0]

# Example usage:
print(validPartition([4, 4, 4, 5, 6]))  # Expected output: True
print(validPartition([1, 1, 1, 2]))     # Expected output: False
← Back to All Questions