search

ankitapuri / DSA-guide

Trying to cover important DSA
MIT License
49 stars 114 forks source link

Sum of All Sub Matrices of a Matrix #264

Open kiruba-r11 opened 3 years ago

kiruba-r11 commented 3 years ago

💥 Proposal

This is the most asked problem in interviews in 2-D Arrays. The brute force of this problem is having a time complexity of O(n ^ 6) and a Space complexity of O(1). Using extra space it can be optimized into a Time Complexity of O(n^4) and a Space Complexity of O(n ^ 2). But this can further be optimized into O(n^2) time and O(1) space. I will be implementing all three approaches to this problem because each one of them has special properties that can be used to solve other matrix-related problems.

Have you read the Contributing Guidelines on Pull Requests?

Yes

kiruba-r11 commented 3 years ago

@ankitapuri Please assign this to me, I will solve this in C++

kiruba-r11 commented 3 years ago

@ankitapuri There are three different approaches with different complexities to this problem. Each one of the approaches is useful for solving other problems related to submatrices. So, can I execute one of the approaches in this issue, and the other two in different issues, or do all three in this issue itself.

ankitapuri commented 3 years ago

@ankitapuri There are three different approaches with different complexities to this problem. Each one of the approaches is useful for solving other problems related to submatrices. So, can I execute one of the approaches in this issue, and the other two in different issues, or do all three in this issue itself.

All 3 in 1 please , bcoz I can take just 1 PR per issue