Skip to content

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

Problem

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: ^97b248

  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

Solve

Recursion check

This is a TLE solution

It share a lot of similarity with 131. Palindrome Partitioning, where I:

  • Preprocess the Partition, to create a function isContiguousSubarrays(x, y) that quickly check any sub arrays start at index x and end at index y from nums array is contiguous. This can be achieve by simulating 3 of the rules
  • After that, a helper recursion is there to partition the array one by one, using try and error burst force process
Time Submitted Status Runtime Memory Language
08/13/2023 15:23 Time Limit Exceeded N/A N/A python3 
class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        last = None
        prev = None
        curr = None
        n = len(nums)
        # This is inclusive
        def isContiguousSubarrays(x, y):
            # enum 0 ==> 2 member; enum  1 == 3 member
            if not (x < y < n):
                return False
            size = y - x - 1
            return contiguousPartition[size][x]

        contiguousPartition = [[],[|],[]]
        for i in nums:
            last = prev
            prev = curr
            curr = i
            if prev is not None:
                type1 = (curr == prev)
                contiguousPartition[0].append(type1)
            if last is not None:
                type2 = (last == curr == prev)
                type3 = (abs(last - prev) == abs(curr - prev) == 1)
                contiguousPartition[1].append(type2 or type3)

        # This sould be inclusive, also, y is not needed and just there for sanity 
        def helper(x, y):
            if (x - 1 == y):
                return True
            if isContiguousSubarrays(x, x + 1):
                if helper(x + 2, y):
                    return True
            if isContiguousSubarrays(x, x + 2):
                if helper(x + 3, y):
                    return True
            return False

        return helper(0, n-1)

Recursion + Caching

  • We only need to cache the helper function, because y not change, so an array storing data base on x is enough.
  • Also, the third rule is True for [1,2,3], but not for [3,2,1]. As it is increasing elements, which I need to modify type3 = (abs(last - prev) == abs(curr - prev) == 1) to pass the test
    1. 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.

This does the job to finish the problem

Time Submitted Status Runtime Memory Language
08/13/2023 15:36 Accepted 1031 ms 84.1 MB python3 
class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        last = None
        prev = None
        curr = None
        n = len(nums)
        # This is inclusive
        def isContiguousSubarrays(x, y):
            # enum 0 ==> 2 member; enum  1 == 3 member
            if not (x < y < n):
                return False
            size = y - x - 1
            return contiguousPartition[size][x]

        contiguousPartition = [[],[|],[]]
        for i in nums:
            last = prev
            prev = curr
            curr = i
            if prev is not None:
                type1 = (curr == prev)
                contiguousPartition[0].append(type1)
            if last is not None:
                type2 = (last == curr == prev)
                type3 = (prev - last == curr - prev == 1)
                contiguousPartition[1].append(type2 or type3)

        cache = [0] * n
        # This sould be inclusive, also, y is not needed and just there for sanity 
        def helper(x, y):
            if (x - 1 == y):
                return True
            if cache[x] != 0:
                return cache[x] > 0

            if isContiguousSubarrays(x, x + 1):
                if helper(x + 2, y):
                    cache[x] = 1
                    return True
            if isContiguousSubarrays(x, x + 2):
                if helper(x + 3, y):
                    cache[x] = 1
                    return True
            cache[x] = -1
            return False

        return helper(0, n-1)

Still, this isn’t ideal, we can do a O(n) loop which is even better base on this formula

isValid[x] = isValid[x-2] && isContiguousSubarrays(x-1, x) 
            || isValid[x-3] && isContiguousSubarrays(x-2, x);

Re-implementation in c : Recursion + Caching

Optimize seem better to use a compile language with a hard type system.

Nothing much to say except I encounter a bug with the implementation, that is:

  • When declare a global variable, if you try to have multiple input from console, the global variable isn’t being reset (keep the last input value).
  • This make my cache isValid and contiguousPartition store last know value and return wrong answer.

There is some debug to be make until I reach above conclusion.

Time Submitted Status Runtime Memory Language
08/13/2023 16:11 Wrong Answer N/A N/A c 
bool contiguousPartition[2][100000] = {0};
int isValid[100000] = {0};
int n;

bool isContiguousSubarrays(int x, int y) {
    if (!((x < y) && (y < n))) return false;
    int size = y - x - 1;
    return contiguousPartition[size][x];
}

bool helper(int x, int  y){
    printf("okay %d, %d", x, y);
    if (x - 1 == y) return true;
    if (isValid[x] != 0) return isValid[x] > 0;

    if (isContiguousSubarrays(x, x + 1))
        if (helper(x + 2, y)) {
            isValid[x] = 1;

            printf("is true\n");
            return true;
        }
    if (isContiguousSubarrays(x, x + 2))
        if (helper(x + 3, y)) {
            isValid[x] = 1;

            printf("is true\n");
            return true;
        }
    isValid[x] = -1;
    printf("is false\n");
    return false;
}

bool validPartition(int* nums, int numsSize){
    int last, prev, curr, indexSize2, indexSize3;
    bool type1, type2, type3;
    n = numsSize;
    last = 0; prev = 0; curr = 0;
    indexSize2 = 0; indexSize3 = 0;
    for (int i= 0; i < numsSize; i ++) {
        last = prev;
        prev = curr;
        curr = nums[i];
        if (prev != 0) {
            type1 = (curr == prev);
            contiguousPartition[0][indexSize2] = type1;
            indexSize2 += 1;
            printf("%d", contiguousPartition[0][indexSize2-1]);
        }
        if (last != 0) {
            type2 = (last == curr && curr == prev);
            type3 = (prev - last == curr - prev && curr - prev == 1);
            contiguousPartition[1][indexSize3] = type2 || type3;
            indexSize3 += 1;
            printf(", %d", contiguousPartition[1][indexSize3-1]);

        }
        printf("\n");
    }

    return helper(0, n-1);
}

By keeping that in mind, I just then initiation inside my main function.

Time Submitted Status Runtime Memory Language
08/13/2023 16:14 Accepted 122 ms 17.4 MB c 
bool contiguousPartition[2][100000] = {0};
int isValid[100000] = {0};
int n;

bool isContiguousSubarrays(int x, int y) {
    if (!((x < y) && (y < n))) return false;
    int size = y - x - 1;
    return contiguousPartition[size][x];
}

bool helper(int x, int  y){
    if (x - 1 == y) return true;
    if (isValid[x] != 0) return isValid[x] > 0;

    if (isContiguousSubarrays(x, x + 1))
        if (helper(x + 2, y)) {
            isValid[x] = 1;
            return true;
        }
    if (isContiguousSubarrays(x, x + 2))
        if (helper(x + 3, y)) {
            isValid[x] = 1;
            return true;
        }
    isValid[x] = -1;
    return false;
}

bool validPartition(int* nums, int numsSize){
    int last, prev, curr, indexSize2, indexSize3;
    bool type1, type2, type3;
    last = 0; prev = 0; curr = 0;
    indexSize2 = 0; indexSize3 = 0;
    n = numsSize;
    for (int i= 0; i < numsSize; i ++) {
        isValid[i] = 0; // <== This is  the initiation needed
        last = prev;
        prev = curr;
        curr = nums[i];
        if (prev != 0) {
            type1 = (curr == prev);
            contiguousPartition[0][indexSize2] = type1;
            indexSize2 += 1;
        }
        if (last != 0) {
            type2 = (last == curr && curr == prev);
            type3 = (prev - last == curr - prev && curr - prev == 1);
            contiguousPartition[1][indexSize3] = type2 || type3;
            indexSize3 += 1;
        }
    }

    return helper(0, n-1);
}

Also, it seem like I the only one who done the problem in c, so there isn’t anything to comparing.

Dynamic programming - c implementation

base on this formula

isValid[x] = isValid[x-2] && isContiguousSubarrays(x-1, x) 
            || isValid[x-3] && isContiguousSubarrays(x-2, x);

We can combine both of isContiguousSubarrays function creation process with isValid in one loop. It is not that much of a jump in time complexity, but we can stop the processing if isValid[i-3] == isValid[i-2] == == isValid[i-1] == false, as the above formula always be false from i and above

Time Submitted Status Runtime Memory Language
08/13/2023 16:51 Accepted 113 ms 14.3 MB c 
bool contiguousPartition[2][100000];
bool isValid[100001];
int n;

bool isContiguousSubarrays(int x, int y) {
    if (!((x < y) && (y < n))) return false;
    int size = y - x - 1;
    return contiguousPartition[size][x];
}

bool validPartition(int* nums, int numsSize){
    int last, prev, curr, indexSize2, indexSize3;
    bool type1, type2, type3;
    last = 0; prev = 0; curr = 0;
    indexSize2 = 0; indexSize3 = 0;
    n = numsSize;
    for (int i= 0; i < numsSize; i ++) {
        last = prev;
        prev = curr;
        curr = nums[i];
        if (prev != 0) {
            type1 = (curr == prev);
            contiguousPartition[0][indexSize2] = type1;
            indexSize2 += 1;
        }
        if (last != 0) {
            type2 = (last == curr && curr == prev);
            type3 = (prev - last == curr - prev && curr - prev == 1);
            contiguousPartition[1][indexSize3] = type2 || type3;
            indexSize3 += 1;
        }


        if (i > 2)
            if (isValid[i-2] == isValid[i-3] 
                && isValid[i-2] == isValid[i-1] 
                && isValid[i-1] == false)
                return false;

        isValid[i] = false;
        if (i > 1)
            isValid[i] = isValid[i] || (isValid[i-2] && isContiguousSubarrays(i-1, i));
        else if (i == 1)
            isValid[i] = isValid[i] || isContiguousSubarrays(i-1, i);

        if (i > 2)
            isValid[i] = isValid[i] || (isValid[i-3] && isContiguousSubarrays(i-2, i));
        else if (i == 2)
            isValid[i] =  isValid[i] || isContiguousSubarrays(i-2, i);
    }

    return isValid[n-1];
}

Even with the most optimize version, c still take too long to finish, it quite weird to see x10 time compare to rust and java needed to finish (is Leetcode overhead function is the problem?)

Time Submitted Status Runtime Memory Language
08/13/2023 18:35 Accepted 101 ms 13.8 MB c 
bool validPartition(int* nums, int numsSize) {
    bool last = false;
    bool prev = false;
    bool curr = false;
    bool type1 = false;
    bool type2 = false;
    for (int i = 0; i < numsSize; i++) {
        bool tmp;

        tmp = false;
        if (i >= 1)
            type1 = nums[i] == nums[i-1];
        if (i >= 2) 
            type2 = (nums[i] == nums[i-1] && nums[i] == nums[i-2])
                    || (nums[i] - nums[i-1] ==  nums[i-1] - nums[i-2]
                        && nums[i] - nums[i-1] == 1);

        if (i == 1)
            tmp = tmp || type1;
        if (i == 2)
            tmp = tmp || type2;
        if (i >= 3) {
            tmp = tmp || (type1 && prev);
            tmp = tmp || (type2 && last);
            if (!tmp && !curr && !prev)
                return false;
        }
        last = prev; prev = curr; curr = tmp;
    }

    return curr;
}

java re-implementation

  • By rewriting all of my code again. I have a new look of my code and and found out that the isContiguousSubarrays function and contiguousPartition array can be remove and we could directly calculate it on the fly
  • Which make the code more compact, but also quite harder to understand how I can come up it it in the first place
class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        boolean[] isValid = new boolean[n];

        int index = 0;
        int last = 0, prev = 0,curr = 0;
        boolean type1 = false, type2 = false;
        for (int i: nums) {
            last = prev; prev = curr; curr = i;
            isValid[index] = false;

            if (index >= 1)
                type1 = curr == prev;
            if (index >= 2) 
                type2 = (curr == prev && curr == last)
                        || (curr - prev == prev - last && curr - prev == 1);

            if (index == 1)
                isValid[index] = isValid[index] || type1;
            if (index == 2)
                isValid[index] = isValid[index] || type2;
            if (index >= 3) {
                isValid[index] = isValid[index] || (type1 && isValid[index-2]);
                isValid[index] = isValid[index] || (type2 && isValid[index-3]);
                if (!isValid[index] && !isValid[index - 1] && !isValid[index -2])
                    return false;
            }
            index++;
        }
        return isValid[n-1];
    }
}

rust reimplementation

  • We also only use 4 most recently value of the isValid cache array, so we could remove the isValid array.
  • It quite nice to use nums.iter().enumerate() which only python have the similarity enumerate(nums) while both java and c does not have. But in the final implementation, we don’t use the value &v anyway.
Time Submitted Status Runtime Memory Language
08/13/2023 18:13 Accepted 15 ms 3.5 MB rust
08/13/2023 18:04 Accepted 13 ms 3.7 MB rust 
impl Solution {
    pub fn valid_partition(nums: Vec<i32>) -> bool {
        let mut last = false;
        let mut prev = false;
        let mut curr = false;
        let mut type1 = false;
        let mut type2 = false;

        for (index, &v) in nums.iter().enumerate() {
            let mut tmp = false;

            if index >= 1 {
                type1 = nums[index] == nums[index-1];
            }
            if index >= 2 {
                type2 = (nums[index] == nums[index-1] && nums[index] == nums[index-2]) 
                     || (nums[index] - nums[index-1] == nums[index-1] - nums[index-2] 
                            && nums[index] - nums[index-1] == 1);
            }

            if index == 1 {
                tmp = tmp || type1;
            }
            if index == 2 {
                tmp = tmp || type2;
            }
            if index >= 3 {
                tmp = tmp || (type1 && prev);
                tmp = tmp || (type2 && last);
                if !tmp && !curr && !prev {
                    return false;
                }
            }
            last = prev;
            prev = curr;
            curr = tmp;
        }
        curr
    }
}
Last update : August 17, 2023
Created : August 16, 2023