Abstract / Summary

Count how many continuous parts of a list have the middle number equal to k when their length is odd.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “count subarrays with median k” problem by exploiting the fact that any qualifying subarray must contain the element k. The algorithm locates the position of k, then builds cumulative counts of elements smaller and larger than k on both sides of that position. By translating these counts into a signed “balance” (larger - smaller) the code can pair left-side and right-side prefixes whose balances satisfy the median condition. The final answer is accumulated by multiplying the frequencies of matching balances.

Key Steps

Locate the pivot element

mid = nums.index(k)

The index of the first occurrence of k is stored in mid. All valid subarrays must start at or before this index and end at or after it, guaranteeing that k is present.

Build cumulative smaller / larger counters

Two arrays, smaller and larger, of length size are allocated. The left-side loop walks backward from mid-1 to 0, updating each entry with the cumulative count of elements less than k and greater than k respectively. The right-side loop walks forward from mid+1 to the end, performing the same cumulative update in the opposite direction.

for i in reversed(range(mid)):
    smaller[i] = smaller[i + 1] + (nums[i] < k)
    larger[i] = larger[i + 1] + (nums[i] > k)

for i in range(mid + 1, size):
    smaller[i] = smaller[i - 1] + (nums[i] < k)
    larger[i] = larger[i - 1] + (nums[i] > k)

After these passes, smaller[i] (or larger[i]) represents the total number of elements smaller (or larger) than k in the segment from i to mid on the left, or from mid to i on the right.

Translate counts into a balance value

For any position i, the expression larger[i] - smaller[i] captures the net excess of elements larger than k over those smaller than k in the prefix ending at i. This balance is the core invariant used to decide whether a combined left-right prefix yields a median of k.

Record frequency of balances on each side

Two defaultdict(int) maps, left and right, store how many times each balance occurs on the left side (including the pivot) and on the right side (including the pivot). The left map iterates from index 0 through mid, while the right map iterates from mid through the last index.

for i in range(mid + 1):
    left[larger[i] - smaller[i]] += 1

for i in range(mid, size):
    right[larger[i] - smaller[i]] += 1

Including the pivot in both maps ensures that subarrays consisting solely of k are counted.

Combine left and right balances to count subarrays

The final loop iterates over each distinct balance delta observed on the left. For odd-length subarrays the total balance must be zero, so a matching right balance of -delta is required. For even-length subarrays the total balance must be +1, which translates to a right balance of -delta + 1. The product of the frequencies gives the number of subarrays formed by pairing any left prefix with any compatible right prefix.

for delta in left:
    if -delta in right:
        result += left[delta] * right[-delta]

    if -delta + 1 in right:
        result += left[delta] * right[-delta + 1]

The accumulated result is returned as the answer.

Edge Cases Handled

When the array consists of a single element equal to k, mid points to index 0, the cumulative loops execute zero iterations, and both left and right contain a single entry with balance 0. The combination step then adds one to result, correctly counting the trivial subarray.

If all elements to the left of k are smaller and all to the right are larger, the cumulative counters correctly reflect a monotonic increase in smaller on the left and larger on the right. The balance values become negative on the left side and positive on the right side, and the matching logic still finds the required pairs.

When the array contains multiple occurrences of the same value as k, the index call selects the first occurrence. Because the algorithm only requires a single pivot that belongs to every qualifying subarray, using the first occurrence still yields a correct count; any subarray that contains a later k will also contain the first one, preserving the invariant.

If the array has no elements smaller than k (or no elements larger than k), the corresponding cumulative array entries remain zero, and the balance reduces to the count of the opposite side. The matching step still works because the opposite side’s map will contain the necessary complementary balances.

When the array is entirely composed of values equal to k, both smaller and larger stay at zero for every index, producing a balance of zero everywhere. The left and right frequency maps both record the full length of the array, and the combination step counts every possible subarray, which is the correct result for this uniform case.

Performance Optimizations

The algorithm avoids nested loops over subarray boundaries by converting the median condition into a simple arithmetic relationship between prefix balances. This reduction enables a linear-time solution. The use of pre-allocated integer lists for smaller and larger ensures that cumulative updates are performed in place without additional memory allocation per iteration.

The two passes that fill smaller and larger each run in O(n) time, and the subsequent construction of the frequency maps also traverses the array once per side. By employing defaultdict(int), the code achieves constant-time insertion and lookup for balance frequencies, eliminating the need for explicit existence checks.

The final aggregation step iterates only over the distinct balances present on the left side, which in the worst case is bounded by the length of the array but typically far fewer. Multiplying the frequencies directly counts all compatible left-right prefix pairs without enumerating each pair individually, dramatically reducing the combinatorial overhead that a naïve double-loop would incur.

Overall, the design leverages prefix aggregation, hash-based frequency counting, and arithmetic symmetry to deliver an efficient solution that scales linearly with the input size.

Imagine a long row of colored blocks. The goal is to hunt for groups of blocks, called subarrays, that have a specific special number right in the middle as their median.

To find these groups, first find where that special number is hiding in the whole row. Since the special number must be the center, every group has to include that spot. Think of the row as having a left side and a right side, starting from the special number.

On the left side, go backward and keep track of how many blocks are smaller than the special one and how many are larger. Do the same thing on the right side, but go forward this time. By looking at the difference between the larger and smaller counts, a pattern emerges. Each spot in the row gets a simple score based on how many extra big or small blocks it has.

After those scores are ready, the code looks at the left side and the right side to see which pairs of scores can fit together perfectly. If the scores match up in just the right way, those sides form a valid group where the special number sits exactly in the middle as the median. Every time a perfect match is found, it counts as one more group found. By checking all the possible ways the left and right sides can combined, all valid groups are discovered.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		C++	Java		Python	TS
	WalkCCC		C++	Java		Python
	leetcode.ca		C++	Java	Go	Python	TS
	Progiez		C++	Java		Python
github	charles-wangkai			Java
	everthis	JS
	fsq		C++
	JoshCrozier	JS
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality