Day 6 of 60 Days DSA — 2D Arrays & Matrices Deep Dive

Finding Missing Numbers, Searching Smartly, and Understanding Contribution in Matrices

Day 6 of 60 Days DSA — 2D Arrays & Matrices Deep Dive

Finding Missing Numbers, Searching Smartly, and Understanding Contribution in Matrices

Welcome back to Day 7 of 60 Days of DSA!
Today, we’ll cover three powerful problems that test your array manipulation and matrix traversal skills:

First Missing Positive Integer
Search Element in Sorted Matrix
Sum of All Submatrices (Contribution Approach)

Each problem pushes your understanding of arrays and matrices one level deeper. Let’s get started. 🚀

Problem 1: First Missing Positive Integer

Problem Description

Given an unsorted integer array, A of size N. Find the first missing positive integer.

Note: Your algorithm should run in O(n) time and use constant space.

Problem Constraints

1 <= N <= 1000000

-109 <= A[i] <= 109

Input Format

First argument is an integer array A.

Output Format

Return an integer denoting the first missing positive integer.

Example Input

Input 1:

[1, 2, 0]

Input 2:

[3, 4, -1, 1]

Input 3:

[-8, -7, -6]

Example Output

Output 1:

Output 2:

Output 3:

Example Explanation

Explanation 1:

A = [1, 2, 0]
First positive integer missing from the array is 3.

Explanation 2:

A = [3, 4, -1, 1]
First positive integer missing from the array is 2.

Explanation 3:

A = [-8, -7, -6]
First positive integer missing from the array is 1.

Approach 1 — Using Extra Space (for understanding)

We create a new array map of size N, initialised with 0.

For every positive element A[i], mark its position in map as filled.
Then, traverse map — the first 0 at position i means that number i+1 is missing.

Example — [-1, 2,4,1]
Map — [1,2,3,4] => these should be actual positions
If We map the example array with our map array, don’t do anything for negative numbers=> [1,2,0,4]
3 is first missing positive

Code

function findMissing(A){
 let map = new Array(A.length).fill(0);
 for(let i=0; i<A.length ; i++){
 if(A[i] > 0){
 map[A[i]-1] = A[i];
 }
 }
 for(let i=0; i<A.length; i++){
 if(A[i] == 0) return i+1;
 }
}

🕒 Time Complexity — O(n)
📦 Space Complexity — O(n)

Approach 2 — Without Extra Space (In-place Swap)

Here’s the beauty — we can place each positive number in its correct index using swaps.

Logic:

If A[i] is positive and A[i] ≤ N, place it at index A[i] - 1.
Keep swapping until each valid element is at its correct position .
Then, scan the array — first position i where A[i] != i+1 gives your answer.

Code

function findMissingWithoutExtraSpace(A){
 for(let i=0; i<A.length; i++){
 // if A[i] is positive then it should be at its correct location
 let elAtCurrentLocation = A[i];
 let elAtDesiredLocation = A[A[i]-1];
 while(A[i] >0 && A[i]-1 != i && elAtCurrentLocation != elAtDesiredLocation){
 // swap A[i] location to i location
 swap(A, A[i]-1, i)
 elAtCurrentLocation = A[i];
 elAtDesiredLocation = A[A[i]-1];
 }
 }
 for(let i=0; i<A.length; i++){
 if(A[i]-1 != i) return i+1;
 }
 return A.length+1;
}

function swap(A, i, j){
 [A[i], A[j]] = [A[j], A[i]]
}

🕒 Time Complexity — O(n)
📦 Space Complexity — O(1)

✅ In-place cyclic sort pattern — a very powerful trick for array rearrangement problems!

Problem 2: Search Element in a Sorted Matrix

Problem Description

Given a matrix of integers A of size N x M and an integer B.In the given matrix every row and column is sorted in non-decreasing order. Find and return the position of B in the matrix in the given form:

If A[i][j] = B then return (i * 1009 + j)

If B is not present return -1.

Note 1: Rows are numbered from top to bottom and columns are numbered from left to right.
Note 2: If there are multiple B in A then return the smallest value of i*1009 +j such that A[i][j]=B.
Note 3: Expected time complexity is linear
Note 4: Use 1-based indexing

Problem Constraints

1 <= N, M <= 1000
-100000 <= A[i] <= 100000
-100000 <= B <= 100000

Input Format

The first argument given is the integer matrix A.
The second argument given is the integer B.

Output Format

Return the position of B and if it is not present in A return -1 instead.

Example Input

Input 1:-

A = [[1, 2, 3]
 [4, 5, 6]
 [7, 8, 9]]
B = 2

Input 2:-

A = [[1, 2]
 [3, 3]]
B = 3

Example Output

Output 1:-

Output 2:-

Example Explanation

Expanation 1:-

A[1][2] = 2
1 * 1009 + 2 = 1011

Explanation 2:-

A[2][1] = 3
2 * 1009 + 1 = 2019
A[2][2] = 3
2 * 1009 + 2 = 2020
The minimum value is 2019

Solution Approach

This is the “staircase search” problem.

Start from the top-right corner:

If A[i][j] == B → record it and move left to check smaller column indices.
If A[i][j] > B → move left.
If A[i][j] < B → move down.

This guarantees O(N + M) traversal.

Why move from the top left and not elsewhere?

We need to decide whether to move along a row (left or right) or along a column (up or down). Since the matrix is sorted both row-wise and column-wise, we can make an informed choice based on our position. If we start from the end (for example, the top-right or bottom-left corner), we can always compare values — the left-side value will be smaller (row-wise), and the value below will be greater (column-wise). This makes it easier to decide the direction to move in. So, if you want to make consistent decisions, start from one of these corners from where you can take a decision.

Code


function searchElement(A, B){
 let min = Number.POSITIVE_INFINITY;
 let rowLength = A.length;
 let colLength = A[0].length;
 let i = 0;
 let j=colLength-1;
 while(i<rowLength && j>=0){
 if(A[i][j] == B){
 let cal = ((i+1) * 1009 + (j+1));
 min = Math.min(cal, min);
 // console.log(i, j)
 j--;
 }
 else if(A[i][j] > B){
 j--;
 }else{
 i++;
 }
 }
 return min == Number.POSITIVE_INFINITY? -1: min;
}

🕒 Time Complexity — O(N + M)
📦 Space Complexity — O(1)

Problem 3: Sum of All Submatrices (Most Popular)

Problem Description

Given a 2D Matrix A of dimensions N*N, we need to return the sum of all possible submatrices.

Problem Constraints

1 <= N <=30

0 <= A[i][j] <= 10

Input Format

Single argument representing a 2-D array A of size N x N.

Output Format

Return an integer denoting the sum of all possible submatrices in the given matrix.

Example Input

Input 1:

A = [ [1, 1]
 [1, 1] ]

Input 2:

A = [ [1, 2]
 [3, 4] ]

Example Output

Output 1:

Output 2:

Example Explanation

Example 1:

Number of submatrices with 1 elements = 4, so sum of all such submatrices = 4 * 1 = 4
Number of submatrices with 2 elements = 4, so sum of all such submatrices = 4 * 2 = 8
Number of submatrices with 3 elements = 0
Number of submatrices with 4 elements = 1, so sum of such submatrix = 4
Total Sum = 4+8+4 = 16

Example 2:

The submatrices are [1], [2], [3], [4], [1, 2], [3, 4], [1, 3], [2, 4] and [[1, 2], [3, 4]].
Total sum = 40

Intuition — Think “Contribution”

Instead of generating all submatrices (which would be exponential),
we find how many times each element contributes to the final sum.

Step 1: Start with 1D Understanding

For an array [1, 2, 3, 4]:

Element A[i] appears in (i + 1) * (n - i) subarrays.

Example:
For A[1] = 2 → (1 + 1) * (4 - 1) = 6 → appears in 6 subarrays.

Total contribution = A[i] * (i + 1) * (n - i)

Step 2: Extend to 2D

For matrix element A[i][j] (0-based):

Top-left choices → (i + 1) * (j + 1)
Bottom-right choices → (n - i) * (m - j)

Total submatrices including A[i][j] =

(i + 1) * (j + 1) * (n - i) * (m - j)

Contribution =

A[i][j] * (i + 1) * (j + 1) * (n - i) * (m - j)

Code

function sumOfAllSubmatrices(A){
 let rowLength = A.length;
 let colLength = A[0].length;
 let contribution =0;
 for(let i=0; i<rowLength; i++){
 for(let j=0; j<colLength; j++){
 contribution += A[i][j]*(i+1)*(j+1)*(rowLength-i)*(colLength-j)
 }
 }
 return contribution;
}
console.log(sumOfAllSubmatrices([[1,1],[1,1]]))
console.log(sumOfAllSubmatrices([[1,2],[3,4]]))

🕒 Time Complexity — O(N²)
📦 Space Complexity — O(1)

Wrap-Up

✅ Problem 1: Taught in-place array reordering logic.
✅ Problem 2: Strengthened matrix traversal using binary direction logic.
✅ Problem 3: Introduced contribution technique — a powerful way to calculate aggregate values efficiently.

Every problem here builds a new intuition layer for your problem-solving toolkit.

🔥 Challenge for You

Try extending the sum of all submatrices problem to a 3D matrix —
Can you derive a similar contribution formula? 😉

Do you want to solve more with us?

Then follow this series and share your progress in the comments.

If the topics are difficult for you to understand, then you can refer to the notes on my GitHub.

At Dev Simplified, We Value Your Feedback 📊

👉 Follow us to not miss any updates.

👉 Have any suggestions? Let us know in the comments!

👉 Subscribe for free and join our growing community!