Best Time to Buy and Sell Stock
Easy About 10 min Free, no account needed
Maximize the profit from a single buy followed by a later sell.
The brief
You are given an array prices where prices[i] is the price of a stock on day
i. Buy on one day and sell on a later day. Return the maximum profit
you can make, or 0 if no profitable trade exists.
The obvious approach compares every pair of days, O(n²). The hidden test
uses 200,000 prices, so that's too slow. MaxProfit needs an approach that
scales better than checking every pair of days.
Starter code
using System;
public class Solution
{
// TODO: return the maximum profit from a single buy and later sell.
public int MaxProfit(int[] prices)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Prefix sums
- Carry running totals or prefix state so any range question becomes a lookup.
- Greedy algorithms
- Make the locally best choice when an exchange argument proves it stays globally optimal.
Related katas
- Find Pivot Index Easy Free The index where everything to the left weighs the same as everything to the right.
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.