101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Brute Force Approach - Complex approach
  2. Binary Search Insertion Approach - Complex approach
  3. Two Heaps Approach - Complex approach

Approach 1: Brute Force Approach

Let's start by understanding the problem: we need to design a data structure that can efficiently add numbers from a data stream and find the median of all numbers added so far.

Thinking Process: The most straightforward approach is to maintain a sorted array of all the numbers we've seen so far. When a new number comes in, we insert it into the correct position to maintain the sorted order. To find the median, we simply look at the middle element(s) of the sorted array.

Intuition: This approach directly follows the definition of the median. By keeping the array sorted, we can easily find the median by looking at the middle element(s). However, inserting a new element into a sorted array requires shifting elements, which can be inefficient for large arrays.

Algorithm:

  1. Initialize an empty array to store the numbers.
  2. For addNum(num):
  3. a. Find the correct position to insert num to maintain the sorted order.
  4. b. Insert num at that position.
  5. For findMedian():
  6. a. If the array has an odd number of elements, return the middle element.
  7. b. If the array has an even number of elements, return the average of the two middle elements.

Time Complexity:

O(n) for addNum, O(1) for findMedian

Where n is the number of elements in the array. Inserting a new element into a sorted array requires shifting elements, which takes O(n) time in the worst case. Finding the median takes constant time since we can directly access the middle element(s).

Space Complexity:

O(n)

We need to store all n elements in the array.

Approach 2: Binary Search Insertion Approach

We can optimize the brute force approach by using binary search to find the insertion position for a new number.

Thinking Process: Instead of linearly searching for the insertion position, we can use binary search to find it more efficiently. This reduces the time complexity of finding the insertion position from O(n) to O(log n). However, we still need to shift elements to make room for the new number, which takes O(n) time in the worst case.

Intuition: Binary search is a divide-and-conquer algorithm that efficiently finds the position of a target value in a sorted array. By using binary search, we can quickly find where to insert a new number to maintain the sorted order. This approach is more efficient than the brute force approach for finding the insertion position, but the overall time complexity for insertion is still dominated by the shifting operation.

Algorithm:

  1. Initialize an empty array to store the numbers.
  2. For addNum(num):
  3. a. Use binary search to find the correct position to insert num to maintain the sorted order.
  4. b. Insert num at that position.
  5. For findMedian():
  6. a. If the array has an odd number of elements, return the middle element.
  7. b. If the array has an even number of elements, return the average of the two middle elements.

Time Complexity:

O(n) for addNum, O(1) for findMedian

Where n is the number of elements in the array. Although binary search takes O(log n) time to find the insertion position, inserting a new element still requires shifting elements, which takes O(n) time in the worst case. Finding the median takes constant time.

Space Complexity:

O(n)

We need to store all n elements in the array.

Approach 3: Two Heaps Approach

We can use two heaps to efficiently maintain the median of a stream of numbers.

Thinking Process: The key insight is to divide the numbers into two halves: the smaller half and the larger half. We can use a max heap to store the smaller half and a min heap to store the larger half. By maintaining the property that the max heap contains all elements smaller than those in the min heap, and the sizes of the two heaps differ by at most 1, we can efficiently find the median.

Intuition: The two heaps approach is based on the observation that we don't need to keep the entire array sorted; we only need to know the middle element(s). By using two heaps, we can efficiently maintain the middle element(s) as new numbers are added to the stream. The max heap gives us the largest element in the smaller half, and the min heap gives us the smallest element in the larger half. These two elements are exactly what we need to calculate the median.

Algorithm:

  1. Initialize a max heap (smallerHalf) to store the smaller half of the numbers and a min heap (largerHalf) to store the larger half.
  2. For addNum(num):
  3. a. If smallerHalf is empty or num <= the top of smallerHalf, add num to smallerHalf.
  4. b. Otherwise, add num to largerHalf.
  5. c. Balance the heaps so that their sizes differ by at most 1.
  6. For findMedian():
  7. a. If the sizes of the heaps are equal, return the average of the tops of both heaps.
  8. b. If smallerHalf has more elements, return the top of smallerHalf.
  9. c. If largerHalf has more elements, return the top of largerHalf.

Time Complexity:

O(log n) for addNum, O(1) for findMedian

Where n is the number of elements in the heaps. Adding a number to a heap takes O(log n) time, and balancing the heaps also takes O(log n) time. Finding the median takes constant time since we can directly access the tops of the heaps.

Space Complexity:

O(n)

We need to store all n elements in the heaps.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MedianFinder:
    function __init__():
        this.nums = []
    
    function addNum(num):
        // Find the correct position to insert num
        position = 0
        while position < this.nums.length and this.nums[position] < num:
            position++
        
        // Insert num at the correct position
        this.nums.insert(position, num)
    
    function findMedian():
        n = this.nums.length
        if n % 2 == 1:
            // Odd number of elements
            return this.nums[n / 2]
        else:
            // Even number of elements
            return (this.nums[n / 2 - 1] + this.nums[n / 2]) / 2
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone