Is Split Array Into Maximum Number of Subarrays easy or hard?

The problem is rated Medium because the implementation is simple but the key insight is non‑obvious. Recognizing that the bitwise AND only decreases and that splitting immediately at zero maximizes segments is the main challenge.

Split Array Into Maximum Number of Subarrays Python/Java solution

The implementation in Python or Java iterates through the array, updates a running AND value, and increments the answer whenever the value becomes zero. After counting the segment, the running value is reset to start forming the next subarray. The logic is identical across Python, Java, C++, and JavaScript with O(n) time complexity.

How to solve Split Array Into Maximum Number of Subarrays in O(n)?

Maintain a running bitwise AND while iterating through the array. Update it with current &= nums[i]. When the value becomes 0, increment the subarray count and reset the running value for the next segment. Because AND operations only reduce bits, splitting immediately at zero ensures the maximum number of subarrays.

What is the best approach for Split Array Into Maximum Number of Subarrays?

The best approach is a greedy scan using cumulative bitwise AND. Traverse the array while maintaining a running AND value. Whenever the value becomes 0, split the subarray and reset the running AND. This produces the maximum number of valid segments in O(n) time and O(1) space.

Is Split Array Into Maximum Number of Subarrays asked at Google/Amazon/Meta?

Problems combining greedy decisions with bit manipulation frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve subarray AND, OR, or XOR behavior are common in coding rounds focused on arrays and bit operations.

What data structure is used in Split Array Into Maximum Number of Subarrays?

The solution mainly uses simple variables while scanning an array. No complex data structures are required. The algorithm relies on bit manipulation operations and a greedy strategy applied during a single array traversal.

What is the time complexity of Split Array Into Maximum Number of Subarrays?

The optimal greedy solution runs in O(n) time because the array is scanned once while maintaining a running AND value. Space complexity is O(1) since only a few variables are used regardless of input size.

Description Hints 3 Solution Video 9:42

2871. Split Array Into Maximum Number of Subarrays

Medium42.4% acceptance

You are given an array nums consisting of non-negative integers.

We define the score of subarray nums[l..r] such that l <= r as nums[l] AND nums[l + 1] AND ... AND nums[r] where AND is the bitwise AND operation.

Consider splitting the array into one or more subarrays such that the following conditions are satisfied:

Each element of the array belongs to exactly one subarray.
The sum of scores of the subarrays is the minimum possible.

Return the maximum number of subarrays in a split that satisfies the conditions above.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,0,2,0,1,2]
Output: 3
Explanation: 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
Explanation: 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 <= 10⁵
0 <= nums[i] <= 10⁶

Topics

Hints open one at a time

Hint 1

The minimum score will always be the bitwise AND of all elements of the array.

Hint 2

If the minimum score is not equal to 0, the only possible split will be to keep all elements in one subarray.

Hint 3

Otherwise, all of the subarrays should have a score of 0, we can greedily split the array while trying to make each subarray as small as possible.

9:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxSubarrays(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,0,2,0,1,2]

Input

[5,7,1,3]

Your code is saved on this device.Solution