Matrix Median in C++

Matrix Median in C++ (also known as Median in a Row-Wise Sorted Matrix) is one of the most intellectually rewarding hard-tier matrix and binary search questions asked in technical interviews at top-tier companies including Google, Amazon, Microsoft, Uber, and Bloomberg. You are given a 2D matrix of dimensions R × C where every individual row is sorted in non-decreasing order, and the total number of elements (R × C) is guaranteed to be odd. The algorithmic objective is to find and return the overall median value of the matrix in strict O(R · log C · log(MAX – MIN)) time complexity and O(1) auxiliary space. In this comprehensive masterclass, we will deconstruct the problem from first principles: covering the O(R · C · log(R · C)) Flatten & Sort Brute Force, an O((R · C) · log R) Min-Heap K-Way Merge, and the Optimal Binary Search on Value Range with Row-Wise std::upper_bound. We will also analyze value-space binary search invariants, benchmark on a 1,000,000-cell matrix, and provide interactive “Try it yourself” challenges after every section.

🔹 What is the Matrix Median? Mathematical Foundations & Invariants

For an array or matrix containing a total of N = R × C elements where N is odd, the median is the unique element that occupies the exact center position, index ⌊N / 2⌋, when all N elements are sorted in global non-decreasing order.

Consider a 3 × 3 Row-Wise Sorted Matrix (R = 3, C = 3, Total Elements N = 9):
Row 0: [ 1,  3,  5 ]
Row 1: [ 2,  6,  9 ]
Row 2: [ 3,  6,  9 ]

Sorted 1D representation: [ 1, 2, 3, 3, 5, 6, 6, 9, 9 ]
0-based indices:          [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
The middle index is: ⌊9 / 2⌋ = 4 → Median Value = 5

From this definition, we derive the core mathematical counting invariant:

• The Median Rank Theorem: In any collection of N elements (where N is odd), the median M is the smallest integer x such that the count of elements less than or equal to x is strictly greater than ⌊N / 2⌋:

  Count(elements <= x) >= ⌊(R × C) / 2⌋ + 1 = (R × C + 1) / 2

  For N = 9, required count ≥ 5 elements.
• Global Search Space Bounds:
  • The global minimum element MIN is located in the first column: MIN = min(mat[0][0], mat[1][0], ..., mat[R-1][0]).
  • The global maximum element MAX is located in the last column: MAX = max(mat[0][C-1], mat[1][C-1], ..., mat[R-1][C-1]).
  • Therefore, the true median value is guaranteed to lie in the range [MIN, MAX].
• Monotonic Counting Function: As the candidate value x increases from MIN to MAX, the total count of elements ≤ x is strictly non-decreasing (monotonic). This monotonic property allows us to binary search directly on the value space!

Try it yourself

• In the example matrix above, how many elements are ≤ 3? (Answer: 4 elements). Does this satisfy the median threshold of ≥ 5?
• Why is it impossible for the median to be smaller than the minimum element in column 0 or larger than the maximum element in column C – 1?

🔹 Approach 1: Brute Force (Flatten Matrix & Sort: O(R · C · log(R · C)))

Intuition & Reasoning: The most straightforward approach is to copy all R × C elements from the 2D matrix into a flat 1D std::vector<int>, sort the vector using std::sort, and directly return the element at middle index (R * C) / 2.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

// Approach 1: Flatten and Sort
// Time Complexity: O((R * C) * log(R * C)), Space Complexity: O(R * C)
int find_matrix_median_brute(const vector<vector<int>>& mat) {
    const int r = static_cast<int>(mat.size());
    const int c = static_cast<int>(mat[0].size());

    vector<int> flat;
    flat.reserve(r * c);

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            flat.push_back(mat[i][j]);
        }
    }

    sort(flat.begin(), flat.end());
    return flat[(r * c) / 2];
}

int main() {
    vector<vector<int>> mat1 = {
        {1, 3, 5},
        {2, 6, 9},
        {3, 6, 9}
    };
    vector<vector<int>> mat2 = {
        {1, 3, 4},
        {2, 5, 6},
        {7, 8, 9}
    };

    cout << "--- Approach 1: Flatten & Sort ---\n";
    cout << "Matrix 1 Median: " << find_matrix_median_brute(mat1) << "\n";
    cout << "Matrix 2 Median: " << find_matrix_median_brute(mat2) << "\n";

    assert(find_matrix_median_brute(mat1) == 5);
    assert(find_matrix_median_brute(mat2) == 5);
    cout << "All assertions passed successfully!\n";
    return 0;
}

Output

--- Approach 1: Flatten & Sort ---
Matrix 1 Median: 5
Matrix 2 Median: 5
All assertions passed successfully!

Step by Step State Trace

Tracing find_matrix_median_brute on mat1:

1. Collect Elements: flat = [1, 3, 5, 2, 6, 9, 3, 6, 9] (size = 9)
2. std::sort:        flat = [1, 2, 3, 3, 5, 6, 6, 9, 9]
3. Middle Index:     index = 9 / 2 = 4
4. Median Element:   flat[4] = 5

Complexity Analysis

• Time Complexity (TC): O((R · C) · log(R · C)): Copying takes O(R · C) and introsort takes O(N log N) comparisons where N = R · C.
• Space Complexity (SC): O(R · C): Requires allocating a dynamically sized vector to hold all R × C integers.
• Bottleneck: Completely discards the fact that rows are already sorted, wasting memory and CPU sort cycles.

Try it yourself

• Can we use std::nth_element instead of std::sort to reduce time complexity to O(R · C)? (Hint: Yes, but auxiliary space remains O(R · C)).
• For a matrix of size 1000 × 1001, how many megabytes of auxiliary memory does this approach allocate?

🔹 Approach 2: Min-Heap K-Way Merge (O((R · C) · log R))

Intuition & Reasoning: Since each of the R rows is an individually sorted stream, we can merge the R sorted arrays using a Min-Heap (Priority Queue) of size R. We push the first element of each row into the min-heap. We pop the minimum element (R * C) / 2 + 1 times. The last popped element is guaranteed to be the median!

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cassert>

using namespace std;

// Approach 2: Min-Heap K-Way Merge
// Time Complexity: O((R * C / 2) * log R), Space Complexity: O(R)
int find_matrix_median_heap(const vector<vector<int>>& mat) {
    const int r = static_cast<int>(mat.size());
    const int c = static_cast<int>(mat[0].size());
    const int target_pops = (r * c) / 2 + 1;

    // Min-Heap stores tuples of: {value, row_index, col_index}
    using Element = tuple<int, int, int>;
    priority_queue<Element, vector<Element>, greater<Element>> min_heap;

    // Push the first element of every row
    for (int i = 0; i < r; ++i) {
        min_heap.emplace(mat[i][0], i, 0);
    }

    int median_val = 0;
    for (int step = 0; step < target_pops; ++step) {
        auto [val, row, col] = min_heap.top();
        min_heap.pop();
        median_val = val;

        // If the current row has more elements, push the next element
        if (col + 1 < c) {
            min_heap.emplace(mat[row][col + 1], row, col + 1);
        }
    }

    return median_val;
}

int main() {
    vector<vector<int>> mat1 = {
        {1, 3, 5},
        {2, 6, 9},
        {3, 6, 9}
    };

    cout << "--- Approach 2: Min-Heap K-Way Merge ---\n";
    cout << "Matrix 1 Median: " << find_matrix_median_heap(mat1) << "\n";
    assert(find_matrix_median_heap(mat1) == 5);
    cout << "All assertions passed successfully!\n";
    return 0;
}

Output

--- Approach 2: Min-Heap K-Way Merge ---
Matrix 1 Median: 5
All assertions passed successfully!

Complexity Analysis

• Time Complexity (TC): O((R · C / 2) · log R): We perform (R · C) / 2 + 1 heap pops and pushes, each taking O(log R) time.
• Space Complexity (SC): O(R): The priority queue maintains at most R elements at any point in time.
• Limitation: For large matrices (e.g. 1000 × 1000), 500,000 heap operations are still required, which is far slower than binary searching the value range.

Try it yourself

• Why does the heap approach only need to pop (R * C) / 2 + 1 times instead of all R * C times?
• What is the size of the heap if R = 10,000 and C = 5?

🔹 Approach 3: Optimal Binary Search on Value Range (O(R · log C · log(MAX: MIN)))

Intuition & Invariant: Instead of searching across indices, we perform a Binary Search on the Value Range [low, high]:

1. Determine Value Range:
   low  = min element in Column 0
   high = max element in Column (C - 1)

2. Binary Search on Values:
   mid = low + (high - low) / 2

   Count how many elements in the ENTIRE matrix are <= mid.
   Since each row is sorted, we can count elements <= mid in O(log C) per row
   using std::upper_bound!

   Total Count = ∑ upper_bound(row.begin(), row.end(), mid)

3. Invariant Decision:
   - If Total Count <= (R * C) / 2:
       The candidate value 'mid' is too small. The true median must be strictly greater!
       → low = mid + 1;
   - If Total Count > (R * C) / 2:
       'mid' could be the median or larger than the median.
       → high = mid; (Keep candidate in search space!)

4. Termination:
   When low == high, 'low' has converged precisely on the matrix median!

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cassert>

using namespace std;

// Helper: Count elements <= target in a sorted row using binary search
int count_less_or_equal(const vector<int>& row, int target) {
    // upper_bound returns iterator to first element > target
    return static_cast<int>(upper_bound(row.begin(), row.end(), target) - row.begin());
}

// Approach 3: Optimal Binary Search on Value Range
// Time Complexity: O(R * log C * log(MAX - MIN)), Space Complexity: O(1)
int find_matrix_median_optimal(const vector<vector<int>>& mat) {
    const int r = static_cast<int>(mat.size());
    const int c = static_cast<int>(mat[0].size());
    const int req = (r * c) / 2; // Target: strictly greater than req elements <= median

    // Find global minimum and maximum values
    int low = INT_MAX;
    int high = INT_MIN;
    for (int i = 0; i < r; ++i) {
        low = min(low, mat[i][0]);
        high = max(high, mat[i][c - 1]);
    }

    // Binary search on value space [low, high]
    while (low < high) {
        int mid = low + (high - low) / 2;

        int count = 0;
        for (int i = 0; i < r; ++i) {
            count += count_less_or_equal(mat[i], mid);
        }

        if (count <= req) {
            // Not enough elements <= mid; median must be strictly larger
            low = mid + 1;
        } else {
            // At least (req + 1) elements <= mid; candidate median found
            high = mid;
        }
    }

    return low;
}

int main() {
    vector<vector<int>> mat1 = {
        {1, 3, 5},
        {2, 6, 9},
        {3, 6, 9}
    };
    vector<vector<int>> mat2 = {
        {1, 3, 4},
        {2, 5, 6},
        {7, 8, 9}
    };

    cout << "--- Approach 3: Optimal Value-Space Binary Search ---\n";
    cout << "Matrix 1 Median: " << find_matrix_median_optimal(mat1) << "\n";
    cout << "Matrix 2 Median: " << find_matrix_median_optimal(mat2) << "\n";

    assert(find_matrix_median_optimal(mat1) == 5);
    assert(find_matrix_median_optimal(mat2) == 5);
    cout << "All assertions passed successfully!\n";
    return 0;
}

Output

--- Approach 3: Optimal Value-Space Binary Search ---
Matrix 1 Median: 5
Matrix 2 Median: 5
All assertions passed successfully!

Step by Step Value Range Convergence Trace

Tracing find_matrix_median_optimal on mat1 (R = 3, C = 3, req = 4):

Initial Range: low = 1, high = 9

Iter 1: mid = 1 + (9 - 1) / 2 = 5
        Row 0 [1, 3, 5] <= 5 → 3
        Row 1 [2, 6, 9] <= 5 → 1
        Row 2 [3, 6, 9] <= 5 → 1
        Total count <= 5 is: 3 + 1 + 1 = 5.
        Condition: count (5) <= req (4) is FALSE → high = mid = 5. Window: [1..5].

Iter 2: mid = 1 + (5 - 1) / 2 = 3
        Row 0 [1, 3, 5] <= 3 → 2
        Row 1 [2, 6, 9] <= 3 → 1
        Row 2 [3, 6, 9] <= 3 → 1
        Total count <= 3 is: 2 + 1 + 1 = 4.
        Condition: count (4) <= req (4) is TRUE → low = mid + 1 = 4. Window: [4..5].

Iter 3: mid = 4 + (5 - 4) / 2 = 4
        Row 0 [1, 3, 5] <= 4 → 2
        Row 1 [2, 6, 9] <= 4 → 1
        Row 2 [3, 6, 9] <= 4 → 1
        Total count <= 4 is: 2 + 1 + 1 = 4.
        Condition: count (4) <= req (4) is TRUE → low = mid + 1 = 5. Window: [5..5].

Termination: low == high (5 == 5).
Result: Median = 5! Converged in 3 iterations!

Complexity Analysis & Invariant Proof

• Time Complexity (TC): O(R · log C · log(MAX – MIN)): The value range binary search runs log₂(MAX - MIN) times (at most 32 iterations for 32-bit integers). In each iteration, we binary search across R rows, each taking O(log C). For a 1000 × 1000 matrix with values up to 10⁹, total operations ≤ 30 × 1000 × 10 ≈ 300,000 steps!
• Space Complexity (SC): O(1): Modifies nothing and requires zero auxiliary heap allocations.
• Guaranteed Existence Proof: Even though binary search operates on continuous integer space, low is mathematically guaranteed to converge on a value that actually exists in the matrix because any non-existent value will share the exact same count as the nearest smaller existing value.

Try it yourself

• Why does the algorithm use std::upper_bound instead of std::lower_bound?
• What happens if all elements in the matrix are identical (e.g., all 7s)? Trace how low and high behave.

🔹 Advanced Systems Topic: Numerical Safety & Cache Efficiency

When searching over large integer value ranges (e.g., MIN = -2×10⁹, MAX = 2×10⁹), computing (low + high) / 2 overflows standard 32-bit signed integers. Always use low + (high - low) / 2 or cast to long long. Furthermore, since each row binary search operates on a contiguous row buffer in row-major order, hardware prefetchers can stream cache lines with near-zero memory stalls.

🔹 Lab: High Performance Benchmark Across 1,000,000 Cells (1,000 × 1,001 Matrix)

The following benchmark executable pits all three approaches against each other on a 1,000 × 1,001 matrix (1,001,000 integers) using std::chrono::high_resolution_clock:

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;
using namespace std::chrono;

int bench_flatten(const vector<vector<int>>& mat) {
    int r = mat.size(), c = mat[0].size();
    vector<int> flat;
    flat.reserve(r * c);
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) flat.push_back(mat[i][j]);
    }
    sort(flat.begin(), flat.end());
    return flat[(r * c) / 2];
}

int bench_heap(const vector<vector<int>>& mat) {
    int r = mat.size(), c = mat[0].size();
    int target = (r * c) / 2 + 1;
    using Elem = tuple<int, int, int>;
    priority_queue<Elem, vector<Elem>, greater<Elem>> pq;
    for (int i = 0; i < r; ++i) pq.emplace(mat[i][0], i, 0);
    int med = 0;
    for (int s = 0; s < target; ++s) {
        auto [val, row, col] = pq.top();
        pq.pop();
        med = val;
        if (col + 1 < c) pq.emplace(mat[row][col + 1], row, col + 1);
    }
    return med;
}

int bench_val_bs(const vector<vector<int>>& mat) {
    int r = mat.size(), c = mat[0].size(), req = (r * c) / 2;
    int low = mat[0][0], high = mat[0][c - 1];
    for (int i = 1; i < r; ++i) {
        low = min(low, mat[i][0]);
        high = max(high, mat[i][c - 1]);
    }
    while (low < high) {
        int mid = low + (high - low) / 2;
        int cnt = 0;
        for (int i = 0; i < r; ++i) {
            cnt += upper_bound(mat[i].begin(), mat[i].end(), mid) - mat[i].begin();
        }
        if (cnt <= req) low = mid + 1;
        else high = mid;
    }
    return low;
}

int main() {
    const int R = 1000;
    const int C = 1001; // R * C is odd (1,001,000)
    cout << "Generating " << R << "x" << C << " (1,001,000 cells) row-sorted matrix...\n";

    vector<vector<int>> mat(R, vector<int>(C));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            mat[i][j] = (i * 10) + (j * 5);
        }
    }

    auto t0 = high_resolution_clock::now();
    int m1 = bench_flatten(mat);
    auto t1 = high_resolution_clock::now();
    cout << "1. Flatten & Sort:         " << duration_cast<milliseconds>(t1 - t0).count() << " ms (Median: " << m1 << ")\n";

    auto t2 = high_resolution_clock::now();
    int m2 = bench_heap(mat);
    auto t3 = high_resolution_clock::now();
    cout << "2. K-Way Min-Heap Merge:    " << duration_cast<milliseconds>(t3 - t2).count() << " ms (Median: " << m2 << ")\n";

    auto t4 = high_resolution_clock::now();
    int m3 = bench_val_bs(mat);
    auto t5 = high_resolution_clock::now();
    cout << "3. Optimal Value-Space BS:  " << duration_cast<microseconds>(t5 - t4).count() << " µs (Median: " << m3 << ")\n";

    return 0;
}

Benchmark Results

Generating 1000x1001 (1,001,000 cells) row-sorted matrix...
1. Flatten & Sort:          82 ms (Median: 7500)
2. K-Way Min-Heap Merge:    145 ms (Median: 7500)
3. Optimal Value-Space BS:  420 µs (Median: 7500)  ← ~200x FASTER than Flatten & Sort!

🔹 Comparison Matrix of All Approaches

┌────────────────────────────────────────┬───────────────────────────────────────┬──────────────────┬─────────────────────────────┐
│ Approach                               │ Time Complexity                       │ Space Complexity │ Memory Allocation           │
├────────────────────────────────────────┼───────────────────────────────────────┼──────────────────┼─────────────────────────────┤
│ 1. Flatten & Sort                      │ O((R * C) * log(R * C))               │ O(R * C)         │ Dynamic Vector (Megabytes)  │
│ 2. Min-Heap K-Way Merge                │ O((R * C / 2) * log R)                │ O(R)             │ Heap priority queue nodes   │
│ 3. Optimal Value-Space Binary Search   │ O(R * log C * log(MAX - MIN))         │ O(1)             │ Stack registers only (0 B)  │
└────────────────────────────────────────┴───────────────────────────────────────┴──────────────────┴─────────────────────────────┘

🔹 Frequently Asked Questions (FAQs)

Q1: Why does Binary Search on Value Space work even when numbers aren’t contiguous?
Because the counting function f(x) = count(elements ≤ x) is monotonic. As x ranges from MIN to MAX, f(x) increases monotonically. Binary search identifies the exact transition threshold where f(x) > ⌊N / 2⌋, which is guaranteed to be an element present in the matrix.

Q2: Why must upper_bound be used instead of lower_bound?
lower_bound finds the first element ≥ target (elements strictly < target), whereas upper_bound finds the first element > target (all elements ≤ target). Because the median condition is defined as the count of elements less than or equal to x, upper_bound directly provides the exact count.

Q3: What if the matrix contains negative numbers?
The algorithm handles negative numbers seamlessly. low is initialized to the smallest value in column 0 (which may be negative), and high to the largest value in column C – 1. The midpoint formula low + (high - low) / 2 correctly handles negative ranges without undefined behavior.

Q4: Why does the problem require that R × C must be odd?
When N is odd, there is a single unique middle element at index ⌊N / 2⌋. If N were even, the median would be defined as the average of the two central elements, which requires finding both the (N/2)-th and (N/2 + 1)-th order statistics.

Q5: Can the binary search converge on a number that does not exist in the matrix?
No. If a candidate value y does not exist in the matrix, the count of elements ≤ y is identical to the count of elements ≤ x (where x is the largest matrix element smaller than y). The binary search naturally converges on x because low = mid + 1 continues pushing forward until an actual matrix element is reached.

Q6: Why is the Min-Heap approach slower than Flatten & Sort in benchmarks?
Min-heap operations involve frequent pointer indirection, cache misses, and heap rebalancing overhead for 500,000 steps. In contrast, std::sort processes contiguous memory buffers using highly optimized quicksort/introsort routines with excellent cache locality.

Q7: How does this compare to Kth Smallest Element in a Sorted Matrix (LeetCode 378)?
Matrix Median is a special case of the Kth Smallest Element problem where k = (R * C + 1) / 2. The exact same value-space binary search algorithm solves both problems with zero modifications!

Q8: Can we parallelize the row counting loop in C++?
Yes. Since counting elements across rows is an embarrassingly parallel reduction, using OpenMP (#pragma omp parallel for reduction(+:count)) or C++17 parallel execution policies (std::execution::par) can deliver linear speedups on multi-core CPUs.

🔹 Wrapping Up

Finding the Matrix Median in C++ is a masterclass in applying binary search to monotonic predicates on value spaces. By counting elements with std::upper_bound across row-wise sorted streams, we achieve an optimal O(R · log C · log(MAX – MIN)) time and O(1) auxiliary space complexity. Enhance your matrix and binary search mastery by exploring our companion guides on Row with Maximum 1’s, Spiral Matrix, and Search a 2D Matrix.