Scale Engineer

Check if There is a Valid Partition For The Array

Med
#2157Time: O(2^n), where n is the length of the array. The number of recursive calls can grow exponentially, similar to a Fibonacci sequence, as `T(n) ≈ T(n-2) + T(n-3)`.Space: O(n), where n is the length of the array. This is for the recursion stack depth in the worst case.1 company
Patterns
Dynamic Programming
Data structures
Array
Companies
Coinbase

Prompt

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.

 

Example 1:

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:

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

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 106

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a straightforward recursive method to explore every possible way the array can be partitioned. It checks from the beginning of the array, trying to form valid subarrays of size 2 or 3, and then recursively checks the remainder of the array.

Algorithm

  • Define a recursive function, say solve(index), which returns true if the subarray nums[index...] can be validly partitioned, and false otherwise.
  • The base case for the recursion is when index reaches the end of the array (index == nums.length). This signifies that the entire array has been successfully partitioned, so we return true.
  • If index exceeds the array bounds, it's an invalid state, so we return false.
  • In the recursive step, we explore all valid partitioning choices from the current index:
    • Check for a 2-element partition: If index + 1 < n and nums[index] == nums[index + 1], we can form a valid 2-element subarray. We then recursively call solve(index + 2) to check if the rest of the array can be partitioned. If it can, we've found a valid partition for the whole array.
    • Check for a 3-element partition: If index + 2 < n, we check if nums[index...index+2] forms a valid 3-element subarray (either all equal or consecutive increasing). If it does, we recursively call solve(index + 3). If the recursive call returns true, we've found a solution.
  • If any of the recursive calls return true, the function returns true. Otherwise, after trying all possibilities, it returns false.

Walkthrough

The brute-force recursive approach directly translates the problem statement into a recursive structure. We define a function that attempts to partition the array starting from a given index. This function tries to match the first 2 or 3 elements against the valid partition rules. If a match is found, it recursively calls itself on the rest of the array. This process continues until the entire array is partitioned or all possibilities are exhausted.

The core idea is to check every path. For example, from index i, we can potentially move to i+2 or i+3. This branching leads to an exponential number of paths to explore.

Here is the Java implementation:

class Solution {    public boolean validPartition(int[] nums) {        return solve(0, nums);    }     private boolean solve(int index, int[] nums) {        int n = nums.length;        if (index == n) {            return true;        }         // Condition 1: Subarray of size 2        if (index + 1 < n && nums[index] == nums[index + 1]) {            if (solve(index + 2, nums)) {                return true;            }        }         // Condition 2 & 3: Subarray of size 3        if (index + 2 < n) {            // 3 equal elements            if (nums[index] == nums[index + 1] && nums[index + 1] == nums[index + 2]) {                if (solve(index + 3, nums)) {                    return true;                }            }            // 3 consecutive increasing elements            if (nums[index] + 1 == nums[index + 1] && nums[index + 1] + 1 == nums[index + 2]) {                if (solve(index + 3, nums)) {                    return true;                }            }        }         return false;    }}

Complexity

Time

O(2^n), where n is the length of the array. The number of recursive calls can grow exponentially, similar to a Fibonacci sequence, as `T(n) ≈ T(n-2) + T(n-3)`.

Space

O(n), where n is the length of the array. This is for the recursion stack depth in the worst case.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Follows the problem definition closely.

Cons

  • Extremely inefficient due to a large number of redundant computations for the same subproblems.

  • Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

Solutions

class Solution {private  int n;private  int[] f;private  int[] nums;public  boolean validPartition(int[] nums) {    this.nums = nums;    n = nums.length;    f = new int[n];    Arrays.fill(f, -1);    return dfs(0);  }private  boolean dfs(int i) {    if (i == n) {      return true;    }    if (f[i] != -1) {      return f[i] == 1;    }    boolean res = false;    if (i < n - 1 && nums[i] == nums[i + 1]) {      res = res || dfs(i + 2);    }    if (i < n - 2 && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2]) {      res = res || dfs(i + 3);    }    if (i < n - 2 && nums[i + 1] - nums[i] == 1 &&        nums[i + 2] - nums[i + 1] == 1) {      res = res || dfs(i + 3);    }    f[i] = res ? 1 : 0;    return res;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem