c++ - Hourglass sum in 2D array

Question

We are given a (6*6) 2D array of which we have to find largest sum of a hourglass in it. For example, if we create an hourglass using the number 1 within an array full of zeros, it may look like this:

The sum of an hourglass is the sum of all the numbers within it. The sum for the hourglasses above are 7, 4, and 2, respectively.

I had written a code for it as follows.It is basically a competitive programming question and as I am new to the field,I have written the code with a very bad compplexity..perhaps so much that the program could not produce the desired output within the stipulated period of time.Below is my code:

    int main(){
    vector< vector<int> > arr(6,vector<int>(6));
    for(int arr_i = 0;arr_i < 6;arr_i++)
    {
      for(int arr_j = 0;arr_j < 6;arr_j++)
       {
        cin >> arr[arr_i][arr_j];
       }
    } //numbers input

    int temp; //temporary sum storing variable
    int sum=INT_MIN; //largest sum storing variable
    for(int i=0;i+2<6;i++) //check if at least3 exist at bottom
     { 
       int c=0; //starting point of traversing column wise for row

       while(c+2<6) //three columns exist ahead from index
        {  
          int f=0; //test case variable
          while(f!=1)  
          { //if array does not meet requirements,no need of more execution  

            for(int j=c;j<=j+2;j++)
             { //1st and 3rd row middle element is 0 and 2nd row is non 0.
               //condition for hourglass stucture                    
             if((j-c)%2==0 && arr[i+1][j]==0||((j-c)%2==1 && arr[i+1][j]!=0)
             //storing 3 dimensional subarray sum column wise               
             temp+=arr[i][j]+arr[i+1][j]+arr[i+2][j]; //sum storage 
             else
             f=1; //end traversing further on failure


              if(sum<temp)
              sum=temp;

              f=1;//exit condition
              }//whiel loop of test variable 

             temp=0; //reset for next subarray execution
             c++; /*begin traversal from one index greater column wise till 
                    condition*/
              }// while loop of c
        } 
      }       

          cout<<sum;

         return 0;
    }

This is my implementation of the code which failed to process in the time interval.Please suggest a better solution considering the time complexity and feel free to point out any mistakes from my side in understanding the problem.The question is from Hackerrank. Here is the link if you need it anyways: https://www.hackerrank.com/challenges/2d-array

Answer 1

The solution for your problem is:

#include <cstdio>
#include <iostream>
#include <climits>

int main() {
    int m[6][6];

    // Read 2D Matrix-Array
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            std:: cin >> m[i][j];
        }
    }

    // Compute the sum of hourglasses
    long temp_sum = 0, MaxSum = LONG_MIN;
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            if (j + 2 < 6 && i + 2 < 6) {
                temp_sum = m[i][j] + m[i][j + 1] + m[i][j + 2] + m[i + 1][j + 1] + m[i + 2][j] + m[i + 2][j + 1] + m[i + 2][j + 2];
                if (temp_sum >= MaxSum) {
                    MaxSum = temp_sum;
                }
            }
        }
    }
    fprintf(stderr, "Max Sum: %ld
", MaxSum);

    return 0;
}

The algorithm is simple, it sums all the Hourglasses starting of the upper left corner and the last 2 columns and 2 rows are not processed because it can not form hourglasses.