Day 71 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/2d-submatrix-sum-queries/1

2D Submatrix Sum Queries

Difficulty: Medium Accuracy: 73.76%

Given a 2D integer matrix mat[][] and a list of queries queries[][], your task is to answer a series of submatrix sum queries.
Each query is represented as a list [r1, c1, r2, c2], where:
• (r1, c1) is the top-left coordinate of the submatrix
• (r2, c2) is the bottom-right coordinate of the submatrix (both inclusive)
Your task is to return a list of integers, the sum of elements within the specified submatrix for each query.

*Examples: *
Input: mat[][] = [[1, 2, 3], queries[][] = [[0, 0, 1, 1], [1, 0, 2, 2]]
[1, 1, 0],
[4, 2, 2]]
Output: [5, 10]
Explanation:
Query 1 selects submatrix [[1, 2], [1, 1]] → sum = 5.
Query 2 selects submatrix [[1, 1, 0], [4, 2, 2]] → sum = 10.

Input: mat[][] = [[1, 1, 1], queries[][] = [[1, 1, 2, 2], [0, 0, 2, 2], [0, 2, 2, 2]]
[1, 1, 1],
[1, 1, 1]]
Output: [4, 9, 3]
Explanation:
Query 1 selects submatrix [[1, 1], [1, 1]] → sum = 4.
Query 2 selects submatrix [[1, 1, 1], [1, 1, 1], [1, 1, 1]] → sum = 9.
Query 3 selects submatrix [[1], [1], [1]] → sum = 3.
Constraints:
1 ≤ n × m, q ≤ 105
0 ≤ mat[i][j] ≤ 104
0 ≤ r1 ≤ r2 ≤ n - 1
0 ≤ c1 ≤ c2 ≤ m - 1

Solution:
class Solution:
def prefixSum2D(self, mat, queries):
n = len(mat)
m = len(mat[0])
ps = [[0]*m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            ps[i][j] = mat[i][j]
            if i > 0:
                ps[i][j] += ps[i-1][j]
            if j > 0:
                ps[i][j] += ps[i][j-1]
            if i > 0 and j > 0:
                ps[i][j] -= ps[i-1][j-1]

    ans = []
    for r1, c1, r2, c2 in queries:
        res = ps[r2][c2]
        if r1 > 0:
            res -= ps[r1-1][c2]
        if c1 > 0:
            res -= ps[r2][c1-1]
        if r1 > 0 and c1 > 0:
            res += ps[r1-1][c1-1]
        ans.append(res)

    return ans