45. Common Elements in All Rows of a Matrix

Given an r x c matrix, print the distinct values that appear in every single row (in any order, space-separated). If no value appears in all rows, print 'None'.

Input: The first line contains r and c, the matrix dimensions. The next r lines each contain c space-separated integers. Output: Print the distinct values common to every row, space-separated in any order; print 'None' if there are none.

1 <= r, c <= 1000

The moment the running candidate set becomes EMPTY partway through processing the rows, you can stop early and immediately report 'None' - there's no need to keep checking further rows once no candidates remain.

Find every value that appears in EVERY single row of a matrix, at least once per row. Brute force: For every distinct value in the first row, scan every OTHER row directly checking if it's present - this costs O(rows * cols) per candidate value, potentially slow if there are many distinct candidates to check. Optimised: Maintaining a running SET (progressively shrinking via intersection with each new row) means you only ever have to check candidates that have survived every row SO FAR against the current row - since the candidate set only shrinks or stays the same, the total work across all rows stays proportional to the matrix's total size.

Use one shared hash map from value to how many distinct rows that value has appeared in so far. For each row, first collect its own distinct values to avoid double-counting a value that appears multiple times within the same row, then increment that value's counter in the shared map by exactly one per row. After processing all r rows, any value whose counter equals r appeared in every row and belongs in the answer; if none do, print 'None'. This performs the equivalent of the intersection in a single combined pass with one shared structure instead of building and repeatedly intersecting r separate sets. Time: O(r*c) Space: O(c)

Convert each row into a hash set of its distinct values. Start with the first row's set as the current running intersection, then for each subsequent row's set, keep only the values also present in that row's set, removing anything from the running intersection not found there. After processing all rows, whatever remains in the running intersection is exactly the set of values common to every row. Time: O(r*c) Space: O(c)

For each distinct value appearing in the first row, scan every other row completely to check whether that value also appears somewhere in it, adding it to the result only if it is found in all remaining rows. Repeating a full linear scan of a row for every candidate value from the first row means the work multiplies together across rows and candidates. Time: O(r * c^2) Space: O(c)

1. Build a set of the DISTINCT values appearing in the very first row. 2. For every subsequent row, keep only the values from your current running set that ALSO appear somewhere in this new row (a running intersection). 3. After processing every row, whatever remains in the running set is common to all rows.

Time: O(rows * cols) - each cell of the matrix is examined a small, constant number of times overall. Space: O(cols), for the running set of candidate common values (bounded by the number of distinct values in any single row).

r = 1 (every distinct value in that single row trivially qualifies); no value shared across all rows (print 'None'); duplicate values within a row that must not be double-counted; and r = c = 1000 (largest, confirming the running-intersection approach is efficient).

Be ready to explain why starting from the FIRST row's distinct values (rather than trying to check all rows simultaneously from scratch) is a natural, efficient starting point - it immediately narrows the candidate pool to a manageable, bounded size before any further intersection work begins.