Check if There is a Valid Partition For The Array

Medium
1159.

Check if There is a Valid Partition For The Array

Check if There is a Valid Partition For The Array is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

Cut the integer array nums into one or more contiguous pieces. The partition is valid when every piece is one of:

  1. exactly 2 equal elements, e.g. [4,4];
  2. exactly 3 equal elements, e.g. [4,4,4];
  3. exactly 3 consecutive increasing elements, each one more than the previous, e.g. [3,4,5] (but not [1,3,5]).

Return true if nums has at least one valid partition, and false otherwise.

Example 1

Input
nums = [3,3,5,6,7]
Output
true
Explanation
`[3,3]` and `[5,6,7]`.

Example 2

Input
nums = [7,8,9,9]
Output
false
Explanation
`[7,8,9]` would leave a lone `9`, and `[7,8]` is not a valid piece.

Example 3

Input
nums = [1,1,1,1]
Output
true
Explanation
`[1,1]` and `[1,1]`.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var validPartition = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check if There is a Valid Partition For The Array — Solution

Check if There is a Valid Partition For The Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check if There is a Valid Partition For The Array is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Cut the integer array nums into one or more contiguous pieces. The partition is valid when every piece is one of:

  1. exactly 2 equal elements, e.g. [4,4];
  2. exactly 3 equal elements, e.g. [4,4,4];
  3. exactly 3 consecutive increasing elements, each one more than the previous, e.g. [3,4,5] (but not [1,3,5]).

Return true if nums has at least one valid partition, and false otherwise.

Example 1

Input: nums = [3,3,5,6,7]
Output: true
Explanation: `[3,3]` and `[5,6,7]`.

Example 2

Input: nums = [7,8,9,9]
Output: false
Explanation: `[7,8,9]` would leave a lone `9`, and `[7,8]` is not a valid piece.

Example 3

Input: nums = [1,1,1,1]
Output: true
Explanation: `[1,1]` and `[1,1]`.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

Hints for Check if There is a Valid Partition For The Array

  1. Hint 1

    Greedily taking the first piece that fits can paint you into a corner — [1,1,1,2,3] needs [1,1] first.

  2. Hint 2

    Let dp[i] say whether the first i elements can be partitioned validly.

  3. Hint 3

    dp[i] is true if the last piece is a valid 2-piece and dp[i-2] holds, or a valid 3-piece and dp[i-3] holds.

How to solve Check if There is a Valid Partition For The Array

Every valid partition ends in a piece of length 2 or 3, so whether a prefix can be partitioned depends only on the two or three prefixes just before it — a linear DP.

Approach

  1. Set dp[0] = true (the empty prefix) and compute dp[i] for i = 1..n.
  2. dp[i] is true if i >= 2, nums[i-1] == nums[i-2] and dp[i-2] is true.
  3. It is also true if i >= 3, dp[i-3] is true and the last three are all equal or form x, x+1, x+2.
  4. Return dp[n].

Why it works

Removing the last piece of any valid partition of the first i elements leaves a valid partition of the first i - 2 or i - 3 elements, and conversely appending a valid last piece to a valid partition is valid. So the recurrence captures exactly the partitionable prefixes.

Complexity

  • Time — O(n)
  • Space — O(n), or O(1) keeping only the last three values

Pitfalls

  • A first-fit greedy fails; both piece lengths must be tried.
  • 'Consecutive increasing' means steps of exactly +1 — [1,2,4] or [3,2,1] do not qualify.
  • Four equal elements are two pairs, not one piece.

Reference solution

Python

from typing import List

def validPartition(nums: List[int]) -> bool:
    n = len(nums)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(2, n + 1):
        if dp[i - 2] and nums[i - 1] == nums[i - 2]:
            dp[i] = True
        elif i >= 3 and dp[i - 3]:
            a, b, c = nums[i - 3], nums[i - 2], nums[i - 1]
            if (a == b == c) or (b == a + 1 and c == b + 1):
                dp[i] = True
    return dp[n]

Java

public static boolean validPartition(int[] nums) {
    int n = nums.length;
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 2; i <= n; i++) {
        if (dp[i - 2] && nums[i - 1] == nums[i - 2]) {
            dp[i] = true;
        } else if (i >= 3 && dp[i - 3]) {
            int a = nums[i - 3], b = nums[i - 2], c = nums[i - 1];
            if ((a == b && b == c) || (b == a + 1 && c == b + 1)) dp[i] = true;
        }
    }
    return dp[n];
}

C++

bool validPartition(vector<int>& nums) {
    int n = nums.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 2; i <= n; i++) {
        if (dp[i - 2] && nums[i - 1] == nums[i - 2]) {
            dp[i] = true;
        } else if (i >= 3 && dp[i - 3]) {
            int a = nums[i - 3], b = nums[i - 2], c = nums[i - 1];
            if ((a == b && b == c) || (b == a + 1 && c == b + 1)) dp[i] = true;
        }
    }
    return dp[n];
}

JavaScript

var validPartition = function(nums) {
    var n = nums.length;
    var dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (var i = 2; i <= n; i++) {
        if (dp[i - 2] && nums[i - 1] === nums[i - 2]) {
            dp[i] = true;
        } else if (i >= 3 && dp[i - 3]) {
            var a = nums[i - 3], b = nums[i - 2], c = nums[i - 1];
            if ((a === b && b === c) || (b === a + 1 && c === b + 1)) dp[i] = true;
        }
    }
    return dp[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming