# 13.08.2023 [2369. Check if There is a Valid Partition For The Array]
Is it possible to partition an array of `2` or `3` equal nums or `3` increasing nums.
13.08.2023
2369. Check if There is a Valid Partition For The Array medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/307
Problem TLDR
Is it possible to partition an array of 2
or 3
equal nums or 3
increasing nums.
Intuition
Hint: don’t spend much time trying to write a greedy solution.
We can consider every suffix of an array and make it a subproblem. Given it depends on only of the starting position, it can be safely cached.
Approach
use Depth-First search and a HashMap for cache by position
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun validPartition(nums: IntArray): Boolean {
val cache = mutableMapOf<Int, Boolean>()
fun dfs(pos: Int): Boolean = cache.getOrPut(pos) {
if (pos == nums.size) true
else if (pos + 1 > nums.lastIndex) false
else {
val diff1 = nums[pos + 1] - nums[pos]
if (diff1 == 0 && dfs(pos + 2)) true
else if (pos + 2 > nums.lastIndex) false
else {
val diff2 = nums[pos + 2] - nums[pos + 1]
(diff1 == 0 && diff2 == 0 || diff1 == 1 && diff2 == 1) && dfs(pos + 3)
}
}
}
return dfs(0)
}