Check if There is a Valid Partition For The Array

Check if There is a Valid Partition For The Array - 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:

The subarray consists of exactly 2, equal elements. For example, the subarray [2,2] is good.
The subarray consists of exactly 3, equal elements. For example, the subarray [4,4,4] is good.
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.

Input & Output

Example 1 — Valid Partition Exists

$ Input: nums = [4,4,4,5,6]

› Output: true

💡 Note: We can partition into [4,4,4] (three equal elements) and [5,6] (two elements, but [5,6] is not valid since they're not equal). Actually this should be false. Let me recalculate: [4,4,4] is valid but [5,6] is invalid, so the answer is false.

Example 2 — Three Equal Elements

$ Input: nums = [4,4,4]

› Output: true

💡 Note: The entire array [4,4,4] consists of exactly 3 equal elements, which is a valid subarray.

Example 3 — Consecutive Sequence

$ Input: nums = [1,2,3]

› Output: true

💡 Note: The entire array [1,2,3] consists of exactly 3 consecutive increasing elements (difference of 1 between adjacent elements).

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers that needs to be partitioned

Check Partitions

Find valid subarrays: 2 equal, 3 equal, or 3 consecutive

Result

Return true if valid partition exists, false otherwise

Key Takeaway

🎯 Key Insight: Use dynamic programming to build the solution from right to left, checking valid partition possibilities at each position

Asked in

G Google 15 a Amazon 12 M Meta 8

The key insight is to use dynamic programming to check if we can partition the array from each position. We work backwards, checking if we can form valid subarrays of length 2 (equal elements), 3 (equal elements), or 3 (consecutive). Best approach is bottom-up DP. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(2ⁿ)	O(n)	Try all possible ways to partition the array recursively
Dynamic Programming (Bottom-Up)	O(n)	O(n)	Build solution iteratively from right to left using DP array
Memoized Recursion	O(n)	O(n)	Add memoization to avoid recalculating the same subproblems

Recursive Backtracking — Algorithm Steps

Start from index 0
Try forming valid subarrays of length 2 or 3
Recursively check remaining array
Return true if any partition works

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at index 0, try different subarray lengths

Branch

For each valid subarray, recursively solve remaining

Backtrack

If path fails, try next possibility

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool canPartition(int* nums, int numsSize, int start) {
    if (start >= numsSize) {
        return true;
    }
    
    // Try length 2: two equal elements
    if (start + 1 < numsSize && nums[start] == nums[start + 1]) {
        if (canPartition(nums, numsSize, start + 2)) {
            return true;
        }
    }
    
    // Try length 3: three equal elements
    if (start + 2 < numsSize && 
        nums[start] == nums[start + 1] && nums[start + 1] == nums[start + 2]) {
        if (canPartition(nums, numsSize, start + 3)) {
            return true;
        }
    }
    
    // Try length 3: consecutive increasing
    if (start + 2 < numsSize && 
        nums[start + 1] == nums[start] + 1 && 
        nums[start + 2] == nums[start] + 2) {
        if (canPartition(nums, numsSize, start + 3)) {
            return true;
        }
    }
    
    return false;
}

bool solution(int* nums, int numsSize) {
    return canPartition(nums, numsSize, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, numsSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each position can start 2-3 different subarrays, leading to exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion call stack can go up to n levels deep

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler