Code optimization | C++

Question

Hi

I have an input vector of string. Each string has space separated two integers. For example, vector<string> inp = {"1 2","2 5"}

This means there are two input as below:
1-> end row and 2-> end col
2->end row and 5->end col

for each input, we need to add one value to existing value from row 1 col 1 to end row and end col.

After all the operations, we need to find out max value count for entire matrix. We can assume matrix initial state as 0 for all cells.

Please find attached code for same. As it is brute force, I am getting Time Limit Exceeded. Can any one suggest the optimal approach? I will try to take it forward and implement then.

https://www.sololearn.com/en/compiler-playground/ch9iQ8W0DVGR

Thanks in advance...!

Answer 1

The TLE didn't happen for me when I tried both of your sample inputs within the code. Did you resolve the problem?

I see an opportunity to optimize the parsing code. Though it wouldn't make a measurable difference, at least the code would be more elegant:

//#include <string>
#include <sstream>
.
.
.
//size_t idx = one.find(' ');
//int row = stoi(one.substr(0, idx));
//int col = stoi(one.substr(idx + 1));
int row, col;
std::istringstream issOne(one);
issOne >> row >> col;

This is a faster way to extract row and col, as it eliminates creating intermediate substrings and function calls to stoi(). StringStream is optimized to parse and perform the int conversion.

Answer 2

You can use a technique called difference array (or 2D prefix sum) which allows you to efficiently perform range updates on a 2D grid. This will significantly more efficient than the brute force method, reducing the time complexity to O(N+R×C), where, 𝑁 is the number of input ranges, 𝑅 and 𝐶 are the number of rows and columns in the matrix, respectively.

Check this link: https://blog.garybricks.com/2d-prefix-array-and-2d-segment-tree-overview

Answer 3

" large number for rows and cols like 10 power 4 inputs and each has row and col as 10 power 4."

have you considered threading?

https://www.geeksforgeeks.org/maximum-in-a-2d-matrix-using-multi-threading-in-cpp/

Answer 4

I wanna make sure my algorithm is proper and efficient before I shift to threads

Answer 5

Thanks Brain for this tip. TLE will happen if input number is very large and when it has large number for rows and cols like 10 power 4 inputs and each has row and col as 10 power 4.

Answer 6

Hi `нттየ⁴⁰⁶,

Thanks for sharing this. I had this prefix sum approach in mind , but was confused to apply this in the current scenario.

As far as I know, for prefix sum method, we precompute everything based on static input of matrix or array. Query range is in variable and it does not modify the content of matrix or array.

How to make it work in current scenario? Here, each query input modifies the input values of matrix cells by 1.