Day 7 of 60 Days of DSA: 2D Subarray sum & Search Element

Breaking down 2D matrix traversal and submatrix sum optimisation

Concept 1: Search Element

Problem:

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

Example:
Input 1:-

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

Input 2:-

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

Output:

Output 1:- 1011

Output 2:- 2019

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

Brute Force

The most straightforward approach is to check each element of the array, compare all elements with the given element, and if a match is found, then calculate the value.

Time complexity- Using the above approach time complexity of this solution will come as O(n*n) as we’re checking all the elements of the matrices once.

Let’s look at the optimised approach for solving this problem.

Optimised Approach:

Let’s look at the problem once more, as it clearly mentions that given array is sorted in non-decreasing order.

It means if we go down in the matrix number is always increasing and if we go backwards in the row, the number is always decreasing.

So, if we stand at the top right corner of the matrix, we can always compare the number with B and take a decision whether to go down or left.

Example- if B is 7, then we go down, and if B is 2, then there is no point in going down; we have to go left. Using this approach, we only have to traverse n+m elements at max.

Solution:

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;
}

Why This Approach Is Efficient

Time Complexity: O(N + M)
Each step moves either left or down, never revisiting a cell.
Space Complexity: O(1)
No extra data structures are used.
Fully utilizes the sorted matrix property, unlike brute forc

Problem 2: 2D Subarray Sum

We have already solved a similar problem in the series for a 1D array. If you haven’t encountered that problem, please do so here to understand the concept clearly.

Problem:

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

Example:

Input 1:

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

Input 2:

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

Example Output

Output 1: 16

Output 2: 40

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

We’ll directly look at the optimised approach, as in brute force will find all submatrices, and the time complexity for the same is very high O(N3×M3).

Optimised Approach: Contribution Technique

Q. What is the contribution technique?

A. Finding how many times an element is contributing to the total answer.

Similarly, we’ll find how many times a number will appear in all the submatrices and include the number of times in the total answer.

Let’s first have a basic understanding through a 1D array, and then we’ll proceed to a 2D array

1D Case — Understanding the Core Idea

Consider an array:

A = [1, 2, 3, 4]

Let’s find how many subarrays include a particular element (say A[i]).

Step 1: Count how many subarrays include A[i]

For index i (0-based) and total length n:

Left choices (start point):

Subarray can start anywhere from index 0 to i

→ number of choices = i + 1

Right choices (end point):

Subarray can end anywhere from index i to n — 1

→ number of choices = n — i

So total subarrays including A[i] = [ (i + 1) * (n — i) ]

Example:

For A = [1, 2, 3, 4], i = 1 (element = 2)

[ (1 + 1) * (4–1) = 2 * 3 = 6 ]

That matches the list: [1,2], [1,2,3], [1,2,3,4], [2], [2,3], [2,3,4]

Step 2: Compute total contribution

If each subarray’s sum contributes A[i] once for each occurrence,

then total contribution of `A[i]` =

[ A[i] * (i + 1) * (n — i) ]

Example:

For element 2 → contribution = 2 * 6 = 12.

2D Case — Extending the Same Idea

Now consider a 2D matrix:

Let’s find the contribution of each element (say, element at position `(i, j)`).

Step 1: Count submatrices that include (i, j)

Each submatrix is defined by:

top-left corner (r1, c1)
bottom-right corner (r2, c2)

where `r1 ≤ i ≤ r2` and `c1 ≤ j ≤ c2`

So:

Possible top-left corners:
Row choices: `i + 1` (from 0 to i)
Column choices: `j + 1` (from 0 to j)

→ total = (i + 1) * (j + 1)

Possible bottom-right corners:
Row choices: `n — i` (from i to n-1)
Column choices: `m — j` (from j to m-1)

→ total = (n — i) * (m — j)

Therefore, total submatrices including (i, j) =[ (i + 1) * (j + 1) * (n — i) * (m — j) ]

Step 2: Compute contribution

Each submatrix sum includes A[i][j] once for each submatrix containing it,

so contribution =[ A[i][j] * (i + 1) * (j + 1) * (n — i) * (m — j) ]

Example:

Take element 5 at (1, 1) (0-based) in 3x3 matrix

[ (1 + 1) * (1 + 1) * (3–1) * (3–1) = 2 * 2 * 2 * 2 = 16 ]

So 5 appears in 16 different submatrices.

Total contribution of 5 = 5 * 16 = 80.

Summary of Formulae

NOTE- Refer to notes for more clarity Page number- 5. Notes on github

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;
}

That’s it for Day 7🎯
You explored 2D matrix fundamentals, including searching for an element in a sorted matrix using linear traversal and efficiently calculating the sum of all submatrices with the contribution technique — both highly relevant for coding interviews at companies like Amazon, Google, and Microsoft.

Next up, we’ll continue strengthening problem-solving patterns with deeper applications of prefix sums and matrix traversal.

Stay consistent — see you in Day 8! 💪

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!