2871. Split Array Into Maximum Number of Subarrays

MediumGreedyBit ManipulationArray

Problem Description

In this problem, we are given an array nums containing non-negative integers. We are looking to split the array into one or more subarrays so that two conditions are met:

Each element of the original array should belong to exactly one subarray.
The sum of the bitwise AND scores of these subarrays should be as small as possible.

A subarray is defined as a contiguous part of the original array. The score of a subarray is calculated by taking the bitwise AND of all the elements in that subarray, ranging from nums[l] to nums[r] where l <= r. The goal is to determine the maximum number of subarrays we can obtain from splitting the array while satisfying the above conditions.

Bitwise AND is a binary operation that takes two equal-length binary representations and performs a logical AND operation on each pair of corresponding bits. In this context, for a sequence of non-negative integers, the result of bitwise AND operation is also a non-negative integer. It only returns 1 for a bit position if both corresponding bits of operands are 1, otherwise, it returns 0.

Intuition

To approach this problem, we can utilize a greedy strategy that leverages the property of the bitwise AND operation. With bitwise AND, the score of a subarray can never be greater than the smallest number in the subarray since adding more numbers with bitwise AND operation either keeps the score the same or decreases it. Our aim is to minimize the sum of the scores of the subarrays, and the minimum score for a subarray is 0.

The key insight is to realize that, since we are looking for minimum scores, we should aim to form subarrays whose score is 0 whenever possible. This is because any non-zero score would contribute to the sum, whereas a score of 0 would not.

Given this, the strategy is fairly straightforward:

We start with a score set to -1 because -1 represents a series of all 1s in binary, ensuring when we perform the first bitwise AND operation with any element of the array, the result is the number itself.
We iterate through the array and perform a bitwise AND operation on the current score and the current element to update the score.
If at any point the score becomes 0, we know we can split the subarray at this point and start a new one because we've achieved the minimum possible score for a subarray.
Each time we start a new subarray, we increment our answer (ans) which represents the maximum number of subarrays we can obtain.
The reason we return ans - 1 instead of ans at the end is to account for the initial subarray count we start with at the beginning.

This greedy and bitwise approach efficiently allows us to partition the array to achieve the minimum sum of scores, thus enabling us to find the maximum number of subarrays that fulfill the conditions.

Learn more about Greedy patterns.

Solution Approach

The solution provided follows a simple yet effective method to achieve the objective defined in the problem statement. Here's the walkthrough of the implementation:

We initialize a variable score and set it to -1. The choice of -1 is strategic because, in binary, -1 corresponds to an infinite sequence of 1s. This means that when we take the bitwise AND of -1 with any number, the result is the number itself.
The variable ans is used to maintain the count of subarrays created as part of the solution and is initially set to 1. This represents the first subarray that will include at least the first element of the array.
We then iterate through each number in the nums array, updating the score with the bitwise AND of the current score and the current element. In code, this is score &= num. What this does is it progressively calculates the bitwise AND of the elements of the forming subarray until the score reaches 0.
The if statement within the loop checks if the score is 0. When score becomes 0, we know that we can split the array at that point since we cannot further minimize the score of the current subarray. We do this by resetting the score to -1 and incrementing ans, which is counting the number of subarrays.
Once we've processed all elements in the nums array, we check the value of ans. If ans is 1, it implies that there was no point in the array where the score reached 0, and thus the whole array is a single subarray, and we return 1. Otherwise, we return ans - 1 as during iteration, ans increment also includes the count for the last subarray which might not have been explicitly split in the iteration.

This implementation effectively uses a single pass of the array and does not require any additional data structures, making it very space-efficient. It leverages the bitwise operation to keep track of the ongoing score of the currently considered subarray and to decide when to split into a new subarray, based on the score reaching 0.

Furthermore, the solution is greedy in nature. Greedy algorithms make the optimal choice at each step as they attempt to find the global optimum. In this case, splitting whenever a subarray reaches a score of 0 guarantees the minimum possible sum of scores, thereby aligning with the problem’s requirement to minimize the sum while maximizing the number of subarrays.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with an array nums given as [6, 1, 8, 7, 8] to illustrate the solution approach.

We start by setting score to -1 since this will allow us to bitwise-AND with any number without affecting its value.
We'll also initialize ans to 1, as we start considering the array as one whole subarray first.
Start iterating over nums:
- First element 6: We perform score &= 6, which results in score being 6 as -1 & 6 = 6.
- Second element 1: score &= 1, and now score is 0 because 6 & 1 = 0. Since score is now 0, we increment ans to 2 and reset score to -1.
- Third element 8: score &= 8, resulting in score being 8.
- Fourth element 7: score &= 7, and score remains 0 because 8 & 7 = 0. We increment ans to 3 and reset score to -1.
- Fifth element 8: score &= 8, resulting in score being 8. The loop ends here.
Finally, since we've reached the end of the array, we check our subarray count ans. We have incremented ans two times, so its value is 3. According to our approach, we return ans - 1, which is 3 - 1 = 2.

Our walkthrough of the [6, 1, 8, 7, 8] example demonstrates that the input array can be split into 2 subarrays to minimize the sum of the bitwise AND scores. The subarrays would be [6, 1] and [8, 7, 8]. This example illustrates how the solution approach strategically breaks down the array into subarrays with minimized AND scores.

Solution Implementation

1class Solution:
2    def maxSubarrays(self, nums: List[int]) -> int:
3        # Initialize the current bitwise AND score and the count of maximum subarrays
4        current_and_score, max_subarrays_count = -1, 1
5
6        # Iterate over each number in the nums list
7        for num in nums:
8            # Perform bitwise AND operation with the current number and store the result
9            current_and_score &= num
10
11            # If the current_and_score becomes 0, reset it to -1 and increment subarray count
12            if current_and_score == 0:
13                current_and_score = -1
14                max_subarrays_count += 1
15
16        # If only 1 subarray, return 1, otherwise return one less than the counted subarrays 
17        # because if there's more than one, the first doesn't count (starts with -1, but 0 resets it)
18        return 1 if max_subarrays_count == 1 else max_subarrays_count - 1
19

1class Solution {
2    public int maxSubarrays(int[] nums) {
3        // Initialize score with all bits set (-1 has all bits set in two's complement representation)
4        int score = -1; 
5        // Initialize answer to 1 since we have at least one subarray by default
6        int answer = 1;
7      
8        // Iterate through the array.
9        for (int number : nums) {
10            // Perform bitwise AND operation with each number and store the result in score.
11            score &= number;
12          
13            // If the score becomes 0, increment the answer.
14            // This implies we start a new subarray as per the given logic.
15            if (score == 0) {
16                answer++;
17                // Reset the score to -1 to consider the next subarray.
18                score = -1; 
19            }
20        }
21        // If we only found one subarray, return 1.
22        // Otherwise, subtract 1 from answer because we incremented it one time too many
23        // due to the last iteration possibly setting score to 0.
24        return answer == 1 ? 1 : answer - 1;
25    }
26}
27

1#include <vector>
2
3class Solution {
4public:
5    // Function to calculate the maximum number of subarrays
6    // with non-zero bitwise AND score.
7    int maxSubarrays(vector<int>& nums) {
8        // Initialize the bitwise AND score to -1 since -1 has
9        // all bits set to 1, which will not affect the initial AND operation.
10        int andScore = -1;
11
12        // Initialize the count of subarrays to 1.
13        int subarrayCount = 1;
14
15        // Iterate over each number in the given vector.
16        for (int num : nums) {
17            // Perform bitwise AND operation between the current andScore and the number.
18            andScore &= num;
19
20            // Check if the current andScore has become 0, indicating that
21            // a subarray with non-zero AND score has ended.
22            if (andScore == 0) {
23                // Reset the andScore for a new subarray by setting it
24                // to -1 (all bits set to 1).
25                andScore = -1;
26
27                // Increment the count of subarrays.
28                ++subarrayCount;
29            }
30        }
31
32        // Since the initial count was set to 1, we need to subtract 1 if multiple
33        // subarrays are identified. If only one subarray exists, return 1.
34        return subarrayCount == 1 ? 1 : subarrayCount - 1;
35    }
36};
37

1function maxSubarrays(nums: number[]): number {
2    // Initialize the variable 'answer' to keep the count of maximum subarrays.
3    // Initialize the variable 'score' to keep track of the bitwise AND accumulation.
4    let [answer, score] = [1, -1];
5
6    // Iterate through each number in the nums array
7    for (const num of nums) {
8        // Apply bitwise AND operation between 'score' and 'num'.
9        score &= num;
10
11        // When 'score' becomes 0, reset it to -1 and increment the 'answer'.
12        if (score === 0) {
13            score = -1;
14            answer++;
15        }
16    }
17
18    // If answer is 1, it means we have not found any sequence that resets score
19    // Hence, return 1. Otherwise, return 'answer' minus 1 since we started from 1.
20    return answer === 1 ? 1 : answer - 1;
21}
22

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the array nums. This is because the code iterates through each element of the array exactly once with a single for-loop, performing constant time operations within the loop.

The space complexity of the code is O(1) which implies that the space required by the algorithm does not depend on the size of the input array. The variables score and ans use a fixed amount of space, and no additional data structures are dependent on the input size are used.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know