Split Array Into Maximum Number of Subarrays solution and explanation
9 more videos on this problem
2871. Split Array Into Maximum Number of Subarrays 🔥 || Bit Manipulation 👏🏻Ayush Rao · 9:42 · 1K views
2871. Split Array Into Maximum Number of Subarrays | Leetcode Biweekly 114codingMohan · 21:32 · 822 views
Split Array Into Maximum Number of Subarrays| Leetcode 2871 | Bitwise AND | Bi Weekly Contest 114Tech Courses · 14:40 · 572 views
2871. Split Array Into Maximum Number of Subarrays (Leetcode Medium)Programming Live with Larry · 13:18 · 512 views
100019. Split Array Into Maximum Number of Subarrays || Biweekly Contest 114 || LeetcodeAshish Kumar · 17:11 · 397 views
Leetcode 2871 || Split Array Into Maximum Number of Subarrays||Leetcode Weekly Medium || cppKomal Pal · 9:24 · 288 views
【每日一题】LeetCode 2871. Split Array Into Maximum Number of SubarraysHuifeng Guan · 10:45 · 279 views
2871. Split Array Into Maximum Number of Subarrays | LeetCode Biweekly Contest-114 | Fully ExplainedAlgoArtist · 23:57 · 127 views
Leetcode 2871. Split Array Into Maximum Number of SubarraysElite Code · 24:41 · 118 views
Split Array Into Maximum Number of Subarrays : Biweekly Contest 114BitByBit - Learn Coding · 0:20 · 40 views
The problem
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 <= 1050 <= nums[i] <= 106
Approach overview
Problem Overview: You are given an integer array and need to split it into the maximum number of non‑empty subarrays such that the bitwise AND of every subarray equals 0. The goal is to maximize the number of valid splits while scanning the array only once.
Approach 1: Divide at Zero AND Positions (Greedy Scan) (Time: O(n), Space: O(1))
The key observation is that the bitwise AND of numbers can only decrease as you add more elements to a subarray. Once the running AND becomes 0, adding more elements cannot increase it back to a non‑zero value. That means the best strategy is to immediately split the array at that point to maximize the number of segments. Iterate through the array while maintaining a running AND value. Every time the running AND becomes 0, increment the subarray count and reset the running value for the next segment. This greedy strategy guarantees the maximum number of valid subarrays because delaying a split never produces more segments later. The solution runs in linear time and constant space, making it optimal for large inputs. This technique relies on properties of bit manipulation combined with a simple greedy decision at each step.
Approach 2: Running AND Reset Strategy (Without Explicit Zero Counting) (Time: O(n), Space: O(1))
Another way to implement the same idea is to continuously maintain a cumulative AND while iterating through the array. Start with the current value initialized to all bits set (or simply the first element). For every element, update current &= nums[i]. When the value becomes 0, a valid subarray has been formed, so increment the result and reset the running AND to begin evaluating the next segment independently. If the entire traversal never produces a zero AND, the whole array must remain as a single subarray. This approach avoids explicitly tracking positions where zero occurs and instead relies on the natural behavior of cumulative AND operations. It is still an O(n) scan over the array with constant extra memory.
Recommended for interviews: Interviewers expect the greedy running‑AND solution. A brute force approach would check every possible split and compute subarray AND values, which quickly becomes inefficient. Demonstrating the insight that AND values only decrease and that splitting immediately at zero maximizes the segment count shows strong understanding of greedy reasoning and bitwise behavior.
Approach 1: Divide at Zero Positions
The key observation is that any subarray that contains a zero will have a score of zero. Hence, the goal is to maximize the number of subarrays with scores equal to zero by dividing the array at zero positions. The number of zero elements in the array determines the maximum number of subarrays that can be formed with a sum of scores equal to zero.
def max_subarrays(nums):
count = nums.count(0)
return count if count > 0 else 1
nums = [1, 0, 2, 0, 1, 2]
print("Max number of subarrays:", max_subarrays(nums))public class Solution {
public int maxSubarrays(int[] nums) {
int count = 0;
for (int num : nums) {
if (num == 0) {
count++;
}
}
return count > 0 ? count : 1;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] nums = {1, 0, 2, 0, 1, 2};
System.out.println("Max number of subarrays: " + s.maxSubarrays(nums));
}
}#include <vector>
#include <iostream>
int maxSubarrays(std::vector<int>& nums) {
int count = 0;
for (int num : nums) {
if (num == 0) {
count++;
}
}
return count > 0 ? count : 1;
}
int main() {
std::vector<int> nums = {1, 0, 2, 0, 1, 2};
std::cout << "Max number of subarrays: " << maxSubarrays(nums) << std::endl;
return 0;
}function maxSubarrays(nums) {
let count = 0;
nums.forEach(num => {
if (num === 0) {
count++;
}
});
return count > 0 ? count : 1;
}
const nums = [1, 0, 2, 0, 1, 2];
console.log("Max number of subarrays:", maxSubarrays(nums));#include <stdio.h>
int maxSubarrays(int* nums, int numsSize) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 0) {
count++;
}
}
return count > 0 ? count : 1;
}
int main() {
int nums[] = {1, 0, 2, 0, 1, 2};
int length = sizeof(nums) / sizeof(nums[0]);
printf("Max number of subarrays: %d\n", maxSubarrays(nums, length));
return 0;
}using System;
class Solution {
public int MaxSubarrays(int[] nums) {
int count = 0;
foreach (int num in nums) {
if (num == 0) {
count++;
}
}
return count > 0 ? count : 1;
}
static void Main(string[] args) {
int[] nums = {1, 0, 2, 0, 1, 2};
Solution s = new Solution();
Console.WriteLine("Max number of subarrays: " + s.MaxSubarrays(nums));
}
}The Python solution utilizes the built-in count method to count the number of zeros in the list and return it as the result. If no zeros exist, it means we have one non-zero score subarray.
Time Complexity: O(n), where n is the length of the list.
Space Complexity: O(1), due to no extra space usage other than the input.
Approach 2: Alternative Way without Direct Zero Count
In certain cases, especially for educational purposes, you may choose to approach the problem by iterating through the array manually maintaining a running state if the current segment contains a zero or not, indirectly counting subarrays that produce zero scores.
def max_subarrays(nums):
count = 0
found_zero = False
for num in nums:
if num == 0:
if not found_zero:
count += 1
found_zero = True
else:
found_zero = False
return count if count > 0 else 1
nums = [1, 0, 2, 0, 1, 2]
print("Max number of subarrays:", max_subarrays(nums))public class Solution {
public int maxSubarrays(int[] nums) {
int count = 0;
boolean foundZero = false;
for (int num : nums) {
if (num == 0) {
if (!foundZero) {
count++;
foundZero = true;
}
} else {
foundZero = false;
}
}
return count > 0 ? count : 1;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] nums = {1, 0, 2, 0, 1, 2};
System.out.println("Max number of subarrays: " + s.maxSubarrays(nums));
}
}#include <vector>
#include <iostream>
int maxSubarrays(std::vector<int>& nums) {
int count = 0;
bool foundZero = false;
for (int num : nums) {
if (num == 0) {
if (!foundZero) {
count++;
foundZero = true;
}
} else {
foundZero = false;
}
}
return count > 0 ? count : 1;
}
int main() {
std::vector<int> nums = {1, 0, 2, 0, 1, 2};
std::cout << "Max number of subarrays: " << maxSubarrays(nums) << std::endl;
return 0;
}function maxSubarrays(nums) {
let count = 0;
let foundZero = false;
nums.forEach(num => {
if (num === 0) {
if (!foundZero) {
count++;
foundZero = true;
}
} else {
foundZero = false;
}
});
return count > 0 ? count : 1;
}
const nums = [1, 0, 2, 0, 1, 2];
console.log("Max number of subarrays:", maxSubarrays(nums));#include <stdio.h>
int maxSubarrays(int* nums, int numsSize) {
int count = 0;
int foundZero = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 0) {
if (!foundZero) {
count++;
foundZero = 1;
}
} else {
foundZero = 0;
}
}
return count > 0 ? count : 1;
}
int main() {
int nums[] = {1, 0, 2, 0, 1, 2};
int length = sizeof(nums) / sizeof(nums[0]);
printf("Max number of subarrays: %d\n", maxSubarrays(nums, length));
return 0;
}using System;
class Solution {
public int MaxSubarrays(int[] nums) {
int count = 0;
bool foundZero = false;
foreach (int num in nums) {
if (num == 0) {
if (!foundZero) {
count++;
foundZero = true;
}
} else {
foundZero = false;
}
}
return count > 0 ? count : 1;
}
static void Main(string[] args) {
int[] nums = {1, 0, 2, 0, 1, 2};
Solution s = new Solution();
Console.WriteLine("Max number of subarrays: " + s.MaxSubarrays(nums));
}
}In this Python solution, `found_zero` helps manage streaks of zeros, ensuring each contiguous section increments the count only once.
Time Complexity: O(n), as we go through each element.
Space Complexity: O(1), because no additional space is required beyond the initial list size.
Approach 3: 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.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function maxSubarrays(nums: number[]): number {
let [ans, score] = [1, -1];
for (const num of nums) {
score &= num;
if (score === 0) {
--score;
++ans;
}
}
return ans == 1 ? 1 : ans - 1;
}func maxSubarrays(nums []int) int {
ans, score := 1, -1
for _, num := range nums {
score &= num
if score == 0 {
score--
ans++
}
}
if ans == 1 {
return 1
}
return ans - 1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Divide at Zero Positions | Time Complexity: O(n), where n is the length of the list. |
| Alternative Way without Direct Zero Count | Time Complexity: O(n), as we go through each element. |
| Greedy + Bitwise Operation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray AND Checking | O(n²) | O(1) | Useful only for understanding the problem or very small arrays |
| Divide at Zero AND Positions (Greedy) | O(n) | O(1) | Optimal solution for interviews and production constraints |
| Running AND Reset Strategy | O(n) | O(1) | Clean implementation when scanning once and resetting after each valid segment |
Frequently asked questions
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.