Find Median from Data Stream - aloalgo
aloalgo logoaloalgo
Beta
Problems
Login

Find Median from Data Stream

Medium

You are given an array of integers, numbers.

Your task is to calculate and record the median of all numbers processed so far, after each new number from numbers is considered.

Remember that:

  • The median of an ordered list with an odd number of elements is the middle value.
  • The median of an ordered list with an even number of elements is the average of the two middle values.
  • If the calculated median is a decimal, it should be rounded down.

Return an array of integers, where each element represents the median calculated after processing each corresponding number in the input array.

Example 1

Input
[1, 2, 3]
Output
[1, 1, 2]
Explanation:
  1. When 1 is added, the list is [1]. Median is 1.
  2. When 2 is added, the list is [1, 2]. Median is (1+2)/2 = 1.5.
  3. When 3 is added, the list is [1, 2, 3]. Median is 2.

Example 2

Input
[5, 15, 1, 3]
Output
[5, 10, 5, 4]
Explanation:
  1. Current numbers: [5], median 5.
  2. Current numbers: [5, 15], median (5+15)/2 = 10.
  3. Current numbers: [1, 5, 15], median 5.0. 4. Current numbers: [1, 3, 5, 15], median `(3+5)/2 = 4.

Example 3

Input
[2, 3, 4]
Output
[2, 2, 3]
Explanation:
  1. Current numbers: [2], median 2.
  2. Current numbers: [2, 3], median (2+3)/2 = 2.5 which gets rounded to 2.
  3. Current numbers: [2, 3, 4], median 3.
Loading...
Case 1Case 2Case 3
Input
[1, 2, 3]
Output
[1, 1, 2]
🤖

Hello! I am your ✨ AI assistant. I can provide you hints, explanations, give feedback on your code, and more. Just ask me anything related to the problem you're working on!