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:

  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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5

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

Solution

Method 1 - TD DP with Memo

Since elements can satisfy more than one rule, this becomes an optimization problem, making dynamic programming a suitable approach.

The three scenarios to check are:

  1. Two consecutive equal elements
  2. Three consecutive equal elements
  3. Three consecutive increasing elements

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
	public boolean validPartition(int[] nums) {
		return dfs(nums, 0, new Boolean[nums.length]);
	}

	private boolean dfs(int[] nums, int idx, Boolean[] dp) {
		int n = nums.length;
		if (idx == n) {
			return true;
		}

		if(dp[idx] != null) {
			return dp[idx];
		}

		if (idx + 1 < n && nums[idx] == nums[idx+1]) {
			if(dfs(nums, idx+2, dp)) {
				return true;
			}
			if (idx + 2 < n && nums[idx] == nums[idx+2]) {
				if (dfs(nums, idx+3, dp)) {
					return true;
				}
			}

		}

		if (idx + 2 < n && nums[idx] == nums[idx+1] - 1 && nums[idx] == nums[idx+2] - 2) {
			if (dfs(nums, idx + 3, dp)) {
				return true;
			}
		}

		return dp[idx] = false;
	}

}

Complexity

  • ⏰ Time complexity: O(n).
    • Each index is visited at most once due to memoization.
    • For each call, only a constant number of checks (at most 3) are performed.
  • 🧺 Space complexity: O(n)
    • O(n) for the memoization array (dp).
    • O(n) for the recursion stack in the worst case.