LeetCode 2321 - Maximum Score Of Spliced Array

The problem presents two integer arrays, nums1 and nums2, of equal length n. You are allowed to select a contiguous subarray from both arrays and swap them exactly once, or choose not to swap at all.

leetcodehardarraydynamic-programming

LeetCode Problem 2321

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem presents two integer arrays, nums1 and nums2, of equal length n. You are allowed to select a contiguous subarray from both arrays and swap them exactly once, or choose not to swap at all. After this optional swap, the score is calculated as the maximum of the sums of the two arrays. Your task is to determine the maximum possible score after considering all valid swaps.

The key insight is that the operation is single-use and only affects a contiguous section. The input constraints indicate that n can be as large as 100,000, so any algorithm iterating over all subarrays naively (O(n^2)) will be too slow. Values in the arrays are all positive, which allows certain optimizations, as the sum of a subarray is always non-negative.

Important edge cases include arrays of length 1, arrays where all elements are equal, or arrays where swapping would decrease the score if done naively. The problem guarantees non-empty arrays and positive integers.

Approaches

Brute-Force Approach

A naive solution would iterate over all possible left and right indices, swap the corresponding subarrays, compute the sums of nums1 and nums2, and record the maximum. This guarantees correctness because it explores all possibilities. However, with n up to 10^5, this results in O(n^2) time complexity, which is infeasible.

Optimal Approach

The key observation is that swapping a subarray from nums1 into nums2 changes the sum of nums1 by the difference between the swapped elements. Specifically, the gain in sum for nums1 if we swap a subarray [i...j] is:

gain = sum(nums2[i..j]) - sum(nums1[i..j])

Thus, the problem reduces to finding a contiguous subarray with the maximum gain. This is a classic maximum subarray sum problem, solvable in O(n) using Kadane's algorithm. Since we can choose to swap either way, we need to calculate the maximum gain for nums1 (by taking nums2 - nums1) and for nums2 (by taking nums1 - nums2) and add it to the original sums.

Comparison of approaches:

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Check all subarrays and compute sums
Optimal O(n) O(1) Use Kadane's algorithm on difference arrays

Algorithm Walkthrough

  1. Compute the sum of nums1 and nums2. Let these be sum1 and sum2.
  2. Create a difference array diff1 = nums2[i] - nums1[i] to represent the gain in nums1 if we swap each element individually.
  3. Use Kadane's algorithm on diff1 to find the maximum subarray sum, representing the best possible gain for nums1 after a swap.
  4. Repeat steps 2-3 for diff2 = nums1[i] - nums2[i] to compute the best gain for nums2.
  5. Calculate max_score1 = sum1 + max_gain1 and max_score2 = sum2 + max_gain2.
  6. Return max(max_score1, max_score2) as the final answer.

Why it works: The algorithm ensures that every possible subarray swap is effectively evaluated using Kadane's algorithm, which guarantees the maximum subarray sum. By considering both arrays as potential gain recipients, it ensures the global maximum score is achieved.

Python Solution

from typing import List

class Solution:
    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
        def max_subarray_gain(diff: List[int]) -> int:
            max_gain = current_gain = 0
            for val in diff:
                current_gain = max(val, current_gain + val)
                max_gain = max(max_gain, current_gain)
            return max_gain

        sum1 = sum(nums1)
        sum2 = sum(nums2)

        diff1 = [b - a for a, b in zip(nums1, nums2)]
        diff2 = [a - b for a, b in zip(nums1, nums2)]

        max_gain1 = max_subarray_gain(diff1)
        max_gain2 = max_subarray_gain(diff2)

        return max(sum1 + max_gain1, sum2 + max_gain2)

This implementation first computes the sums of both arrays. The difference arrays encode the potential gain in swapping. Kadane’s algorithm efficiently finds the subarray producing the maximum gain, which is then added to the original sum to compute the maximum score.

Go Solution

func maximumsSplicedArray(nums1 []int, nums2 []int) int {
    maxSubarrayGain := func(diff []int) int {
        maxGain, currentGain := 0, 0
        for _, val := range diff {
            if currentGain + val > val {
                currentGain += val
            } else {
                currentGain = val
            }
            if currentGain > maxGain {
                maxGain = currentGain
            }
        }
        return maxGain
    }

    sum1, sum2 := 0, 0
    n := len(nums1)
    diff1 := make([]int, n)
    diff2 := make([]int, n)

    for i := 0; i < n; i++ {
        sum1 += nums1[i]
        sum2 += nums2[i]
        diff1[i] = nums2[i] - nums1[i]
        diff2[i] = nums1[i] - nums2[i]
    }

    maxGain1 := maxSubarrayGain(diff1)
    maxGain2 := maxSubarrayGain(diff2)

    if sum1 + maxGain1 > sum2 + maxGain2 {
        return sum1 + maxGain1
    }
    return sum2 + maxGain2
}

Go-specific notes: Slices are used for difference arrays. Kadane’s algorithm is implemented using standard integer variables, and the if statement ensures proper handling of the maximum subarray sum. Overflow is not a concern due to problem constraints.

Worked Examples

Example 1:

nums1 = [60,60,60], nums2 = [10,90,10]

  1. sum1 = 180, sum2 = 110
  2. diff1 = [-50, 30, -50], diff2 = [50, -30, 50]
  3. Max subarray gain for diff1 is 30 (swap index 1), for diff2 is 50 (swap index 0 or 2)
  4. Maximum score: max(180+30, 110+50) = max(210, 160) = 210

Example 2:

nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]

  1. sum1 = 180, sum2 = 180
  2. diff1 = [30,-20,30,-30,-10], diff2 = [-30,20,-30,30,10]
  3. Max subarray gain diff1 = 30+(-20)+30 = 40? Let's compute carefully:

Step-by-step Kadane on diff1: [-30? Wait correct diff1 is nums2-nums1 = [30,-20,30,-30,-10]]

Kadane steps:

current=0, max=0

val=30 => current=30, max=30

val=-20 => current=10, max=30

val=30 => current=40, max=40

val=-30 => current=10, max=40

val=-10 => current=0, max=40

=> max_gain1=40 4. diff2 = nums1-nums2 = [-30,20,-30,30,10], Kadane: max_gain2=40 5. Maximum score: max(180+40,180+40)=220

Complexity Analysis

Measure Complexity Explanation
Time O(n) Compute sums, difference arrays, and Kadane’s algorithm each take O(n)
Space O(n) Difference arrays store n elements each

The algorithm scales linearly with array size, satisfying constraints for n up to 10^5.

Test Cases

# Provided examples
assert Solution().maximumsSplicedArray([60,60,60], [10,90,10]) == 210  # swap index 1
assert Solution().maximumsSplicedArray([20,40,20,70,30], [50,20,50,40,20]) == 220  # swap indices 3-4
assert Solution().maximumsSplicedArray([7,11,13], [1,1,1]) == 31  # no swap

# Edge cases
assert Solution().maximumsSplicedArray([1], [10000]) == 10000  # single element, swap improves score
assert Solution().maximumsSplicedArray([10000], [1]) == 10000  # single