#2871

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Split Array Into Maximum Number of Subarrays

Maximize the number of subarrays in an array while ensuring each subarray's bitwise AND meets the minimum score requirement efficiently.

array greedy bit manipulation

Problem Statement

You are given an array nums consisting of non-negative integers. Define the score of any subarray nums[l..r] as nums[l] AND nums[l+1] AND ... AND nums[r], where AND is the bitwise AND operation. Your goal is to split the array into one or more subarrays such that each subarray contributes to achieving the minimum total score possible.

Return the maximum number of subarrays you can create under this condition. For example, given nums = [1,0,2,0,1,2], the optimal split results in three subarrays with a total minimum score, while nums = [5,7,1,3] can only be split into one subarray to achieve the minimum score. Consider how greedy selection and maintaining the AND invariant guide these splits.

Examples

Example 1

Input: nums = [1,0,2,0,1,2]

Output: 3

We can split the array into the following subarrays:

[1,0]. The score of this subarray is 1 AND 0 = 0.
[2,0]. The score of this subarray is 2 AND 0 = 0.
[1,2]. The score of this subarray is 1 AND 2 = 0. The sum of scores is 0 + 0 + 0 = 0, which is the minimum possible score that we can obtain. It can be shown that we cannot split the array into more than 3 subarrays with a total score of 0. So we return 3.

Example 2

Input: nums = [5,7,1,3]

Output: 1

We can split the array into one subarray: [5,7,1,3] with a score of 1, which is the minimum possible score that we can obtain. It can be shown that we cannot split the array into more than 1 subarray with a total score of 1. So we return 1.

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 106

Solution Approach

Compute the Minimum Score

First, calculate the bitwise AND of all elements in nums. This value is the minimum achievable score for any subarray, which serves as the invariant for greedy splitting.

Greedy Splitting with Invariant Validation

Iterate through nums, accumulating a running AND. Whenever the running AND equals the minimum score, finalize the current subarray, increment the subarray count, and reset the running AND. This ensures each subarray satisfies the minimum score constraint.

Maximize Subarray Count Efficiently

Continue scanning the array to maximize the number of valid subarrays. Avoid merging beyond the point where the running AND reaches the minimum score, because combining further would violate the greedy choice principle and reduce the total count.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since we scan the array once and perform constant-time bitwise operations per element. Space complexity is O(1) if only counters and a running AND are maintained, or O(n) if storing all subarrays explicitly.

What Interviewers Usually Probe

Focus on the greedy choice plus invariant validation pattern and its correctness.
Expect clarity on why the bitwise AND of all elements determines the minimum score.
Be ready to discuss failure modes if subarrays are merged incorrectly, reducing the maximum count.

Common Pitfalls or Variants

Common pitfalls

Attempting to split based on zero or any other arbitrary value instead of the computed minimum score.
Resetting the running AND incorrectly, which can merge subarrays violating the invariant.
Overcomplicating with dynamic programming instead of a direct greedy scan, increasing time and space unnecessarily.

Follow-up variants

Maximize subarrays where each subarray's OR equals a target instead of AND.
Split arrays to minimize the sum of squared bitwise AND scores instead of counting subarrays.
Apply the greedy AND invariant method to a circular array scenario for extended pattern practice.

FAQ

What is the minimum score for splitting an array in this problem?

The minimum score is the bitwise AND of all elements in the array, which every subarray must achieve in a valid split.

Can this problem be solved using dynamic programming?

While possible, dynamic programming is inefficient here; the greedy choice with invariant validation achieves optimal O(n) time.

Why do we reset the running AND after reaching the minimum score?

Resetting ensures each new subarray starts fresh, maintaining the invariant and allowing the maximum number of subarrays.

Does the order of elements affect the maximum subarray count?

Yes, since bitwise AND is order-sensitive, the greedy approach respects the original sequence to maintain correct minimum scores.

How does the greedy choice plus invariant validation pattern apply here?

The pattern ensures each subarray satisfies the minimum AND score as we scan, finalizing subarrays at the exact point the invariant is met.

terminal

Solution

Solution 1: Greedy + Bitwise Operation

We initialize a variable $score$ to record the score of the current subarray, and set $score=-1$ initially. Then we traverse the array, for each element $num$, we perform a bitwise AND operation between $score$ and $num$, and assign the result to $score$. If $score=0$, it means the score of the current subarray is 0, so we can split the current subarray and reset $score$ to $-1$. Finally, we return the number of split subarrays.

1

2

3

4

5

6

7

8

9

class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        score, ans = -1, 1
        for num in nums:
            score &= num
            if score == 0:
                score = -1
                ans += 1
        return 1 if ans == 1 else ans - 1

Continue Practicing

#2897 apply operations on array to maximize sum of squares #2835 minimum operations to form subsequence with target sum #3022 minimize or of remaining elements using operations