Check if There is a Valid Partition For The Array

Check if There is a Valid Partition For The Array

What is this problem about?

Given an array of integers, you need to determine if it can be partitioned into one or more valid subarrays. A subarray is valid if it meets one of three conditions:

1. It consists of exactly 2 equal elements (e.g., [2, 2]).
2. It consists of exactly 3 equal elements (e.g., [4, 4, 4]).
3. It consists of exactly 3 consecutive increasing elements (e.g., [3, 4, 5]).

Why is this asked in interviews?

Companies like Coinbase and Google use this to test your understanding of linear Dynamic Programming. It’s a "decision" problem where at each index, you have to decide which rule to apply. It evaluates your ability to break a large problem into overlapping subproblems and your skill in using memoization to avoid exponential time complexity.

Algorithmic pattern used

The pattern is 1D Dynamic Programming. Let dp[i] be a boolean representing whether the prefix of the array ending at index i-1 can be validly partitioned. To calculate dp[i], you check:

• If dp[i-2] is true and the last 2 elements match Rule 1.
• If dp[i-3] is true and the last 3 elements match Rule 2 or Rule 3. Since you only ever look back 3 steps, you can optimize this to $O(1)$ space.

Example explanation

Array: [4, 4, 4, 5, 6]

1. dp[0] = True (empty prefix).
2. dp[2]: Is [4, 4] valid? Yes. dp[2] = dp[0] = True.
3. dp[3]: Is [4, 4, 4] valid? Yes. dp[3] = dp[0] = True.
4. dp[5]: Can we reach here?
   • From dp[2]: Is [4, 5, 6] valid? Yes. dp[5] = True. Result: True.

Common mistakes candidates make

A common error is not checking the bounds correctly when looking back 2 or 3 elements. Another is failing to realize that a single index could be the end of multiple valid partitions (e.g., an index could be the end of a group of 2 AND a group of 3). Candidates also sometimes forget to handle the base cases for very short arrays.

Interview preparation tip

Linear DP problems where you "look back" a fixed number of steps are very common. Practice recognizing when a global property ("can the whole array be partitioned?") can be derived from local properties ("can the last $k$ elements form a valid group?").