Skip to main content
Talentd

Split Array Into Maximum Number of Subarrays - Solution & Explanation

MediumArrayGreedyBit Manipulation16 min read
Practice this problem

Problem Statement

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 <= 105
  • 0 <= 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.

This C solution iterates through the array and counts the number of zeros. Since subarrays are split at positions where zeros occur, the number of zeros directly corresponds to the maximum number of subarrays with zero scores. If no zeros are found, the whole array is one subarray.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array
Space Complexity: O(1) because we use a constant amount of extra space.

Try this approach in the editor →

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.

This C solution involves checking when a new zero streak starts by marking the start with a boolean flag `foundZero`. This is checked each time a zero is encountered, and increments a counter only once per streak.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) due to use of constant space regardless of input size.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Divide at Zero Positions

Time Complexity: O(n), where n is the number of elements in the array
Space Complexity: O(1) because we use a constant amount of extra space.

Alternative Way without Direct Zero Count

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) due to use of constant space regardless of input size.

Greedy + Bitwise Operation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray AND CheckingO(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 StrategyO(n)O(1)Clean implementation when scanning once and resetting after each valid segment

Video Solution

2871. Split Array Into Maximum Number of Subarrays 🔥 || Bit Manipulation 👏🏻 • Ayush Rao • 1,375 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Split Array Into Maximum Number of Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays