Check if There is a Valid Partition For The Array LeetCode Solution

Problem – Check if There is a Valid Partition For The Array LeetCode Solution

You are given a 0-indexed integer array nums. You have to partition the array into one or more contiguous subarrays.

We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:

  1. The subarray consists of exactly 2 equal elements. For example, the subarray [2,2] is good.
  2. The subarray consists of exactly 3 equal elements. For example, the subarray [4,4,4] is good.
  3. The subarray consists of exactly 3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.

Return true if the array has at least one valid partition. Otherwise, return false.

Example 1:

Input: nums = [4,4,4,5,6]
Output: true
Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6].
This partition is valid, so we return true.

Example 2:

Input: nums = [1,1,1,2]
Output: false
Explanation: There is no valid partition for this array.

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 106

Check if There is a Valid Partition For The Array LeetCode Solution in Java

    public boolean validPartition(int[] A) {
        int n = A.length, dp[] = new int[] {0, 0, 0, 1};
        for (int i = 0; i < n; ++i) {
            dp[i % 4] = 0;
            if (i - 1 >= 0 && A[i] == A[i - 1])
                dp[i % 4] |= dp[(i + 2) % 4];
            if (i - 2 >= 0 && A[i] == A[i - 1] && A[i - 1] == A[i - 2])
                dp[i % 4] |= dp[(i + 1) % 4];
            if (i - 2 >= 0 && A[i] - 1 == A[i - 1] && A[i - 1] == A[i - 2] + 1)
                dp[i % 4] |= dp[(i + 1) % 4];
        }
        return dp[(n - 1) % 4] > 0;
    }

Check if There is a Valid Partition For The Array LeetCode Solution in C++

    bool validPartition(vector<int>& A) {
        int n = A.size(), dp[4] = {0, 0, 0, 1};
        for (int i = 0; i < n; ++i) {
            dp[i % 4] = 0;
            if (i - 1 >= 0 && A[i] == A[i - 1])
                dp[i % 4] |= dp[(i + 2) % 4];
            if (i - 2 >= 0 && A[i] == A[i - 1] && A[i - 1] == A[i - 2])
                dp[i % 4] |= dp[(i + 1) % 4];
            if (i - 2 >= 0 && A[i] - 1 == A[i - 1] && A[i - 1] == A[i - 2] + 1)
                dp[i % 4] |= dp[(i + 1) % 4];
        }
        return dp[(n - 1) % 4];
    }

Check if There is a Valid Partition For The Array LeetCode Solution in Python

    def validPartition(self, A):
        n = len(A)
        dp = [False, False, False, True]
        for i in range(n):
            dp[i % 4] = False
            if i - 1 >= 0 and A[i] == A[i-1]:
                dp[i % 4] |= dp[(i - 2) % 4]
            if i - 2 >= 0 and A[i] == A[i-1] == A[i-2]:
                dp[i % 4] |= dp[(i - 3) % 4]
            if i - 2 >= 0 and A[i] == A[i-1] + 1 == A[i-2] + 2:
                dp[i % 4] |= dp[(i - 3) % 4]
        return dp[(n - 1) % 4]
Check if There is a Valid Partition For The Array LeetCode Solution Review:

In our experience, we suggest you solve this Check if There is a Valid Partition For The Array LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Check if There is a Valid Partition For The Array LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Check if There is a Valid Partition For The Array LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.