Running Median
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.heaps;
/* * ============================================================================================ * PROBLEM: Running Median (Dynamic Delivery Time Estimation) * ============================================================================================ * * --------------------- * 1. Logical Breakdown & Mathematical Formulation * --------------------- * We need to find the median after every insertion. Sorting the array every time * would take O(N^2 log N) total, which is too slow. * * Step 1: Divide and Conquer with Heaps * - Max-Heap (leftHalf): Stores the smaller half of the numbers. The root is the * largest of the small numbers. * - Min-Heap (rightHalf): Stores the larger half of the numbers. The root is the * smallest of the large numbers. * * Step 2: Balancing Act * - For every new element x: * 1. If x <= leftHalf.peek(), add to leftHalf. Else, add to rightHalf. * 2. Rebalance: Ensure the size difference between heaps is at most 1. * 3. Per problem constraints: If total elements N is even, median is leftHalf.peek(). * This implies we should maintain leftHalf.size() >= rightHalf.size(). * * Step 3: Median Extraction * - If N is odd: The median is the root of the larger heap. * - If N is even: The median is B[N/2 - 1], which corresponds to the root of the * Max-Heap (leftHalf) when we keep sizes equal or left favored. * * --------------------- * 2. Complexity Analysis * --------------------- * Time Complexity: * O(N log N) * - We process N elements. * - Each element involves a heap insertion and potentially a rebalance: O(log N). * * Space Complexity: * O(N) to store all delivery times across the two heaps. * * --------------------- * 3. Base Case Verification * --------------------- * - N=1: Element added to Max-Heap. Median = Max-Heap.peek(). * - N=2: Max-Heap size 1, Min-Heap size 1. Median = Max-Heap.peek(). * ============================================================================================ / public class RunningMedian { public int[] solve(int[] A) { // TODO: Implement solution return new int[0]; } }