Weekly Coding Challenge #2: Best Time to Buy and Sell Stock

Problem: You're given an array prices where prices[i] is the price of a stock on day i. You want to maximize profit by choosing a single day to buy and a different, later day to sell. Return the maximum profit achievable, or 0 if no profit is possible.

Business rules

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

Example 1: Input: prices = [7,1,5,3,6,4] Output: 5 (buy on day 2 at price 1, sell on day 5 at price 6, profit = 5)

Example 2: Input: prices = [7,6,4,3,1] Output: 0 (prices only fall — no transaction is profitable)

Why this pattern matters beyond interviews: the core skill is tracking a running minimum (or maximum) in a single pass instead of comparing every pair of days . The same technique behind streaming anomaly detection, monitoring a rolling baseline for drift, or flagging the best entry point in any time series without re-scanning history each time a new data point arrives.

Challenge #1 Recap: Two Sum

Problem: Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you can't use the same element twice.

Solution. single-pass HashMap, O(n) time / O(n) space:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // value -> index of the first time we saw it
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[] { seen.get(complement), i };
            }
            seen.put(nums[i], i);
        }

        throw new IllegalArgumentException("No two sum solution");
    }
}

The trick: instead of checking every pair (O(n²)), you check for a number's complement before inserting the current number into the map. By the time you reach index i, the map already holds every value from earlier in the array, so the lookup is O(1) and the whole pass is O(n). This "remember what you've seen" pattern shows up constantly: deduplication, frequency counts, caching lookups you'd otherwise redo.

Please feel free to post your solution! There is no right or wrong.

References

LeetCode. (n.d.). Best time to buy and sell stock. LeetCode. https://leetcode.com/problems/best-time-to-buy-and-sell-stock/