DSA: Arrays 2: Two Dimensional

17 min read

Arrays (2-Dimensional)

Complete Notes

Sorted-matrix search → submatrices → the contribution technique → first missing natural number

Contents

1. The Agenda (what this chapter covers)

2. Warm-Up: Revision Quiz

3. Search in a Row-wise + Column-wise Sorted Matrix

4. What Is a Submatrix and How to Uniquely Identify It

5. Sum of All Submatrices’ Sums — the Contribution Technique

6. Find the First Missing Natural Number

7. Doubt-Session Recap: Trapping Rain Water

8. One-Page Revision

1. The Agenda (what this chapter covers)

This chapter moves from 1-D arrays into 2-D arrays (matrices). Everything below is one connected chain — each problem sets up the tool the next one needs.

Revision quiz — five questions locking in the 1-D toolkit.
Search in a row-wise, column-wise sorted matrix.
What is a submatrix, and how can we uniquely identify it.
Sum of all submatrices’ sums → the contribution technique.
Find the first missing integer (natural number).

2. Warm-Up: Revision Quiz

Five quick checks on the previous chapter. The wrong options are worth reading too — each one names where that tool actually belongs.

Quiz 1 — Which algorithm is most efficient to find the maximum subarray sum?

Brute Force algorithm ✗
Kadane’s Algorithm ✓
Dijkstra’s Algorithm ✗ → belongs to graphs
Moore’s Voting algorithm ✗ → belongs to majority element

Quiz 2 — In maximum subarray sum, what does the ‘carry forward’ technique imply?

Using a stack to store elements ✗
Using recursion for sum calculation ✗
Continuously adding elements while maintaining the maximum sum ✓ → a single variable does the job
Using two pointers for sum calculation ✗

Quiz 3 — How can time complexity be optimized for multiple “increment from index i to the last index” queries on an array?

by using stack ✗
by using prefix sums ✓
by using recursion ✗
by using a queue ✗

Example from the board: arr = [1, 0, 1, 0, 0] → its prefix sum psum = [1, 1, 2, 2, 2].

Quiz 4 — What is the optimized time complexity for handling multiple range queries using the prefix sum technique?

O(Q + N) ✓
O(Q × N) ✗
O(Q²) ✗
O(N²) ✗

Why: Q iterations to apply the effect of the queries + N iterations to build the prefix sum → T.C. = O(N + Q).

Quiz 5 — In the rainwater trapping problem, what does the water stored over a building depend on?

the width of the building ✗
the height of the building ✗
the minimum of the maximum heights on either side of the building ✓
the total number of buildings ✗

(Section 7 revisits this with a full worked example from the doubt session.)

3. Search in a Row-wise + Column-wise Sorted Matrix

Problem. Given a row-wise and column-wise sorted matrix, find out whether an element K is present or not.

“Row-wise and column-wise sorted” means: every row increases left → right, and every column increases top → bottom. Working example (3 × 4):

	0	1	2	3
0	-5	-2	1	13
1	-4	0	3	14
2	-3	2	6	18

Sample queries: K = 13 → true; K = 2 → true; K = 15 → false.

3.1 Brute force — scan every cell

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (arr[i][j] == k) return true;

}

return false;

Total iterations = n × m. T.C. O(n × m), S.C. O(1). It never uses the sortedness — that’s the waste.

3.2 A first improvement — binary search on each row

Since every row is sorted, apply binary search on each row and try to find K. For a single row that is O(log n); with m rows the total iterations become O(m × log n). Better — but the matrix is sorted in two directions and we are still only using one.

3.3 The key question — which corner do we start from?

To use both sorted directions at once, stand on one cell and ask: if my cell is bigger than K, which direction can I safely discard? Test each corner:

Case	Starting corner	Test value	Verdict
Case 1	Top-left	K = 18	Ambiguous ✗ — K can be in the row OR in the column (both grow away from here).
Case 2	Bottom-right	K = −4	Ambiguous ✗ — same problem, K can be in the row OR in the column.
Case 3	Top-right	K = −2	Works ✓ — this cell is the MAX of its row and the MIN of its column, so every comparison points one exact way.
Case 4	Bottom-left	(dry run — TODO)	Conclusion from class: this starting point will also work (it is the mirror image of Case 3: min of its row, max of its column).

Board question: “Say we are at 1 and want to find 0, where should we move?” In the example matrix, 1 sits in the top row; 0 is smaller than 1, so move toward the left.

The top-right rule. Standing at mat[i][j] (started at top-right):

• mat[i][j] == K → we found the data → return true.

• mat[i][j] > K → discard this column, move toward left (j−−).

• mat[i][j] < K → discard this row, move toward down (i++).

Dry run — K = −1 (not present)

Start at (0,3) = 13: 13 > −1 → left; (0,2) = 1 > −1 → left; (0,1) = −2 < −1 → down; (1,1) = 0 > −1 → left; (1,0) = −4 < −1 → down; (2,0) = −3 < −1 → down → i = 3: out of the matrix → return false.

3.4 Pseudocode

boolean searchInRowColSortedMatrix(int[][] mat, int k) {

int n = mat.length; // rows

int m = mat[0].length; // cols

int i = 0;

int j = m - 1; // start: top-right corner

while (i < n && j >= 0) {

if (mat[i][j] == k) {

return true; // we found the data

} else if (mat[i][j] > k) {

j--; // discard column, move left

} else {

i++; // discard row, move down

}

return false;

}

T.C. O(n + m), S.C. O(1).

4. What Is a Submatrix and How to Uniquely Identify It

A submatrix is a rectangular block of contiguous cells inside a matrix. Working example (4 × 4), with one submatrix highlighted:

	0	1	2	3
0	1	2	3	4
1	5	6	7	8
2	1	7	5	9
3	3	0	6	2

The highlighted block is the submatrix with top-left (2,2) and bottom-right (3,3).

The four corners of any rectangle

TL → top left
TR → top right
BL → bottom left
BR → bottom right

To define a submatrix uniquely you need two opposite corners:

• Top-left + Bottom-right → the standard way.

• Top-right + Bottom-left → also works.

A single element can be a submatrix.
The complete matrix is also an example of a submatrix.

Reading TL/BR pairs on the example

TL	BR	What it selects
(0, 0)	(1, 2)	the 2 × 3 block: rows 0–1, cols 0–2
(1, 1)	(2, 2)	the 2 × 2 block: rows 1–2, cols 1–2
(1, 3)	(3, 3)	the 3 × 1 column block: rows 1–3, col 3
(1, 3)	(1, 3)	the single element 8 (TL = BR)

5. Sum of All Submatrices’ Sums — the Contribution Technique

Problem. Given a matrix of N rows and M columns, determine the sum of all the possible submatrices’ sums.

Working example (2 × 3):

	0	1	2
0	4	9	6
1	5	-1	2

5.1 Brute force — enumerate every submatrix

Every submatrix is one TL/BR pair. Enumerating all of them for the example:

Shape	Submatrices → sums
1 × 1	[4] → 4; [9] → 9; [6] → 6; [5] → 5; [−1] → −1; [2] → 2
1 × 2	[4, 9] → 13; [9, 6] → 15; [5, −1] → 4; [−1, 2] → 1
1 × 3	[4, 9, 6] → 19; [5, −1, 2] → 6
2 × 1	[4 / 5] → 9; [9 / −1] → 8; [6 / 2] → 8
2 × 2	[4, 9 / 5, −1] → 17; [9, 6 / −1, 2] → 16
2 × 3	the whole matrix → 25

total sum = 4 + 9 + 6 + 5 + (−1) + 2 + 13 + 15 + 4 + 1 + 19 + 6 + 9 + 8 + 8 + 17 + 16 + 25

= 166

Enumerating every submatrix and re-adding its cells is brutally repetitive — the same elements get added again and again. That repetition is exactly what the next idea exploits.

5.2 Flip the lens — contribution of each element

Instead of asking “what is each submatrix’s sum?”, ask: “how many submatrices does each element appear in?” If element e occurs in f submatrices, it contributes e × f to the grand total.

Element	Occurrence in all submatrices	Contribution
4	6	4 × 6 = 24
9	8	9 × 8 = 72
6	6	6 × 6 = 36
5	6	5 × 6 = 30
−1	8	(−1 × 8) = −8
2	6	2 × 6 = 12

Total = 24 + 72 + 36 + 30 − 8 + 12 = 166 — the same answer, no enumeration.

5.3 Counting the occurrences of (i, j)

A submatrix contains cell (i, j) exactly when its top-left corner is at-or-above-and-left of (i, j) and its bottom-right corner is at-or-below-and-right of it. So:

every valid TL lives in rows 0…i and columns 0…j — they are all top-lefts;
every valid BR lives in rows i…n−1 and columns j…m−1 — they are all bottom-rights.

Every TL pairs with every BR to make one distinct submatrix, so (exactly like counting pairs across two groups):

total pairs = count of TL × count of BR

Worked count 1 — an 8 × 10 grid, cell (i, j) = (3, 4)

TLs: rows 0…3 (4 rows) × cols 0…4 (5 cols) → count of TL = 20.
BRs: rows 3…7 (5 rows) × cols 4…9 (6 cols) → count of BR = 30.
count of submatrices = count of TL × count of BR = 20 × 30 = 600.

Worked count 2 — a 5 × 6 grid, cell (i, j) = (2, 3)

count of TL = 3 × 4 = 12; count of BR = 3 × 3 = 9; count of occurrence = 12 × 9 = 108.

Quiz — in a matrix of size 4 × 5, how many submatrices is (1, 2) part of?

count of occurrence = count of TL × count of BR = 6 × 9 = 54.

5.4 Generic dimensions — the frequency formula

One counting fact does all the work: the range [a to b] contains b − a + 1 elements.

Rows from 0 to i → [0, i] → i − 0 + 1 = (i + 1); cols from 0 to j → (j + 1).
Rows from i to n−1 → n − 1 − i + 1 = (n − i); cols from j to m−1 → (m − j).

count of TL = (i + 1) × (j + 1)

count of BR = (n − i) × (m − j)

freq. of (i, j) = count of TL × count of BR = ((i + 1) × (j + 1)) × ((n − i) × (m − j))

contribution of (i, j) = freq × mat[i][j]

5.5 Pseudocode

// n -> rows, m -> cols

total = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

topleft = (i + 1) * (j + 1);

bottomright = (n - i) * (m - j);

contribution = mat[i][j] * topleft * bottomright;

total += contribution;

}

return total;

T.C. O(n × m), S.C. O(1).

5.6 Verify the formula on the 2 × 3 example

freq = (i+1) × (j+1) × (n−i) × (m−j) with n = 2, m = 3:

Index	Element	Freq = (i+1)(j+1)(n−i)(m−j)	Contribution = freq × ele
0, 0	4	1 × 1 × 2 × 3 = 6	6 × 4 = 24
0, 1	9	1 × 2 × 2 × 2 = 8	8 × 9 = 72
0, 2	6	1 × 3 × 2 × 1 = 6	6 × 6 = 36
1, 0	5	2 × 1 × 1 × 3 = 6	6 × 5 = 30
1, 1	−1	2 × 2 × 1 × 2 = 8	8 × (−1) = −8
1, 2	2	2 × 3 × 1 × 1 = 6	6 × 2 = 12

Grand total = 166 — identical to the brute-force enumeration of 5.1, and to the occurrence table of 5.2. Same answer, three views. The formula wins because it needs one pass, no enumeration.

6. Find the First Missing Natural Number

First, the number families:

0 to n → whole numbers; 1 to n → natural numbers; (−∞ … −1, 0, 1, 2 … +∞) → integers.

Problem. Given an unsorted array of integers, find the first missing natural number.

Read a few by hand first — walk 1, 2, 3, … and stop at the first one the array does not have:

Array	Walk 1, 2, 3, …	Answer
[3, −2, 1, 2, 7]	1 ✓ 2 ✓ 3 ✓ 4 ✗	4
[−9, 2, 6, 4, −8, 1, 3]	1 ✓ 2 ✓ 3 ✓ 4 ✓ 5 ✗	5
[−2, 4, −1, −6, 3, 7, 8, 4, −2]	1 ✗	1
[1, 0, −5, −6, 4, 2]	1 ✓ 2 ✓ 3 ✗	3
[1, 2, 5, 6, 4, 3]	1–6 all ✓ 7 ✗	7
[−4, 8, 3, −1, 0]	1 ✗	1
[4, 2, 1, 3]	1–4 all ✓ 5 ✗	5

Quiz — In the array [5, 3, 1, −1, −2, −4, 7, 2], what is the first missing natural number?

1 ✓ 2 ✓ 3 ✓ 4 ✗ → answer = 4.

6.1 Approach 1 — check 1, 2, 3, … one by one

Step: check all the numbers from 1 till the answer is not encountered — for each, scan the array to see if it is present or not.

Example arr = [1, 3, 4, 7, 6, 2, 5]: num = 1 → present ✓; 2 ✓; 3 ✓; 4 ✓; 5 ✓; 6 ✓; 7 ✓; 8 → ✗ → 8 is my answer.

T.C. O(ans × n) → worst case ans grows like n → (n × n) ⇒ O(n²).

6.2 Two observations that box in the answer

Before optimizing, pin down what the answer can even be. For an array of size n:

The smallest possible answer is 1; the maximum possible answer is n + 1 (when the array is exactly 1…n, everything present).
A negative number can’t be the answer.
So the range of the answer for an n-size array is [1 to n + 1].
Can n + 2 be my answer? → No — it is out of range. (This makes n + 2 a safe “garbage value” — used twice below.)

6.3 Approach 2 — using sorting

n = 6, arr = [1, 0, −5, −6, 4, 2].

Make every out-of-bound value n + 2: [1, 0, −5, −6, 4, 2] → [1, 8, 8, 8, 4, 2].
Sort the array now: → [1, 2, 4, 8, 8, 8] (indices 0 1 2 3 4 5).
Check i + 1 == arr[i] or not — if yes, move ahead; if no, (i + 1) is missing. Here index 2 fails (expected 3, found 4) → (2 + 1) = 3 is missing.

T.C.: replace → n + sort → n log n ⇒ O(n log n).

S.C.: O(log n) — sorting space. Implement it → TODO.

6.4 Optimised solution — mark presence inside the array itself

Assumption to start with: all numbers are +ve (section 6.5 removes this). Range of answer: [1 to n + 1].

The trick. The array has n slots and the candidates are 1…n — so let index (v − 1) act as the register for value v. Seeing value v, mark its presence by making arr[v − 1] negative. Values outside 1…n can’t be marked (out of range) — and can’t be the answer anyway.

Marking walk-through — arr = [−6, −3, −9, −2, 8, −1, 4], n = 7, Ans ∈ [1, 8]

(Values are read by magnitude — the sign is only the mark.)

Read	Magnitude	Action
arr[0]	6	mark presence at (6 − 1)th index
arr[1]	3	mark presence at (3 − 1)th index
arr[2]	9	can’t mark it — out of range ✗
arr[3]	2	mark presence at (2 − 1)th index
arr[4]	8	can’t mark — out of range ✗
arr[5]	1	mark presence at (1 − 1)th index
arr[6]	4	mark presence at (4 − 1)th index

Now read the signs back: index 0 → 1 ✓, index 1 → 2 ✓, index 2 → 3 ✓, index 3 → 4 ✓, index 4 is positive → 5 ✗ → missing = 5.

Reading the final (post-marking) state — two more examples

[−8, −1, −4, −2, 6, −3]: indices 0–3 negative → 1 ✓ 2 ✓ 3 ✓ 4 ✓; index 4 positive → 5 ✗ → ans = 5.
[−4, −5, −6, −7, −4, −3, −1, 2]: indices 0–6 negative → 1…7 all ✓; index 7 positive → 8 ✗ → ans = 8.

The marking pass in code

for (int i = 0; i < n; i++) {

int ele = Math.abs(arr[i]);

if (ele >= 1 && ele <= n) {

index = ele - 1;

arr[index] = -1 * Math.abs(arr[index]);

}

6.5 How to deal with −ve numbers (and 0)?

If a value is 0 or −ve → make it n + 2. From 6.2, n + 2 can never be the answer and never marks anything — so replacing junk values with it is harmless. Do this as a first pass; after it, the assumption “all numbers are +ve” of 6.4 holds.

6.6 The full algorithm — three passes

// pass 1: neutralise 0 / negative values -> n itr

for (int i = 0; i < n; i++) {

if (arr[i] <= 0) {

arr[i] = n + 2;

}

// pass 2: mark presence at index (value - 1) -> n itr

for (int i = 0; i < n; i++) {

int ele = Math.abs(arr[i]);

if (ele >= 1 && ele <= n) {

index = ele - 1;

arr[index] = -1 * Math.abs(arr[index]); // stays -ve

}

// pass 3: first positive slot = missing number -> n itr

for (int i = 0; i < n; i++) {

if (arr[i] > 0) {

return i + 1;

}

return n + 1;

Total iterations = 3n ⇒ T.C. O(n), S.C. O(1).

6.7 The sign gotcha (from the doubt session)

Example under discussion: arr = [−4, −3, −1, −7, 2, 4, −3, 7], n = 8, ans ∈ [1, 9]. Why must the mark be written with Math.abs?

Wrong: arr[index] = −1 * arr[index]. If arr[index] is already marked (say −7), then −1 × (−7) = 7 — the mark flips back to positive and is destroyed ✗

Right: arr[index] = −1 * abs(arr[index]) = −1 × 7 = −7 — already-marked slots stay negative ✓

7. Doubt-Session Recap: Trapping Rain Water

Quiz 5 said it: the water on the roof of the i-th building depends on the minimum of the maximum heights on either side. As a formula:

water on roof of i-th building = min( lmax[i], rmax[i] ) − ht[i]

where lmax[i] = tallest building from the left up to i, and rmax[i] = tallest from the right. Worked example, heights = [7, 8, 4, 2, 5, 3, 7, 2, 4, 2]:

i	0	1	2	3	4	5	6	7	8	9
ht	7	8	4	2	5	3	7	2	4	2
lmax	7	8	8	8	8	8	8	8	8	8
rmax	8	8	7	7	7	7	7	4	4	2
min(lmax, rmax)	7	8	7	7	7	7	7	4	4	2
water	0	0	3	5	2	4	0	2	0	0

water = 0 + 0 + 3 + 5 + 2 + 4 + 0 + 2 + 0 + 0 = 16 units. (The board left the total box blank; 16 is simply the sum of the written terms.)

8. One-Page Revision

The whole chapter, compressed. If you remember this table, you can rebuild every section above.

Topic	The rule to remember
Staircase search	Row-wise + col-wise sorted matrix: start at the TOP-RIGHT (max of its row, min of its column). ==K found; >K discard column (j−−); <K discard row (i++). Bottom-left also works; top-left / bottom-right are ambiguous. T.C. O(n + m), S.C. O(1).
Submatrix identity	A submatrix is uniquely defined by two opposite corners: Top-left + Bottom-right (standard), or Top-right + Bottom-left. A single element counts; the whole matrix counts.
Counting occurrences	count of TL = (i + 1)(j + 1); count of BR = (n − i)(m − j); freq(i, j) = TL × BR. Root fact: [a to b] holds b − a + 1 elements; every TL pairs with every BR.
Contribution technique	Sum of all submatrices’ sums = Σ mat[i][j] × freq(i, j) over all cells — one pass, T.C. O(n × m), S.C. O(1). (2 × 3 example total: 166.)
First missing natural	Answer ∈ [1, n + 1]; n + 2 is safe garbage. Pass 1: values ≤ 0 → n + 2. Pass 2: for magnitude v in 1…n, set arr[v − 1] = −1 × abs(arr[v − 1]) — abs so existing marks survive. Pass 3: first positive index i → answer i + 1; none → n + 1. 3n itr, T.C. O(n), S.C. O(1).
Slower ladders	Missing natural: check-each-number O(ans × n) ⇒ O(n²); sorting way (junk → n + 2, sort, find i + 1 ≠ arr[i]) O(n log n).
Rain water	water[i] = min(lmax[i], rmax[i]) − ht[i]. Depends on the minimum of the maximum heights on either side.
1-D recap	Max subarray sum → Kadane’s; carry-forward = keep adding while maintaining the max in a single variable; range/increment queries → prefix sums, T.C. O(N + Q).