Probability and Statistics Problems
6 Probability and Statistics LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Separate outcomes, probabilities, and expectations
A probability measures how likely an event is; an expectation averages a numeric value over outcomes. For a sequence of random steps, define the state and transitions before choosing a recurrence. For a frequency histogram, each distinct value must be weighted by its count rather than treated as one equally likely observation.
When to use it
Use indicator variables to count expected successes, probability DP when future behavior depends on a compact state, and cumulative counts for histogram medians. New 21 Game and Soup Servings require careful terminal states as well as transition probabilities.
Worked example
Toss a fair coin twice. Compare the number of heads with the event of seeing at least one head.
- The equally likely outcomes are HH, HT, TH, TT; each has probability 1/4.
- Their head counts are 2, 1, 1, 0, so the expected head count is (2 + 1 + 1 + 0) / 4 = 1.
- Three outcomes have at least one head, giving that event probability 3/4.
Expected heads = 1, while P(at least one head) = 3/4. These answer different questions.
Time and space
A probability DP with S reachable states and T transitions per state typically takes O(S × T) time and O(S) storage. A histogram with b value bins can be scanned in O(b) time for count, mean, and median without expanding all observations.
Mistakes to check
- Linearity of expectation does not require independent indicators. Multiplying probabilities generally does require independence or a conditional-probability argument.
- Terminal states must follow the exact success, failure, and tie rules; accidentally continuing a finished process changes its probabilities.
- For an even number of observations, find both middle ranks using cumulative frequencies. Do not take the median of distinct keys alone.
Further reading: MIT Mathematics for Computer Science: probability and expectation
Guide reviewed .