How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Compute max profit from single stock trade

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an array prices where prices[i] is the stock price on day i, compute the maximum profit achievable with at most one transaction (one buy and one sell, buy before sell). Return 0 if no profit is possible. Aim for O(n) time and O( 1) extra space. Explain the algorithm, prove correctness, and analyze time/space complexity. Optionally, also return the buy and sell indices.

Quick Answer: This question evaluates a candidate's ability to design efficient array algorithms, reason about time and space complexity constraints, and handle edge cases related to single-transaction profit calculation.

Given an array `prices` where `prices[i]` is the price of a given stock on day `i`, find the maximum profit you can achieve from at most one transaction (buy on one day and sell on a later day). You must buy before you sell. If no profit is possible, return `0`. Aim for O(n) time and O(1) extra space. Example 1: Input: prices = [7, 1, 5, 3, 6, 4] Output: 5 Explanation: Buy on day 1 (price = 1) and sell on day 4 (price = 6), profit = 6 - 1 = 5. Example 2: Input: prices = [7, 6, 4, 3, 1] Output: 0 Explanation: Prices only fall, so no transaction is profitable; return 0.

Constraints

0 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
You may complete at most one transaction (one buy followed by one later sell).
If no profitable transaction exists, return 0.

Examples

Input: ([7, 1, 5, 3, 6, 4],)

Expected Output: 5

Explanation: Buy at 1 (day 1), sell at 6 (day 4); profit = 5, the maximum achievable.

Input: ([7, 6, 4, 3, 1],)

Expected Output: 0

Explanation: Prices strictly decrease, so any buy-then-sell loses money; return 0.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 4

Explanation: Buy at 1 (day 0), sell at 5 (day 4); profit = 4.

Input: ([],)

Expected Output: 0

Explanation: Empty array: no transaction possible, return 0.

Input: ([5],)

Expected Output: 0

Explanation: Single day: cannot buy and sell on different days, return 0.

Input: ([2, 2, 2, 2],)

Expected Output: 0

Explanation: All prices equal, so no positive profit; return 0.

Input: ([3, 2, 6, 1, 4],)

Expected Output: 4

Explanation: Best is buy at 2 (day 1), sell at 6 (day 2); profit = 4. The later 1->4 only gives 3.

Input: ([2, 4, 1],)

Expected Output: 2

Explanation: Buy at 2 (day 0), sell at 4 (day 1); profit = 2. The trailing 1 cannot be sold higher.

Hints

Track the lowest price seen so far as you scan left to right; the best sell-on-day-i profit is prices[i] minus that running minimum.
Keep two running values: the minimum price so far and the maximum profit so far. Update profit before lowering the minimum, since you must buy strictly before you sell.
Brute force tries every (buy, sell) pair in O(n^2); the single-pass approach collapses this to O(n) time and O(1) space.

Quick Overview

This question evaluates a candidate's ability to design efficient array algorithms, reason about time and space complexity constraints, and handle edge cases related to single-transaction profit calculation.