Skip to main content
Talentd

Best Time to Buy and Sell Stock using Strategy - Solution & Explanation

MediumArraySliding WindowPrefix Sum12 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

You are given two integer arrays prices and strategy, where:

  • prices[i] is the price of a given stock on the ith day.
  • strategy[i] represents a trading action on the ith day, where:
    • -1 indicates buying one unit of the stock.
    • 0 indicates holding the stock.
    • 1 indicates selling one unit of the stock.

You are also given an even integer k, and may perform at most one modification to strategy. A modification consists of:

  • Selecting exactly k consecutive elements in strategy.
  • Set the first k / 2 elements to 0 (hold).
  • Set the last k / 2 elements to 1 (sell).

The profit is defined as the sum of strategy[i] * prices[i] across all days.

Return the maximum possible profit you can achieve.

Note: There are no constraints on budget or stock ownership, so all buy and sell operations are feasible regardless of past actions.

 

Example 1:

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

Output: 10

Explanation:

Modification Strategy Profit Calculation Profit
Original [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4
Modify [0, 1] [0, 1, 1] (0 × 4) + (1 × 2) + (1 × 8) = 0 + 2 + 8 10
Modify [1, 2] [-1, 0, 1] (-1 × 4) + (0 × 2) + (1 × 8) = -4 + 0 + 8 4

Thus, the maximum possible profit is 10, which is achieved by modifying the subarray [0, 1]ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹.

Example 2:

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

Output: 9

Explanation:

Modification Strategy Profit Calculation Profit
Original [1, 1, 0] (1 × 5) + (1 × 4) + (0 × 3) = 5 + 4 + 0 9
Modify [0, 1] [0, 1, 0] (0 × 5) + (1 × 4) + (0 × 3) = 0 + 4 + 0 4
Modify [1, 2] [1, 0, 1] (1 × 5) + (0 × 4) + (1 × 3) = 5 + 0 + 3 8

Thus, the maximum possible profit is 9, which is achieved without any modification.

 

Constraints:

  • 2 <= prices.length == strategy.length <= 105
  • 1 <= prices[i] <= 105
  • -1 <= strategy[i] <= 1
  • 2 <= k <= prices.length
  • k is even

Approach Overview

Problem Overview: You are given stock prices and a strategy-derived gain sequence. The task is to determine the best buy and sell window that maximizes total profit. Conceptually, this reduces to finding the maximum profit segment over an array of gains.

Approach 1: Prefix Sum + Enumeration (O(n) time, O(n) space)

Convert the strategy impact into a profit array where each element represents the gain or loss contributed on that day. Build a prefix sum array so the profit of any interval [l, r] can be computed in constant time using prefix[r] - prefix[l-1]. While iterating through the array, track the smallest prefix value seen so far and compute the maximum difference with the current prefix. This effectively finds the maximum subarray profit without enumerating all pairs explicitly. Time complexity is O(n) and space complexity is O(n) for the prefix array.

The key insight: maximizing profit between two days is equivalent to maximizing the difference between two prefix sums where the smaller prefix appears earlier. This pattern appears frequently in Prefix Sum problems and can also be viewed as a sliding profit window over the array.

Instead of recomputing sums for every candidate buy and sell pair, prefix sums allow constant-time range evaluation. Maintaining the minimum prefix seen so far eliminates the need for nested loops. The algorithm performs a single pass through the data, updating the best achievable profit at each step.

This technique is closely related to maximum subarray problems and commonly appears with Array manipulation and window-based optimization. When implemented carefully, the logic resembles a rolling comparison similar to patterns used in Sliding Window problems.

Recommended for interviews: The prefix sum + enumeration optimization is the expected solution. A brute-force approach that checks all buy/sell pairs demonstrates understanding but runs in O(n^2). Interviewers typically look for the optimized linear scan using prefix differences because it shows recognition of the maximum-subarray-style transformation.

Solution

We use an array s to represent the prefix sum, where s[i] is the total profit for the first i days, i.e., s[i] = sum_{j=0}^{i-1} prices[j] times strategy[j]. We also use an array t to represent the prefix sum of stock prices, where t[i] = sum_{j=0}^{i-1} prices[j].

Initially, the maximum profit is s[n]. We enumerate the right endpoint i of the subarray to be modified, with the left endpoint being i-k. After modification, the first k/2 days of the subarray have strategy 0, and the last k/2 days have strategy 1, so the profit change is:

$\Delta = -(s[i] - s[i-k]) + (t[i] - t[i-k/2])

Therefore, we can update the maximum profit by enumerating all possible i.

The time complexity is O(n), and the space complexity is O(n), where n$ is the length of the array.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Buy/Sell EnumerationO(n^2)O(1)Useful for understanding the problem or verifying small inputs
Prefix Sum + EnumerationO(n)O(n)Best general solution for large arrays and interview settings
Running Minimum Prefix (Optimized Scan)O(n)O(1)When memory is constrained and prefix array storage is unnecessary

Video Solution

Best Time to Buy and Sell Stock using Strategy | Simply Detailed | Dry Run | Leetcode 3652 | MIK ā€¢ codestorywithMIK ā€¢ 7,852 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Best Time to Buy and Sell Stock using Strategy easy or hard?
The problem is typically classified as Medium because the brute-force idea is straightforward but the optimal solution requires recognizing a prefix-sum or maximum-subarray transformation. Identifying this pattern is the key step.
Best Time to Buy and Sell Stock using Strategy Python/Java solution
Most implementations compute a prefix sum or running cumulative gain while tracking the smallest prefix seen so far. This pattern works the same in Python, Java, C++, Go, TypeScript, Rust, and C#, producing an O(n) solution with minimal extra memory.
How to solve Best Time to Buy and Sell Stock using Strategy in O(n)?
First compute cumulative profit using prefix sums. While iterating through the array, track the minimum prefix value encountered so far. The difference between the current prefix and this minimum represents the best profit ending at that index, allowing the algorithm to update the global maximum in linear time.
What is the best approach for Best Time to Buy and Sell Stock using Strategy?
The most efficient approach uses prefix sums with a running minimum prefix value. By transforming the strategy into a gain array, the problem becomes finding the maximum difference between two prefix sums where the smaller one appears earlier. This runs in O(n) time and either O(n) or O(1) space depending on whether the prefix array is stored.
Is Best Time to Buy and Sell Stock using Strategy asked at Google/Amazon/Meta?
Stock profit optimization and maximum subarray style problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve prefix sums, dynamic profit tracking, or sliding windows are commonly used to test array optimization skills.
What data structure is used in Best Time to Buy and Sell Stock using Strategy?
The core structure is a simple array combined with prefix sums for cumulative profit computation. The algorithm also maintains a running minimum value to efficiently determine the best buy point before each sell point.
What is the time complexity of Best Time to Buy and Sell Stock using Strategy?
The optimal solution runs in O(n) time because the array is scanned once while maintaining the smallest prefix sum seen so far. Each step computes a candidate profit in constant time. Space complexity is O(n) with an explicit prefix array or O(1) with a running prefix calculation.

Ready to solve this problem?

Practice Best Time to Buy and Sell Stock using Strategy with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays