This content originally appeared on DEV Community and was authored by Ertugrul

Problems Solved:

#36 Valid Sudoku
#295 Find Median from Data Stream

This continues my daily series (Day 11: Hash Sets + Two Heaps). Today I focused on two classic data-structure problems: validating partial Sudoku boards with constant-size bookkeeping, and maintaining the running median of a data stream using two heaps.

What I Learned

For Valid Sudoku, the trick is to maintain three trackers: rows, columns, and 3×3 sub-boxes. Each new digit must not already exist in its row, column, or sub-box. Using either sets or boolean arrays makes duplicate detection simple.
For Median Finder, a single min-heap doesn’t work since we need access to the middle element(s). The efficient solution is to use two heaps: a max-heap (lower half) and a min-heap (upper half), rebalancing sizes after each insertion.
Key realization: correctness in both problems comes from enforcing constraints incrementally instead of computing from scratch.

#36 — Valid Sudoku

Python (Using sets)

class Solution:
    def isValidSudoku(self, board):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for r in range(9):
            for c in range(9):
                val = board[r][c]
                if val == ".":
                    continue
                b = (r // 3) * 3 + (c // 3)
                if val in rows[r] or val in cols[c] or val in boxes[b]:
                    return False
                rows[r].add(val)
                cols[c].add(val)
                boxes[b].add(val)
        return True

C++ (Using boolean arrays)

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool row[9][10] = {false};
        bool col[9][10] = {false};
        bool box[9][10] = {false};

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char ch = board[r][c];
                if (ch == '.') continue;
                int d = ch - '0';
                int b = (r/3)*3 + (c/3);
                if (row[r][d] || col[c][d] || box[b][d]) return false;
                row[r][d] = col[c][d] = box[b][d] = true;
            }
        }
        return true;
    }
};

Why it works: each filled cell is validated against its row, column, and box constraints immediately.

Time: O(81) ~ constant
Space: O(1)

#295 — Find Median from Data Stream

Python (Two heaps)

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap (store negatives)
        self.high = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.low, -num)
        if self.high and -self.low[0] > self.high[0]:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2.0

C++ (Two heaps)

class MedianFinder {
    priority_queue<int> low; // max-heap
    priority_queue<int, vector<int>, greater<int>> high; // min-heap
public:
    MedianFinder() {}

    void addNum(int num) {
        low.push(num);
        if (!high.empty() && low.top() > high.top()) {
            high.push(low.top());
            low.pop();
        }
        if (low.size() > high.size() + 1) {
            high.push(low.top());
            low.pop();
        } else if (high.size() > low.size()) {
            low.push(high.top());
            high.pop();
        }
    }

    double findMedian() {
        if (low.size() > high.size()) return low.top();
        return (low.top() + high.top()) / 2.0;
    }
};

Why it works: the two heaps divide numbers into lower and upper halves. Their tops represent the median candidates.

Time: O(log n) per insertion, O(1) median
Space: O(n)

Achievements

Valid Sudoku (Python & C++)

Median Finder (Python & C++)

Complexity Recap

Valid Sudoku: O(1) time & space (since 9×9 fixed grid)
Median from Data Stream: O(log n) time per add, O(1) findMedian

Join the Journey

I’m solving and documenting problems daily in both Python and C++, highlighting data-structure tricks, edge cases, and algorithmic reasoning. Follow along if you’re into problem solving and system design thinking.

Links

LinkedIn: https://www.linkedin.com/in/ertugrul-mutlu
GitHub Series: https://github.com/Ertugrulmutlu/leetcode-series