Make each element equal to its neighbouring element which is maximum in a matrix

Question

I have a matrix and I want to make each of its element equal to the maximum of its neighbouring element and each time I increase number of counts till all the elements in the matrix becomes equal to the maximum element of the initial matrix. Note that this increase in element will happen simultaneously for each element.

For example:

1 2 2 1
1 1 2 1
2 2 3 4

1st time:

2 2 2 2
2 3 4 4
2 3 4 4

2nd time:

3 4 4 4
3 4 4 4
3 4 4 4

3rd time:

4 4 4 4
4 4 4 4
4 4 4 4

So, answer would be 3.

What I've tried:

#include<bits/stdc++.h>
using namespace std;
int main()
{
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int t,i,j,k,n,m;
 cin>>t;
 while(t--)
 {
 cin>>n>>m;
 long int a[n+2][m+2],maxi[n][m],ma=0,counti=0;
 int flag[n][m];
 for(i=0;i<n+2;i++)
 {
 for(j=0;j<m+2;j++)
 {
 if(i==0 || j==0 || i==n+1 || j==m+1)
 {
 a[i][j]=0;
 continue;
 }
 cin>>a[i][j];
 flag[i][j]=0;
 if(a[i][j]>ma)
 ma=a[i][j];
 }
 }
 for(i=1;i<n+1;i++)
 {
 for(j=1;j<m+1;j++)
 {
 int myints[] = {a[i][j+1],a[i][j-1],a[i-1][j],a[i+1][j],a[i+1][j+1],a[i+1][j-1],a[i-1][j+1],a[i-1][j-1]};
 maxi[i-1][j-1]= *max_element(myints,myints+8);
 if(maxi[i-1][j-1]<a[i][j])
 maxi[i-1][j-1]=a[i][j];
 if(a[i][j]==ma)
 counti++;
 }
 }
 if(counti==m*n)
 {
 cout<<"0"<<endl;
 continue;
 }
 int time=0;
 while(counti!=m*n)
 {
 counti=0;
 for(i=1;i<n+1;i++)
 {
 for(j=1;j<m+1;j++)
 {
 a[i][j]=maxi[i-1][j-1];
 if(a[i][j]==ma)
 {
 counti++;
 }
 }
 }
 for(i=1;i<n+1;i++)
 {
 for(j=1;j<m+1;j++)
 {
 int myints[] = {a[i][j+1],a[i][j-1],a[i-1][j],a[i+1][j],a[i+1][j+1],a[i+1][j-1],a[i-1][j+1],a[i-1][j-1]};
 maxi[i][j]= *max_element(myints,myints+8);
 }
 }
 time++;
 }
 cout<<time<<endl;
 }
}

The variables I have used are badly used and make you uneasy to read the code but I used them for my comfort so please don't point out minor mistakes.

Also, I know that using namespace std and including bits/stdc++.h are also bad practices, so please avoid them and focus on the problem here.

The problem is my time complexity to traverse is going too high. So, I want the answer with least time complexity as possible. Any pseudocode or logic explanation with reduced complexity would be sufficient.

Answer 1

please avoid them and focus on the problem here.

The problem is my time complexity to traverse is going too high.

No, your variable naming and abuse of C++ features is also a problem. For the most part your code is structured OK. It's moderately understandable, but fixing those things could make it really easily understandable. You do need to think about these things, not just so others can read your code, but so your future self can understand it, too.

Naming

Your variable names are not clear at all. I'm all for 1-letter variable names for loop control variables like i and j. But you've gone too far for anyone who wants to understand your code. It's not hard to change t to numMatrixes or if you really need short names, numMats. (Also, you didn't really describe that there was more than one matrix in your description. Did I understand that correctly?) n and m should be numRows and numColumns (or numCols).

Your actual matrixes should have better names, too. a should be paddedMatrix. maxi is better than your other names. ma should be maxEntry. counti is also ambiguous. What is it counting? It looks to me like it's counting the number of values that match the maximum value, so maybe call it matchCount or numMatches?

Whitespace

This code is very dense and difficult for a human to parse. I recommend using far more whitespace in your code. For example, I'd put spaces before and after every operator. That means =, ==, +, -, >>, etc.

Also, you should add some empty lines between blocks of functionality from time to time. For example, between the for loops, the if statements, andwhile loops. Even better would be to...

Use Functions

I see 3 things happening in the outer while loop. You're:

1. Reading in the input values for the array (while finding the maximum element)
2. Replacing each element in the array with the maximum of its neighbors
3. Finding the number of times you need to do that until you've filled the array with the maximum values

Each of those things should be a separate function.

Careful with continue

The continue keyword is essentially a goto. As such, it can make code flow harder to understand than it needs to be. I don't think your use of it adds anything, so I'd remove it in favor of using else clauses in your ifs. For example in the first inner loop, I'd change it to look like this:

 if(i == 0 || j == 0 || i == n + 1 || j == m + 1)
 {
 a[i][j] = 0;
 }
 else
 {
 cin >> a[i][j];
 flag[i][j] = 0;
 if(a[i][j] > ma)
 {
 ma = a[i][j];
 }
 }

It does the exact same thing, but is much clearer. Now I don't have to think, "does the continue apply to the inner or outer loop?" I just automatically understand what happens when the code runs.

I'd do the same thing with the other continue.

Avoid magic numbers

You have a couple of uses of the number 8. What does it represent? Does it need to change if you change anything else in the code? It appears that you're trying to use the number of values in the myints array. If that's what you want, you should use that directly. You can write it as:

const int numMyInts = sizeof(myints) / sizeof(myints[0]);

Stop Abusing C++

You say you know that using namespace std is bad, but you do it anyway. My compiler can't even find bits/stdc++.h, so I had to include the 2 headers you actually need: algorithm and iostream.

Errors and Warnings

My compiler (llvm) won't actually compile your code. It points out the error you have in the myints array. It's only big enough to hold ints, but you're trying to copy long ints into it. This might work for small values, but not for values that exceed the size of int.

You have an unused variable k. You should remove it.

Your algorithm fails for negative values.

Performance

In order to understand what's causing your code to be slow, you should profile it. That will tell you for certain where the slowdown is. You will often be surprised by the answer.

My first guess (and it's best to test it rather than guessing, because guesses are often wrong) is that it's costing you a lot of time copying the neighboring elements into the myints array. I wonder if you could avoid the copies by using some pointer arithmetic? Finding the max of several values is simple enough that you probably don't need to call max_elements(). You could manually unroll the loop into something like this:

const long int kRowStride = numCols - 2; // Number of elements to skip to get to the right element in the next row
long int *nextInt = &a[ i - 1 ][ j - 1 ];
long int currentMax = *nextInt;
nextInt++;
currentMax = std::max(currentMax, *nextInt);
nextInt++;
currentMax = std::max(currentMax, *nextInt);
nextInt += kRowStride;
//... etc.for the remaining 2 rows

It's possible that there's some matrix operation that will do the equivalent of your search in fewer steps. I don't remember enough matrix math to know off the top of my head whether that's true or not, but often the best optimization is not to optimize your algorithm, but to find a better algorithm. So I'd explore that route, as well.

• Alfran: Thank you for pointing out these mistakes. I will keep that in mind in future. One point i would like to mention is "my algorithm fails for negative values", yes it does .But my constraints are all positive integers in the problem and another is that your heading of abusing c++ is improper because i mentioned that it's bad and i am using namespace std because i knew that i am not going to use any other library in my code. I am not abusing c++. Still, Thanks again for your effort to teach me these lessons.