Check if There is a Valid Partition For The Array

Medium

Coinbase

3 views

Topics:

ArraysDynamic Programming

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.

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 <= 10⁵
1 <= nums[i] <= 10⁶

Try coding it in LeetCode

Check if There is a Valid Partition For The Array

Medium

Coinbase

3 views

Topics:

ArraysDynamic Programming

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.

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 <= 10⁵
1 <= nums[i] <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array?
Can the array contain negative integers or zero?
What exactly constitutes a 'valid partition'? Is it a partition into subsequences or subarrays?
If there are multiple valid partitions, do I need to return all of them or just determine if at least one exists?
If no valid partition exists, what should I return?

Brute Force Solution

Approach

The brute force method for this problem is all about exploring every conceivable way to cut up the original list of numbers into smaller pieces. We'll check if any of these arrangements satisfy the puzzle's condition. If we find even one that works, we're done.

Here's how the algorithm would work step-by-step:

Consider the first number in the list. Either it starts a new group on its own, or it's paired with the next number, or it's part of a group of three with the next two numbers.
For each of these possibilities, check if that initial group meets the specific requirement of the puzzle (for instance, that the numbers in the group are all equal or fit a certain pattern).
If the first group is valid, move on to the rest of the list and repeat the same process: consider one number at a time, or pairs of numbers, or groups of three. Again, check if these new groups meet the required condition.
Keep doing this until you've checked all the ways to divide the whole original list into groups. Each time you find an arrangement where every single group is valid, that means you've found a solution.
If, after checking absolutely every single possibility, you haven't found even one arrangement that works, then there is no solution.

Code Implementation

def check_if_there_is_a_valid_partition(numbers):
    def can_partition(start_index):
        if start_index == len(numbers):
            return True

        # Check if we can take one element
        if start_index + 1 <= len(numbers):
            if can_partition(start_index + 1):
                return True

        # Check if we can take two elements
        if start_index + 2 <= len(numbers):
            if numbers[start_index] == numbers[start_index + 1]:
                if can_partition(start_index + 2):
                    return True

        # Check if we can take three elements
        if start_index + 3 <= len(numbers):
            # Check if all three elements are equal
            if numbers[start_index] == numbers[start_index + 1] == numbers[start_index + 2]:
                if can_partition(start_index + 3):
                    return True

            # Check if the three elements are consecutive increasing
            if numbers[start_index + 1] == numbers[start_index] + 1 and \
               numbers[start_index + 2] == numbers[start_index] + 2:
                if can_partition(start_index + 3):
                    return True

        return False

    # Start the recursion from the beginning of the array.
    return can_partition(0)

Big(O) Analysis

Time Complexity

O(3^n) – The brute force approach explores all possible partitions of the array. For each element, we have three choices: form a group of size 1, 2, or 3 (if possible). This leads to a branching factor of 3 at each element, resulting in roughly 3 * 3 * ... * 3 (n times) possibilities to explore. Hence, the time complexity is O(3^n), as we are essentially exploring a ternary tree of depth n in the worst case.

Space Complexity

O(N) – The brute force approach, as described, explores different partition possibilities using recursion. Each recursive call potentially creates a new stack frame to store the state of the exploration, including the current index and the partial solution. In the worst-case scenario, where each number starts a new group of size one, the recursion depth could reach N, where N is the number of elements in the input array. Thus, the maximum space used by the recursion stack would be proportional to N, resulting in O(N) auxiliary space.

Optimal Solution

Approach

We need to figure out if we can split the list into smaller, valid groups. The best way to do this is by working through the list, remembering what we've already figured out, and using that knowledge to avoid repeating work.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
For each number, check if it can be part of a valid group of size two or three based on the rules (equal numbers or consecutive numbers).
Store whether we could form a valid group up to that point. This is important because if we couldn't form a valid group up to a certain number, then any splits that rely on getting to that number won't work either.
Move to the next number and repeat the process, using the stored information to determine if a valid group can be formed.
If you reach the end of the list and can form a valid group, then the list can be split according to the rules.

Code Implementation

def check_if_array_is_partitionable(numbers) -> bool:
    list_length = len(numbers)
    dp_table = [False] * (list_length + 1)
    dp_table[0] = True

    for i in range(1, list_length + 1):
        # Check for a group of size 2
        if i >= 2 and numbers[i - 1] == numbers[i - 2]:
            dp_table[i] = dp_table[i] or dp_table[i - 2]

        # Check for a group of size 3
        if i >= 3 and numbers[i - 1] == numbers[i - 2] == numbers[i - 3]:
            dp_table[i] = dp_table[i] or dp_table[i - 3]

        # Check for a group of size 3, consecutive increasing
        if i >= 3 and numbers[i - 1] == numbers[i - 2] + 1 == numbers[i - 3] + 2:
            # This allows to track if previous valid partitions existed.
            dp_table[i] = dp_table[i] or dp_table[i - 3]

    return dp_table[list_length]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once. In each iteration, it performs a constant amount of work: checking for possible pairs or triplets and updating a boolean value indicating whether a valid partition is possible up to that point. Since the amount of work in each iteration is constant and the number of iterations is directly proportional to n, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm stores whether a valid group can be formed up to each point in the list, effectively creating an auxiliary array or list (often implemented using dynamic programming) to remember intermediate results. The size of this auxiliary data structure directly corresponds to the length of the input list. Therefore, the space used grows linearly with the input size N, where N is the number of elements in the list, to store the validity information for each prefix. This results in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return true if the array is null or empty, as an empty array trivially satisfies the condition of having a valid partition.
Array with a single element	Return false if the array has only one element, as it cannot be partitioned into valid groups of size 2 or 3.
Array with two elements that are equal	Return true if the array has two equal elements, as it forms a valid partition of size 2.
Array with two elements that are not equal	Return false, as it cannot be partitioned into valid groups.
Array with all identical elements	The dynamic programming solution or recursive calls should handle this gracefully and eventually return true if the length is a multiple of 2 or 3.
Array with elements exceeding integer limits, leading to overflow during comparisons.	Use appropriate data types (e.g., long) for intermediate calculations to prevent integer overflow.
Array with negative numbers	The solution should correctly handle negative numbers without any issues, as long as comparisons and sums are performed accurately.
A very large input array that might cause stack overflow with a recursive solution	Prefer a dynamic programming approach over recursion to avoid stack overflow issues for large input sizes.