Maximal Stock Return — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Arrays
O(n)O(k)Problem Description
You are given two arrays of equal length: an integer array stockPrices where stockPrices[i] denotes the current price of the i‑th stock, and a floating‑point array growthRates where growthRates[i] denotes the expected fractional growth (e.g., 0.07 means a 7 % increase). The projected monetary gain of selecting stock i is defined as stockPrices[i] * growthRates[i]. Your task is to identify every index i that achieves the maximum projected gain. If several stocks share the same highest gain, return all their indices in ascending order. If the arrays are empty, return an empty list. The output must be a list of zero‑based indices.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximal Stock Return"
WHY DOES IT MATTER?
The max‑tracking pattern appears in many real‑world ranking, budgeting, and risk‑assessment tasks where you need the best candidate(s) without sorting the entire dataset, saving both time and memory.
OPTIMIZATION CHALLENGE
Recognizing that you only need the current maximum product and the indices achieving it eliminates the need for auxiliary arrays or sorting, collapsing the problem to O(n) time and O(k) extra space.
REAL-WORLD CONNECTION
Think of a stock‑exchange order book that continuously updates the best bid/ask price; the system must instantly know the current maximum without scanning all orders, similar to our single‑pass max product scan.
During an interview, compute the product on the fly, compare with a stored max, and immediately reset or extend the result list—this shows you can manage state efficiently under pressure.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem reduces to finding the maximum value of the product of two parallel arrays and then enumerating all positions that achieve this maximum. A naïve solution might compute every product, store them, sort, or use nested loops, which inflates time to O(n log n) or O(n²) and wastes memory. The optimal paradigm is a single‑pass linear scan that tracks the current maximum product and a dynamic list of indices, updating the list whenever a new maximum is discovered. This leverages the classic “single‑pass max‑tracking” pattern common in array problems.\n\nBecause growthRates are floating‑point numbers, precision issues arise; therefore comparisons should use a tolerance or rely on the language’s double precision semantics. By maintaining the maximum product as a double and updating only when a strictly larger value appears (or when equal, appending the index), we avoid both overflow and rounding pitfalls while keeping the algorithm simple and robust.
Interview Questions on This Problem
Q1How would you modify the solution if you needed the top k stocks by projected gain instead of all maximums?
Maintain a min‑heap of size k while iterating; push each product‑index pair, and when the heap exceeds k, pop the smallest. After the pass, the heap contains the top k indices in O(n log k) time and O(k) space.
Q2What issues can arise when comparing floating‑point projected gains, and how do you mitigate them in code?
Direct equality can fail due to rounding errors. Use a small epsilon (e.g., 1e-9) to treat two values as equal when their absolute difference is below the threshold, or rely on the language’s built‑in comparison of doubles if exact equality is not required for the problem constraints.
Q3Explain how you would adapt the algorithm for a streaming scenario where stock prices and growth rates arrive in real time.
Keep the current max product and its indices in state. For each incoming pair, compute the product, compare to the stored max, and update the state accordingly. This yields O(1) amortized update time and O(k) memory for the indices of the current maximum.
Examples
Input
stockPrices = [100,200,150], growthRates = [0.05,0.02,0.08]
Output
[2]
Explanation: Projected gains are: 100*0.05=5, 200*0.02=4, 150*0.08=12. The largest gain is 12, achieved only by index 2.
Input
stockPrices = [50,80,80], growthRates = [0.10,0.05,0.05]
Output
[0]
Explanation: Gains: 50*0.10=5, 80*0.05=4, 80*0.05=4. The maximum gain is 5 at index 0.
Input
stockPrices = [120,90,150,150], growthRates = [0.10,0.20,0.05,0.05]
Output
[1]
Explanation: Gains: 120*0.10=12, 90*0.20=18, 150*0.05=7.5, 150*0.05=7.5. The highest gain is 18, occurring at index 1.
Input
stockPrices = [100,200], growthRates = [0.20,0.10]
Output
[0,1]
Explanation: Gains: 100*0.20=20, 200*0.10=20. Both indices achieve the same maximal gain, so both are returned in ascending order.
Constraints
- 1 <= stockPrices.length <= 100000
- stockPrices.length == growthRates.length
- 0 <= stockPrices[i] <= 10^9
- 0.0 <= growthRates[i] <= 10.0
Optimal Approach & Strategy
Track the maximum product and result list while iterating once, updating them as you go.
Brute Force Approach
Compute all products, find the maximum in a second pass, then collect indices that match the maximum.
Code Solutions
/**
* @param {number[]} stockPrices - Array of integers representing current stock prices
* @param {number[]} growthRates - Array of floats representing expected fractional growth
* @return {number[]} - Array of indices of stocks with maximal projected monetary gain
*/
function maximalStockReturn(stockPrices, growthRates) {
const n = stockPrices.length;
if (n === 0) return [];
// Calculate projected gains and find the maximum
const gains = new Array(n);
let maxGain = -Infinity;
for (let i = 0; i < n; i++) {
gains[i] = stockPrices[i] * growthRates[i];
if (gains[i] > maxGain) {
maxGain = gains[i];
}
}
// Collect all indices with maximal gain
const result = [];
const EPS = 1e-9;
for (let i = 0; i < n; i++) {
if (Math.abs(gains[i] - maxGain) < EPS) {
result.push(i);
}
}
return result;
}
// Example usage
const stockPrices = [100, 200, 150];
const growthRates = [0.05, 0.02, 0.08];
const result = maximalStockReturn(stockPrices, growthRates);
console.log(result);#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> maximalStockReturn(vector<int>& stockPrices, vector<double>& growthRates) {
int n = stockPrices.size();
if (n == 0) return {};
// Calculate projected gains and find the maximum
vector<double> gains(n);
double maxGain = -1e18;
for (int i = 0; i < n; ++i) {
gains[i] = static_cast<double>(stockPrices[i]) * growthRates[i];
if (gains[i] > maxGain) {
maxGain = gains[i];
}
}
// Collect all indices with maximal gain
vector<int> result;
for (int i = 0; i < n; ++i) {
// Use epsilon comparison for floating point
if (fabs(gains[i] - maxGain) < 1e-9) {
result.push_back(i);
}
}
return result;
}
int main() {
vector<int> stockPrices = {100, 200, 150};
vector<double> growthRates = {0.05, 0.02, 0.08};
vector<int> result = maximalStockReturn(stockPrices, growthRates);
for (size_t i = 0; i < result.size(); ++i) {
if (i > 0) cout << ", ";
cout << result[i];
}
cout << endl;
return 0;
}
import java.util.List;
import java.util.ArrayList;
public class Solution {
/**
* Identify all indices of stocks with maximal projected monetary gain.
*
* @param stockPrices Array of integers representing current stock prices
* @param growthRates Array of doubles representing expected fractional growth
* @return List of indices of stocks with maximal projected monetary gain
*/
public static List<Integer> maximalStockReturn(int[] stockPrices, double[] growthRates) {
int n = stockPrices.length;
if (n == 0) return new ArrayList<>();
// Calculate projected gains and find the maximum
double[] gains = new double[n];
double maxGain = -Double.MAX_VALUE;
for (int i = 0; i < n; i++) {
gains[i] = stockPrices[i] * growthRates[i];
if (gains[i] > maxGain) {
maxGain = gains[i];
}
}
// Collect all indices with maximal gain
List<Integer> result = new ArrayList<>();
final double EPS = 1e-9;
for (int i = 0; i < n; i++) {
if (Math.abs(gains[i] - maxGain) < EPS) {
result.add(i);
}
}
return result;
}
public static void main(String[] args) {
int[] stockPrices = {100, 200, 150};
double[] growthRates = {0.05, 0.02, 0.08};
List<Integer> result = maximalStockReturn(stockPrices, growthRates);
System.out.println(result);
}
}
from typing import List
def maximal_stock_return(stock_prices: List[int], growth_rates: List[float]) -> List[int]:
"""
Identify all indices of stocks with maximal projected monetary gain.
Args:
stock_prices: List of integers representing current stock prices
growth_rates: List of floats representing expected fractional growth
Returns:
List of indices of stocks with maximal projected monetary gain
"""
n = len(stock_prices)
if n == 0:
return []
# Calculate projected gains and find the maximum
gains = [stock_prices[i] * growth_rates[i] for i in range(n)]
max_gain = max(gains)
# Collect all indices with maximal gain
EPS = 1e-9
result = [i for i in range(n) if abs(gains[i] - max_gain) < EPS]
return result
# Example usage
if __name__ == "__main__":
stock_prices = [100, 200, 150]
growth_rates = [0.05, 0.02, 0.08]
result = maximal_stock_return(stock_prices, growth_rates)
print(result)
/**
* @param {number[]} stockPrices - Array of integers representing current stock prices
* @param {number[]} growthRates - Array of floats representing expected fractional growth
* @return {number[]} - Array of indices of stocks with maximal projected monetary gain
*/
function maximalStockReturn(stockPrices, growthRates) {
const n = stockPrices.length;
if (n === 0) return [];
// Calculate projected gains and find the maximum
const gains = new Array(n);
let maxGain = -Infinity;
for (let i = 0; i < n; i++) {
gains[i] = stockPrices[i] * growthRates[i];
if (gains[i] > maxGain) {
maxGain = gains[i];
}
}
// Collect all indices with maximal gain
const result = [];
const EPS = 1e-9;
for (let i = 0; i < n; i++) {
if (Math.abs(gains[i] - maxGain) < EPS) {
result.push(i);
}
}
return result;
}
// Example usage
const stockPrices = [100, 200, 150];
const growthRates = [0.05, 0.02, 0.08];
const result = maximalStockReturn(stockPrices, growthRates);
console.log(result);
Asked in Top Tech Interviews
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.