LeetCode Entry

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

13.08.2023 medium 2023 kotlin

Is it possible to partition an array of 2 or 3 equal nums or 3 increasing nums.

2369. Check if There is a Valid Partition For The Array medium blog post substack

image.png

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)
    }