I took about three versions before working out a solution in Python

My solution breaks the problem down as follows

• Median function based on frequency list / counting sort
• Prime the frequency list with the first d items
• Check for odd/even median (odd run median once, even run median twice and avarage)
• Check expenditure vs. median from d onwards and update frequency list (+1 / -1) at each iteration