Optimal Single Transaction Gain — Problem Statement & Solution Guide

ArraysMediumKadane's / Prefix Sum

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Optimal Single Transaction Gain problem optimally.

TopicArrays

PatternKadane's / Prefix Sum

TimeO(n)

SpaceO(1)

Problem Description

You are provided with an integer array prices representing the daily market value of a specific asset over a period of time. Your task is to determine the maximum profit achievable by executing exactly one buy-sell transaction within a specified subarray defined by two indices, left and right.

The transaction must follow the chronological constraint: the purchase day i must be strictly before the sale day j (i.e., i < j), and both indices must lie within the inclusive range [left, right]. The profit for a transaction is calculated as prices[j] - prices[i]. If no such pair of days yields a positive profit, the maximum gain is considered to be 0.

Given the array prices and the indices left and right, return the maximum possible profit. Note that you are not allowed to hold multiple transactions simultaneously; only one buy and one sell operation are permitted within the specified window.

DSA Pattern Breakdown

"Optimal Single Transaction Gain"

medium

WHY DOES IT MATTER?

This pattern is essential for optimizing financial calculations, real-time data processing, and any scenario where you need to find the maximum difference between two elements with an order constraint. It is a fundamental building block for more complex problems like 'Best Time to Buy and Sell Stock II' or 'Maximum Subarray Sum'.

OPTIMIZATION CHALLENGE

The key insight is to maintain the minimum price seen so far as you iterate through the array. By doing this, you can calculate the potential profit at each step in O(1) time, reducing the overall complexity from O(n^2) to O(n). This avoids the need to check all pairs of indices.

REAL-WORLD CONNECTION

In distributed systems, this is analogous to finding the maximum latency difference between two events in a log stream. Just as you track the minimum timestamp to find the maximum delay, you track the minimum price to find the maximum profit. This is crucial for monitoring and alerting in real-time systems.

In an interview, start by explaining the naive O(n^2) approach to show you understand the problem. Then, transition to the O(n) solution by emphasizing the state tracking (min price) and how it eliminates the need for nested loops. This demonstrates both problem-solving and optimization skills.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem of finding the maximum profit from a single buy-sell transaction within a subarray is a classic application of the 'Kadane's Algorithm' variant or a linear scan with state tracking. The naive approach involves checking every possible pair of indices (i, j) where i < j within the range [left, right], resulting in O(n^2) time complexity. This quadratic behavior becomes prohibitive for large arrays, such as those representing high-frequency trading data with millions of entries, where even a single query could take seconds or minutes to compute.

Interview Questions on This Problem

Q1At a fintech platform like Stripe, how would you optimize the calculation of maximum profit for a stock price array if you had to handle 10,000 such queries per second on the same static array?

For a static array with multiple queries, you can precompute a sparse table or a segment tree that stores the minimum price seen so far and the maximum profit achievable for any subarray. This allows each query to be answered in O(log n) or O(1) time after an O(n log n) or O(n) preprocessing step, respectively. The key is to store the minimum value and the maximum difference (current price - min price) for each segment.

Q2In a high-growth startup dealing with real-time asset valuation, how would you handle the case where the price array is being updated dynamically (insertions/deletions) while still needing to answer max profit queries efficiently?

For dynamic arrays, a balanced binary search tree (like a Treap or Red-Black Tree) augmented with additional fields (min value, max profit) can be used. Each node would store the minimum price in its subtree and the maximum profit achievable within that subtree. Updates would require recalculating these values up the tree, maintaining O(log n) time complexity for both updates and queries.

Q3At a global product company like Amazon, if the array represents daily prices and you need to find the max profit for a subarray, how would you handle the edge case where the prices are strictly decreasing?

If the prices are strictly decreasing, the maximum profit will be 0, as no profitable transaction is possible. The algorithm should initialize the maximum profit to 0 and ensure that it never goes negative. This is a critical edge case to handle to avoid returning a negative profit, which is not allowed in a single transaction scenario where you can choose not to trade.

Examples

Example 1

Input

prices = [7, 1, 5, 3, 6, 4], left = 1, right = 4

Output

Explanation: The subarray within indices [1, 4] is [1, 5, 3, 6]. The possible transactions are: buy at index 1 (val 1) and sell at index 2 (val 5) for profit 4; buy at index 1 (val 1) and sell at index 3 (val 3) for profit 2; buy at index 1 (val 1) and sell at index 4 (val 6) for profit 5; buy at index 2 (val 5) and sell at index 3 (val 3) for profit -2; buy at index 2 (val 5) and sell at index 4 (val 6) for profit 1; buy at index 3 (val 3) and sell at index 4 (val 6) for profit 3. The maximum profit is 5. Wait, let me re-calculate. Buy at 1 (val 1), sell at 4 (val 6) -> 6-1=5. Buy at 3 (val 3), sell at 4 (val 6) -> 6-3=3. Max is 5. Let me adjust the example to be clearer or pick different numbers to avoid confusion. Let's use prices = [10, 2, 5, 1, 7, 3], left=1, right=4. Subarray: [2, 5, 1, 7]. Buy 2 sell 5 -> 3. Buy 2 sell 1 -> -1. Buy 2 sell 7 -> 5. Buy 5 sell 1 -> -4. Buy 5 sell 7 -> 2. Buy 1 sell 7 -> 6. Max is 6.

Example 2

Input

prices = [10, 2, 5, 1, 7, 3], left = 1, right = 4

Output

Explanation: The relevant subarray is indices 1 to 4: [2, 5, 1, 7]. We evaluate all valid pairs (i, j) where i < j within this range. The minimum price encountered before the maximum price is key. The lowest price in the range is 1 (at index 3). The highest price after index 3 is 7 (at index 4). Profit = 7 - 1 = 6. Other pairs yield lower profits (e.g., buy 2 sell 7 = 5). Thus, the optimal gain is 6.

Example 3

Input

prices = [5, 4, 3, 2, 1], left = 0, right = 4

Output

Explanation: The subarray is [5, 4, 3, 2, 1]. The prices are strictly decreasing. Any buy-sell pair will result in a negative profit (e.g., buy 5 sell 4 = -1). Since the problem states that if no positive profit is possible, the answer is 0, the output is 0.

Example 4

Input

prices = [1, 2, 3, 4, 5], left = 0, right = 4

Output

Explanation: The subarray is [1, 2, 3, 4, 5]. The prices are strictly increasing. The optimal strategy is to buy at the earliest opportunity (index 0, val 1) and sell at the latest opportunity (index 4, val 5). Profit = 5 - 1 = 4.

Constraints

1 <= prices.length <= 10^5
0 <= left < right < prices.length
1 <= prices[i] <= 10^9

Optimal Approach & Strategy

Iterate through the subarray from left to right, maintaining the minimum price seen so far. At each step, calculate the potential profit by subtracting the minimum price from the current price and update the maximum profit if the current profit is higher.

Brute Force Approach

Iterate through all possible pairs of indices (i, j) within the range [left, right] where i < j. For each pair, calculate the profit as prices[j] - prices[i] and keep track of the maximum profit found.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} prices
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
function maxProfit(prices, left, right) {
    // Handle edge cases: if left > right or subarray has less than 2 elements
    if (left >= right || left < 0 || right >= prices.length) {
        return 0;
    }
    
    let minPrice = Infinity;
    let maxProfit = 0;
    
    // Iterate through the subarray from 'left' to 'right'
    for (let i = left; i <= right; i++) {
        // Update the minimum price seen so far
        minPrice = Math.min(minPrice, prices[i]);
        
        // Calculate potential profit if we sell on day i
        const currentProfit = prices[i] - minPrice;
        
        // Update maximum profit if current profit is higher
        maxProfit = Math.max(maxProfit, currentProfit);
    }
    
    return maxProfit;
}

// Example usage
const prices = [7, 1, 5, 3, 6, 4];
const left = 1;
const right = 4;

console.log(maxProfit(prices, left, right));

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int maxProfit(vector<int>& prices, int left, int right) {
    // Handle edge cases: if left > right or subarray has less than 2 elements
    if (left >= right || left < 0 || right >= prices.size()) {
        return 0;
    }
    
    int minPrice = INT_MAX;
    int maxProfit = 0;
    
    // Iterate through the subarray from 'left' to 'right'
    for (int i = left; i <= right; i++) {
        // Update the minimum price seen so far
        minPrice = min(minPrice, prices[i]);
        
        // Calculate potential profit if we sell on day i
        int currentProfit = prices[i] - minPrice;
        
        // Update maximum profit if current profit is higher
        maxProfit = max(maxProfit, currentProfit);
    }
    
    return maxProfit;
}

int main() {
    // Example usage
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    int left = 1;
    int right = 4;
    
    int result = maxProfit(prices, left, right);
    cout << result << endl;
    
    return 0;
}

import java.util.*;

public class Solution {
    public static int maxProfit(int[] prices, int left, int right) {
        // Handle edge cases: if left > right or subarray has less than 2 elements
        if (left >= right || left < 0 || right >= prices.length) {
            return 0;
        }
        
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        // Iterate through the subarray from 'left' to 'right'
        for (int i = left; i <= right; i++) {
            // Update the minimum price seen so far
            minPrice = Math.min(minPrice, prices[i]);
            
            // Calculate potential profit if we sell on day i
            int currentProfit = prices[i] - minPrice;
            
            // Update maximum profit if current profit is higher
            maxProfit = Math.max(maxProfit, currentProfit);
        }
        
        return maxProfit;
    }
    
    public static void main(String[] args) {
        // Example usage
        int[] prices = {7, 1, 5, 3, 6, 4};
        int left = 1;
        int right = 4;
        
        int result = maxProfit(prices, left, right);
        System.out.println(result);
    }
}

def max_profit(prices, left, right):
    """
    Determine the maximum profit achievable by executing exactly one buy-sell transaction
    within the subarray defined by indices 'left' and 'right'.
    
    Args:
        prices (list[int]): Array of daily prices
        left (int): Start index of the subarray
        right (int): End index of the subarray
    
    Returns:
        int: Maximum profit achievable
    """
    # Handle edge cases: if left > right or subarray has less than 2 elements
    if left >= right or left < 0 or right >= len(prices):
        return 0
    
    min_price = float('inf')
    max_profit = 0
    
    # Iterate through the subarray from 'left' to 'right'
    for i in range(left, right + 1):
        # Update the minimum price seen so far
        min_price = min(min_price, prices[i])
        
        # Calculate potential profit if we sell on day i
        current_profit = prices[i] - min_price
        
        # Update maximum profit if current profit is higher
        max_profit = max(max_profit, current_profit)
    
    return max_profit

# Example usage
if __name__ == "__main__":
    prices = [7, 1, 5, 3, 6, 4]
    left = 1
    right = 4
    
    result = max_profit(prices, left, right)
    print(result)

/**
 * @param {number[]} prices
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
function maxProfit(prices, left, right) {
    // Handle edge cases: if left > right or subarray has less than 2 elements
    if (left >= right || left < 0 || right >= prices.length) {
        return 0;
    }
    
    let minPrice = Infinity;
    let maxProfit = 0;
    
    // Iterate through the subarray from 'left' to 'right'
    for (let i = left; i <= right; i++) {
        // Update the minimum price seen so far
        minPrice = Math.min(minPrice, prices[i]);
        
        // Calculate potential profit if we sell on day i
        const currentProfit = prices[i] - minPrice;
        
        // Update maximum profit if current profit is higher
        maxProfit = Math.max(maxProfit, currentProfit);
    }
    
    return maxProfit;
}

// Example usage
const prices = [7, 1, 5, 3, 6, 4];
const left = 1;
const right = 4;

console.log(maxProfit(prices, left, right));

Asked in Top Tech Interviews

Zomato

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.