LeetCode 2871 - Split Array Into Maximum Number of Subarrays

LeetCode Problem 2871

Difficulty: 🟡 Medium
Topics: Array, Greedy, Bit Manipulation

Solution

Problem Understanding

The problem is asking us to split a given array of non-negative integers into contiguous subarrays in a way that maximizes the number of subarrays, while minimizing the sum of their bitwise AND scores. The score of a subarray is defined as the bitwise AND of all elements in that subarray. Since AND-ing any number with 0 results in 0, the minimal possible score for a subarray is 0.

The array must be split such that each element belongs to exactly one subarray. Our goal is not just to minimize the sum of scores but to find the maximum number of subarrays that can achieve this minimal sum.

For example, an array containing zeros allows us to split around them to create more subarrays with AND = 0. If the array has no zeros, we may only be able to split it minimally, resulting in fewer subarrays.

Constraints highlight that nums can be as long as 10^5, so any solution with quadratic or exponential complexity is impractical. All numbers are ≤ 10^6, so bitwise operations are safe and efficient. Important edge cases include arrays with all zeros, arrays with no zeros, and arrays with a single element.

Approaches

The brute-force approach would involve checking all possible subarray partitions, computing their AND scores, and keeping track of those that minimize the sum. This guarantees correctness but is computationally infeasible for large arrays, as the number of partitions grows exponentially (O(2^n)).

The key insight for an optimal approach is recognizing the property of bitwise AND: if you AND a sequence of numbers and the result becomes 0, adding more numbers cannot decrease it further. Therefore, to maximize subarrays with minimal sum, we can greedily split the array whenever the cumulative AND becomes 0. Each time this happens, we can safely close a subarray and start a new one without increasing the sum. This reduces the problem to a single linear pass through the array, updating a running AND accumulator and counting splits whenever it reaches 0.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Generate all subarray partitions and compute AND sums
Optimal (Greedy)	O(n)	O(1)	Use a running AND accumulator and split when it reaches 0

Algorithm Walkthrough

1. Initialize a counter count to 0 to track the number of subarrays.
2. Initialize a variable current_and to ~0 (all bits set) to accumulate the AND of the current subarray.
3. Iterate over each number in the array.
4. Update current_and by AND-ing it with the current number.
5. If current_and becomes 0, increment count and reset current_and to ~0 to start a new subarray.
6. Continue until the end of the array.
7. Return the counter count as the maximum number of subarrays.

Why it works: The greedy invariant is that any sequence of numbers AND-ed together that results in 0 cannot be split further to reduce the sum. Therefore, splitting at each point where the cumulative AND reaches 0 guarantees the minimal score for each subarray and maximizes the number of subarrays.

Python Solution

from typing import List

class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        count = 0
        current_and = (1 << 21) - 1  # Since nums[i] <= 10^6, 21 bits are sufficient
        for num in nums:
            current_and &= num
            if current_and == 0:
                count += 1
                current_and = (1 << 21) - 1
        return count

This solution initializes current_and to all 1s within 21 bits to ensure all numbers in nums are representable. It iterates linearly, updating current_and and incrementing the subarray count whenever the AND reaches 0. After each split, current_and resets to all 1s to start a new subarray.

Go Solution

func maxSubarrays(nums []int) int {
    count := 0
    currentAnd := (1 << 21) - 1  // 21 bits cover numbers up to 10^6
    for _, num := range nums {
        currentAnd &= num
        if currentAnd == 0 {
            count++
            currentAnd = (1 << 21) - 1
        }
    }
    return count
}

The Go implementation mirrors the Python version. Slices are iterated using range, and bitwise operations are performed the same way. Resetting currentAnd after a zero ensures a new subarray can start.

Worked Examples

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

Step	num	current_and	count
1	1	1	0
2	0	0	1
3	2	2	1
4	0	0	2
5	1	1	2
6	2	0	3

Result: 3

Example 2: nums = [5,7,1,3]

Step	num	current_and	count
1	5	5	0
2	7	5	0
3	1	1	0
4	3	1	0

Result: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array of length n, updating a running AND
Space	O(1)	Constant extra space for counters and the current AND accumulator

The linear time complexity is justified because each element is processed exactly once. No additional data structures are needed beyond the scalar variables, so space is constant.

Test Cases

# Provided examples
assert Solution().maxSubarrays([1,0,2,0,1,2]) == 3  # splits around zeros
assert Solution().maxSubarrays([5,7,1,3]) == 1      # cannot split for zero

# Edge cases
assert Solution().maxSubarrays([0,0,0,0]) == 4       # all zeros, max splits
assert Solution().maxSubarrays([1]) == 1            # single element
assert Solution().maxSubarrays([1,2,4,8]) == 1      # no zeros, only 1 subarray
assert Solution().maxSubarrays([1,0,1,0,1,0]) == 3  # alternating zeros

# Large case
assert Solution().maxSubarrays([1]*100000) == 1     # long array with no zeros

Test	Why
[1,0,2,0,1,2]	Validates greedy splits at zeros
[5,7,1,3]	Validates array without zeros remains one subarray
[0,0,0,0]	Checks maximal splits for all zeros
[1]	Handles single element edge case
[1,2,4,8]	Confirms behavior with no zero present
[1,0,1,0,1,0]	Confirms alternating zero splits
[1]*100000	Stress test for large n

Edge Cases

All zeros: If the array is [0,0,0,...], every element is a subarray with AND = 0. The algorithm correctly counts each zero as a separate subarray because current_and becomes 0 immediately and resets each iteration.

No zeros: For arrays like [1,2,3,4], the cumulative AND never reaches 0. The algorithm correctly returns 1 since the entire array forms a single subarray.

Single element: For arrays with one element, whether 0 or non-zero, the algorithm correctly returns 1. If the element is 0, it counts as one subarray. If non-zero, the AND is non-zero, and the split count is still 1.

This greedy approach covers all edge cases while maintaining linear time and constant space, making it robust and efficient for the problem constraints.