LeetCode 3652 - Best Time to Buy and Sell Stock using Strategy

Difficulty: 🟡 Medium
Topics: Array, Sliding Window, Prefix Sum

Solution

Problem Understanding

This problem asks us to calculate the maximum possible profit from a stock trading strategy with the option to modify it once in a very specific way. You are given two arrays: prices, which contains the stock price on each day, and strategy, which tells you what action to take each day: -1 for buy, 0 for hold, and 1 for sell. The profit for a strategy is calculated simply as the sum of strategy[i] * prices[i].

You are allowed one modification to the strategy: choose exactly k consecutive days, and transform the first k/2 days to 0 (hold) and the last k/2 days to 1 (sell). Your goal is to find the maximum profit achievable, either with or without this modification.

Key observations from the problem include:

There are no constraints about owning stock before selling or having enough money before buying, so every operation is "feasible" mathematically. This simplifies the problem to a pure array manipulation and sum calculation problem.
k is guaranteed to be even, so splitting it into two halves is always valid.
prices and strategy can be large (up to 10^5), which rules out naive brute-force approaches that iterate over all possible subarrays for modification.

Edge cases include when the modification does not improve the profit at all, or when k equals the length of the array.

Approaches

Brute Force

A brute-force solution would iterate over all possible starting indices for the k-length subarray. For each subarray, we apply the modification, recalculate the total profit, and track the maximum. This works correctly because it exhaustively considers every valid modification, but it is too slow because recalculating profit from scratch for each subarray is O(n), and there are O(n) subarrays. This gives an overall time complexity of O(n^2).

Optimal Approach

The key insight is that we can calculate the delta or improvement in profit for applying the modification to any k-length subarray without recomputing the entire sum each time. For any subarray of length k, the difference between the modified and original profit is:

delta = sum(prices[i] * new_strategy[i] - prices[i] * strategy[i]) for i in subarray

Since the modification sets the first k/2 elements to 0 and the last k/2 elements to 1, this simplifies to:

delta = sum((0 - strategy[i]) * prices[i]) for i in first half
      + sum((1 - strategy[i]) * prices[i]) for i in second half

We can compute delta efficiently for all subarrays of length k using a sliding window approach:

Precompute the initial profit as the sum of strategy[i] * prices[i].
Compute the delta for the first k-length window.
Slide the window forward one element at a time, updating the delta by subtracting the contribution of the element leaving the window and adding the contribution of the element entering the window.
Keep track of the maximum delta encountered.
The maximum achievable profit is initial_profit + max_delta.

This reduces the time complexity to O(n) and space complexity to O(1) extra space, aside from input storage.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Computes profit from scratch for every k-length subarray
Optimal	O(n)	O(1)	Uses sliding window to compute modification delta efficiently

Algorithm Walkthrough

Compute the initial profit as sum(strategy[i] * prices[i]).
Initialize delta to 0 for the first k-length subarray.
For the first k/2 elements in the window, add -strategy[i] * prices[i] to delta.
For the last k/2 elements in the window, add (1 - strategy[i]) * prices[i] to delta.
Set max_delta to this initial delta.
Slide the window forward by one element at a time. For each slide:

Update delta by removing the contribution of the element leaving the window and adding the contribution of the element entering.
Update max_delta if the new delta is larger.

Return initial_profit + max_delta.

Why it works: The algorithm maintains a running delta for the modification across all valid subarrays, guaranteeing that the maximum possible improvement is found. Adding it to the original profit gives the global maximum.

Python Solution

from typing import List

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        initial_profit = sum(p * s for p, s in zip(prices, strategy))
        
        half = k // 2
        # Compute delta for the first window
        delta = 0
        for i in range(half):
            delta += -strategy[i] * prices[i]
        for i in range(half, k):
            delta += (1 - strategy[i]) * prices[i]
        
        max_delta = delta
        
        # Slide the window
        for i in range(1, n - k + 1):
            # Remove leftmost old contributions
            delta -= -strategy[i - 1] * prices[i - 1]
            delta -= (1 - strategy[i + half - 1]) * prices[i + half - 1]
            
            # Add new rightmost contributions
            delta += -strategy[i + half - 1] * prices[i + half - 1]
            delta += (1 - strategy[i + k - 1]) * prices[i + k - 1]
            
            max_delta = max(max_delta, delta)
        
        return initial_profit + max_delta

The Python implementation first calculates the original profit. Then it initializes a delta for the first k-length subarray. Using a sliding window, it efficiently updates delta for all subsequent subarrays. Finally, it returns the maximum achievable profit.

Go Solution

func maxProfit(prices []int, strategy []int, k int) int64 {
    n := len(prices)
    var initialProfit int64
    for i := 0; i < n; i++ {
        initialProfit += int64(prices[i] * strategy[i])
    }

    half := k / 2
    var delta int64
    for i := 0; i < half; i++ {
        delta += int64(-strategy[i] * prices[i])
    }
    for i := half; i < k; i++ {
        delta += int64((1 - strategy[i]) * prices[i])
    }
    
    maxDelta := delta

    for i := 1; i <= n - k; i++ {
        delta -= int64(-strategy[i-1] * prices[i-1])
        delta -= int64((1 - strategy[i+half-1]) * prices[i+half-1])
        delta += int64(-strategy[i+half-1] * prices[i+half-1])
        delta += int64((1 - strategy[i+k-1]) * prices[i+k-1])
        if delta > maxDelta {
            maxDelta = delta
        }
    }
    
    return initialProfit + maxDelta
}

The Go implementation mirrors the Python logic. Care is taken to use int64 for profit calculations to prevent integer overflow. The sliding window technique is applied identically.

Worked Examples

Example 1: prices = [4,2,8], strategy = [-1,0,1], k = 2

Initial profit: (-1*4) + (0*2) + (1*8) = 4

First k-length subarray [4,2]:

First half (0 elements): delta = 0
Second half (element 2): delta += 1 - 0 * 2 = 2
max_delta = 6

Maximum profit = 4 + 6 = 10

Example 2: prices = [5,4,3], strategy = [1,1,0], k = 2

Initial profit: (1*5)+(1*4)+(0*3)=9

Sliding window calculations show no positive delta; max_delta = 0

Maximum profit = 9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Sliding window over n-k+1 subarrays, each update in O(1)
Space	O(1)	Only a few integers for delta and max_delta; input is not counted

The algorithm is efficient for the given constraint of n ≤ 10^5.

Test Cases

# Provided examples
assert Solution().maxProfit([4,2,8], [-1,0,1], 2) == 10  # modification improves profit
assert Solution().maxProfit([5,4,3], [1,1,0], 2) == 9   # no modification needed

# Edge cases
assert Solution().maxProfit([1,1], [-1,1], 2) == 1  # smallest array and k
assert Solution().maxProfit([1,2,3,4