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


Problem Description

In this problem, we're given an integer array nums, and our goal is to partition this array into one or more contiguous subarrays. A partition is considered valid if each resulting subarray meets one of three specific conditions:

  1. The subarray consists of exactly 2 equal elements, such as [2, 2].
  2. The subarray consists of exactly 3 equal elements, like [4, 4, 4].
  3. The subarray consists of exactly 3 consecutive increasing elements, which means the difference between adjacent elements is 1. An example of such a subarray is [3, 4, 5].

We need to determine if there's at least one such valid partition for the given array, and we should return true if there is, or false otherwise.

Intuition

The intuition behind the solution is to use Depth First Search (DFS) to explore all possible ways to partition the array. Starting from the beginning of the array, we recursively check if we can form a valid subarray according to the rules given. If we can, we proceed to explore partitions of the remaining part of the array.

Here's the thought process for DFS:

  1. If we reach the end of the array (index i equals the length of the array n), it means we've successfully partitioned the array into valid subarrays, so we return true.

  2. Starting from the current index i, we check if we can form a valid subarray with the next one or two elements based on the given conditions:

    • If the current and the next element are the same, we check the possibility of forming a valid partition with the subsequent elements by calling the DFS for the index i + 2.
    • If the current and the next two elements are the same, we again call the DFS for index i + 3.
    • If the current element and the next two elements form a sequence of three consecutive increasing numbers, we call the DFS for the index i + 3.
  3. We consider a partition valid if any of these subarray conditions lead to a successful partition of the rest of the array.

  4. To optimize the solution, we use memoization (@cache) to avoid re-computing the same state of the array multiple times.

By exploring all possible partitions in a DFS manner and using memoization to reduce duplicate work, we can determine if the array has at least one valid partition in an efficient way.

Solution Approach

The solution uses a recursive Depth First Search (DFS) approach with memoization to avoid redundant computations. In the code, we define a recursive function dfs that attempts to find a valid partition starting from index i. The base case for our recursive function is when i is equal to n, the length of the array, which means we have successfully reached the end of the array with a valid partition and thus return true.

Let's walk through the implementation details:

  • Recursion and DFS: The core of the solution is the recursive function dfs(i) which is called with the starting index i to explore all possible valid subarrays from that index onwards.
  • Memoization: This function is decorated with @cache, which is a feature in Python used for memoization. It stores the results of the function calls with particular arguments so that future calls with the same arguments can return the stored result immediately, without re-executing the whole function.
  • Base Case: When i equals n, we've reached the end and hence return true, implying a successful partition.
  • Recursive Calls:
    • If nums[i] is equal to nums[i + 1], we attempt to create a subarray of length 2 by making a recursive call to dfs(i + 2).
    • If nums[i], nums[i + 1], and nums[i + 2] are equal, we attempt to create a subarray of length 3 by making a recursive call to dfs(i + 3).
    • If nums[i], nums[i + 1], and nums[i + 2] form a sequence of three consecutive increasing numbers, we attempt to create a subarray of length 3 by making a recursive call to dfs(i + 3).
  • Early Termination: The res variable is used to keep track of whether a valid partition has been found. As soon as we find a valid partition, res becomes true and subsequent calls won't be made since the or operator short-circuits.
  • Efficient Checking: To evaluate the conditions, the implementation uses simple if checks and arithmetic comparisons. No additional data structures are required, which keeps the space complexity low.

Finally, dfs(0) is called to initiate the partitioning process starting from the first element of the array, and the result of this call determines whether at least one valid partition exists. If it returns true, the entire array can be partitioned according to the given rules. If not, the array does not have a valid partition configuration.

Example Walkthrough

Let's consider an example nums array to illustrate the solution approach: [3, 3, 2, 2, 1, 1, 2, 3, 4].

Here is a step-by-step walk-through:

  1. Start with index i = 0, attempt to find valid subarrays beginning at that index.
  2. Since nums[0] and nums[1] are equal (3, 3), try to make a subarray [3, 3] and call dfs(2) for the next index.
  3. At index i = 2, nums[2] and nums[3] are also equal (2, 2), so take subarray [2, 2] and call dfs(4) for the next index.
  4. At index i = 4, nums[4] and nums[5] are equal (1, 1), form subarray [1, 1] and call dfs(6) for the next index.
  5. At index i = 6, nums[6], nums[7], and nums[8] form a sequence of three consecutive increasing numbers (2, 3, 4), so take subarray [2, 3, 4] and call dfs(9) for the next index.
  6. Now i = 9 which equals n (the length of nums). According to our base case, we've successfully found a partition for the entire array and return true.

With this walk-through, you can see that the original array can be partitioned into valid subarrays [3, 3], [2, 2], [1, 1], and [2, 3, 4] conforming to the given rules. The DFS approach systematically checks for each subarray possibility at every index, and the use of memoization ensures that we do not perform redundant calculations, leading to an efficient solution.

Python Solution

1from typing import List
2from functools import lru_cache
3
4class Solution:
5    def validPartition(self, nums: List[int]) -> bool:
6        # Calculate the length of the nums list.
7        length_of_nums = len(nums)
8      
9        # Define the depth-first search function with memoization.
10        @lru_cache(maxsize=None)
11        def dfs(index):
12            # Base case: if the whole array has been checked, return True
13            if index == length_of_nums:
14                return True
15          
16            # Initialize the result as False.
17            res = False
18
19            # Check if the current and next items are the same and recurse for the remaining array.
20            if index < length_of_nums - 1 and nums[index] == nums[index + 1]:
21                res = res or dfs(index + 2)
22              
23            # Check for three consecutive elements with the same value and recurse.
24            if index < length_of_nums - 2 and nums[index] == nums[index + 1] == nums[index + 2]:
25                res = res or dfs(index + 3)
26              
27            # Check for a sequence of three consecutive increasing numbers and recurse.
28            if index < length_of_nums - 2 and nums[index + 1] - nums[index] == 1 and nums[index + 2] - nums[index + 1] == 1:
29                res = res or dfs(index + 3)
30          
31            # Return the result.
32            return res
33      
34        # Call the dfs function starting from index 0.
35        return dfs(0)
36

Java Solution

1import java.util.Arrays; // Import necessary for Arrays.fill
2
3class Solution {
4    // Class-wide variables to hold the state of the problem.
5    private int arrayLength;
6    private int[] memo;
7    private int[] numbers;
8
9    // The function to be called to check if a valid partition exists.
10    public boolean validPartition(int[] nums) {
11        this.numbers = nums;
12        arrayLength = nums.length;
13        memo = new int[arrayLength]; // memo array for memoization to avoid re-computation.
14        Arrays.fill(memo, -1); // Initialize all elements of memo to -1.
15        return dfs(0); // Start the depth-first search from the first element.
16    }
17
18    // Helper method to perform depth-first search and check for a valid partition.
19    private boolean dfs(int index) {
20        if (index == arrayLength) { // Base case: if we've reached the end of the array, return true.
21            return true;
22        }
23        if (memo[index] != -1) { // If we have a memoized result, return it.
24            return memo[index] == 1;
25        }
26
27        boolean result = false; // Initialize the result as false initially.
28
29        // Check if the current and next elements are the same, which forms a valid partition of two elements.
30        if (index < arrayLength - 1 && numbers[index] == numbers[index + 1]) {
31            result = result || dfs(index + 2); // Recursively check the partition from the next index.
32        }
33
34        // Check if three consecutive elements are identical, which forms a valid partition.
35        if (index < arrayLength - 2 && numbers[index] == numbers[index + 1] && numbers[index + 1] == numbers[index + 2]) {
36            result = result || dfs(index + 3); // Recursively check the partition from the next index.
37        }
38
39        // Check if three consecutive elements form a contiguous sequence, which is also a valid partition.
40        if (index < arrayLength - 2 && numbers[index + 1] - numbers[index] == 1 && numbers[index + 2] - numbers[index + 1] == 1) {
41            result = result || dfs(index + 3); // Recursively check the partition from the next index.
42        }
43
44        memo[index] = result ? 1 : 0; // Memoize the result for the current index.
45        return result; // Return the result of the current recursion.
46    }
47}
48

C++ Solution

1class Solution {
2public:
3    vector<int> memo; // memoization table to store intermediate results
4    vector<int> numbers; // reference to the input array
5    int size; // size of the input array
6
7    // Main function to check if the given vector can be partitioned according to the rules
8    bool validPartition(vector<int>& nums) {
9        size = nums.size();
10        numbers = nums;
11        memo.assign(size, -1); // initialize memoization table with -1, indicating uncomputed states
12        return dfs(0); // start the recursion from the first element
13    }
14
15    // Helper function using Depth-First Search and memoization to find if valid partition exists
16    bool dfs(int index) {
17        // Base case: If we have reached the end, the partition is valid
18        if (index == size) return true;
19      
20        // If this state has been computed before, return its result
21        if (memo[index] != -1) return memo[index] == 1;
22      
23        // Initialize the validity of the current position's partition as false
24        bool isValidPartition = false;
25      
26        // Check for two consecutive numbers with the same value
27        if (index < size - 1 && numbers[index] == numbers[index + 1])
28            isValidPartition = isValidPartition || dfs(index + 2);
29      
30        // Check for three consecutive numbers with the same value
31        if (index < size - 2 && numbers[index] == numbers[index + 1] && numbers[index + 1] == numbers[index + 2])
32            isValidPartition = isValidPartition || dfs(index + 3);
33      
34        // Check for three consecutive numbers forming a strict increasing sequence by 1
35        if (index < size - 2 && numbers[index + 1] - numbers[index] == 1 && numbers[index + 2] - numbers[index + 1] == 1)
36            isValidPartition = isValidPartition || dfs(index + 3);
37      
38        // Store the result in memoization table before returning
39        memo[index] = isValidPartition ? 1 : 0;
40      
41        return isValidPartition;
42    }
43};
44

Typescript Solution

1function validPartition(nums: number[]): boolean {
2    const length = nums.length;
3    const visited = new Array(length).fill(false); // This keeps track of visited indices to prevent reprocessing.
4    const queue: number[] = [0]; // Queue for breadth-first search, starting with the first index.
5
6    // Process the queue until it's empty.
7    while (queue.length > 0) {
8        const currentIndex = queue.shift()!; // Safely extract an element since queue is non-empty.
9
10        // If we've reached the end of the array, return true.
11        if (currentIndex === length) {
12            return true;
13        }
14
15        // Condition to check if a partition of two identical numbers is possible
16        if (!visited[currentIndex + 2] && currentIndex + 2 <= length && nums[currentIndex] === nums[currentIndex + 1]) {
17            queue.push(currentIndex + 2); // Add next index to the queue.
18            visited[currentIndex + 2] = true; // Mark this index as visited.
19        }
20
21        // Condition to check if a partition of three consecutive numbers (either identical or increasing) is possible
22        if (
23            !visited[currentIndex + 3] &&
24            currentIndex + 3 <= length &&
25            ((nums[currentIndex] === nums[currentIndex + 1] && nums[currentIndex + 1] === nums[currentIndex + 2]) ||
26                (nums[currentIndex] === nums[currentIndex + 1] - 1 && nums[currentIndex + 1] === nums[currentIndex + 2] - 1))
27        ) {
28            queue.push(currentIndex + 3); // Add next index to the queue.
29            visited[currentIndex + 3] = true; // Mark this index as visited.
30        }
31    }
32
33    // If the loop completes without returning true, there is no valid partition.
34    return false;
35}
36

Time and Space Complexity

The given code defines a recursive function dfs that uses memoization to return whether a valid partition exists starting from the i-th index of the array nums. The function recursively tries to partition the array into groups of two or three adjacent elements, either with the same value or forming a consecutive increasing sequence.

Time Complexity:

The time complexity of the dfs function primarily depends on the number of subproblems it needs to solve, which is directly related to the length of nums (n). Due to memoization (through the use of the @cache decorator), each subproblem (each starting index of the array) is solved only once. There are n possible starting indices.

For each index, there are at most three recursive calls to check for three different partitioning conditions. However, these recursive calls don't multiply the complexity because memoization ensures that we do not recompute results for the same inputs.

Therefore, the time complexity of the algorithm is O(n), as each index is processed a constant number of times.

Space Complexity:

The space complexity consists of the memory used for the memoization cache and the stack space used by the recursive calls.

  1. Memoization cache: The cache will store results for each index of the array, leading to a space complexity of O(n) for the memoization cache.

  2. Recursive stack: In the worst case, the function might end up calling itself recursively n/2 times if the partition consists entirely of pairs of identical numbers ([1, 1, 2, 2, ..., n/2, n/2]). This would lead to a stack depth of n/2. Hence, the worst-case space complexity for the call stack is O(n).

Considering both the memoization cache and the recursive call stack, the overall space complexity is also O(n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫