LeetCode 3117 - Minimum Sum of Values by Dividing Array

This problem asks us to partition an array nums into exactly m contiguous subarrays such that the bitwise AND of elements in the i-th subarray equals andValues[i].

leetcodehardarraybinary-searchdynamic-programmingbit-manipulationsegment-treequeue

LeetCode Problem 3117

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Bit Manipulation, Segment Tree, Queue

Solution

Problem Understanding

This problem asks us to partition an array nums into exactly m contiguous subarrays such that the bitwise AND of elements in the i-th subarray equals andValues[i]. Once partitioned, we sum the last elements of each subarray to compute a total value, and the goal is to minimize this sum. If no valid partition exists, we return -1.

In other words, we are looking for contiguous subarrays [li, ri] where the AND of all elements equals the target andValues[i], and among all valid partitions, we want the sum of the last elements to be minimal. This is a constrained partition problem combined with bitwise operations.

The constraints tell us that the input size is moderate for n (1 <= n <= 10^4), but m is very small (m <= 10). The nums[i] values are up to 10^5, so we can work directly with integers without worrying about overflow. The small m suggests a dynamic programming or recursive approach over subarray indices is feasible.

Edge cases include arrays where no subarray satisfies a target AND, arrays of length 1, and arrays where the only possible partitions are single-element subarrays.

Approaches

The brute-force approach would try all possible ways to split nums into m contiguous subarrays and check if each subarray's AND equals the corresponding andValues[i]. For each valid partition, we calculate the sum of the last elements and take the minimum. This approach is correct but exponentially slow because the number of partitions grows combinatorially with n and m. Specifically, for n elements and m splits, the number of partitions is roughly C(n-1, m-1), which is infeasible for n up to 10^4.

The optimal approach leverages dynamic programming with bitwise AND propagation. The key observation is that the AND operation is monotonic: if AND(a, b, c) = x and we extend it with a new number d, the result can only decrease (set more bits to 0). This allows us to try contiguous subarrays in order, updating the current AND and only considering subarrays that satisfy the target AND. Using a DP array dp[i][j] representing the minimal sum using the first i elements to form the first j subarrays allows us to efficiently compute the answer.

Approach Time Complexity Space Complexity Notes
Brute Force O(C(n-1, m-1) * n) O(n) Tries all partitions, infeasible for large n
Dynamic Programming O(n * m * n) worst-case, but pruning reduces it O(n * m) Use DP + bitwise AND monotonicity to prune invalid partitions

Algorithm Walkthrough

  1. Initialize a DP array dp[i][j] where dp[i][j] is the minimum sum to partition nums[0:i] into j subarrays satisfying the AND targets. Fill with infinity initially, except dp[0][0] = 0.
  2. Iterate over the current number of subarrays j from 1 to m.
  3. For each i (end index of the current subarray), try extending backward to find all starting indices k such that nums[k:i] satisfies AND(nums[k:i]) == andValues[j-1].
  4. If a valid subarray is found, update dp[i][j] as min(dp[i][j], dp[k][j-1] + nums[i-1]) because the last element of the subarray contributes to the sum.
  5. After filling the DP table, the answer is dp[n][m] if it is not infinity, otherwise return -1.

Why it works: The DP keeps track of all minimal sums for partitions of increasing subarray count. By checking all backward subarrays using bitwise AND, we ensure that we only consider valid subarrays, and the DP ensures minimal sums are propagated.

Python Solution

from typing import List

class Solution:
    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
        n, m = len(nums), len(andValues)
        INF = float('inf')
        dp = [[INF] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 0

        for j in range(1, m + 1):
            target = andValues[j - 1]
            for i in range(1, n + 1):
                curr_and = nums[i - 1]
                for k in range(i, 0, -1):
                    curr_and &= nums[k - 1]
                    if curr_and < target:
                        break
                    if curr_and == target:
                        dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + nums[i - 1])
        return dp[n][m] if dp[n][m] != INF else -1

The Python solution initializes a 2D DP table, iterates through the number of subarrays, and uses a nested loop to check all valid subarrays ending at each index using backward iteration. The AND propagation is used to prune invalid candidates early.

Go Solution

func minimumValueSum(nums []int, andValues []int) int {
    n, m := len(nums), len(andValues)
    INF := 1 << 60
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
        for j := range dp[i] {
            dp[i][j] = INF
        }
    }
    dp[0][0] = 0

    for j := 1; j <= m; j++ {
        target := andValues[j-1]
        for i := 1; i <= n; i++ {
            currAnd := nums[i-1]
            for k := i; k >= 1; k-- {
                currAnd &= nums[k-1]
                if currAnd < target {
                    break
                }
                if currAnd == target {
                    if dp[k-1][j-1]+nums[i-1] < dp[i][j] {
                        dp[i][j] = dp[k-1][j-1] + nums[i-1]
                    }
                }
            }
        }
    }
    if dp[n][m] == INF {
        return -1
    }
    return dp[n][m]
}

The Go solution mirrors the Python logic. Slices are used for the DP table, and the INF value is represented using a large integer. The backward iteration and bitwise AND pruning is identical.

Worked Examples

Example 1: nums = [1,4,3,3,2], andValues = [0,3,3,2]

i j Subarray checked curr_and dp[i][j]
2 1 [1,4] 0 4
3 2 [3] 3 7
4 3 [3] 3 10
5 4 [2] 2 12

Final answer: 12

Example 2: nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

Optimal partition found: [[2,3,5],[7,7,7],[5]] with sum 5+7+5=17

Example 3: nums = [1,2,3,4], andValues = [2]

No valid partition exists, return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n * m * n) worst-case For each subarray count, check all ending indices and backward subarrays; pruning reduces actual iterations
Space O(n * m) DP table stores minimal sums for each prefix and subarray count

The DP ensures we explore only valid partitions efficiently, and the backward AND propagation helps prune impossible subarrays quickly.

Test Cases

# Provided examples
assert Solution().minimumValueSum([1,4,3,3,2], [0,3,3,2]) == 12
assert Solution().minimumValueSum([2,3,5,7,7,7,5], [0,7,5]) == 17
assert Solution().minimumValueSum([1,2,3,4], [2]) == -1

# Edge cases
assert Solution().minimumValueSum([1], [1]) == 1  # Single element array matches target
assert Solution().minimumValueSum([1], [0]) == -1 # Single element cannot match target 0
assert Solution().minimumValueSum([7,7,7], [7,7,7]) == 21 # All elements match, sum last elements
assert Solution().minimumValueSum([1,2,3], [0