We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Arrays
  4. 2D Array - DS
  5. Discussions

2D Array - DS

  • michaelchen0611
     + 0 comments

    Time complexity: O(n^2) Space complexity: O(1)

    Of course, one can assign the coordination of the 2-D array to compute hourglasses value directly.

    int compute_hourglasses(int** arr, int start_row, int start_cloumn){
    int sum = 0;
    for (int i = start_row-1; i<=start_row+1; i++){
        for (int j = start_cloumn-1; j <= start_cloumn+1; j++){
            sum += arr[i][j];
        }
    }
    sum -= (arr[start_row][start_cloumn-1] + arr[start_row][start_cloumn+1]);
    return sum;
}

int hourglassSum(int arr_rows, int arr_columns, int** arr) {
    int start_row = 1, start_cloumn = 1;
    int end_row = arr_rows-1, end_column = arr_columns-1;
    int max_res = compute_hourglasses(arr, start_row, start_cloumn);
    for (int i = start_row; i<end_row; i++){
        for (int j = start_cloumn; j< end_column; j++){
            int temp = compute_hourglasses(arr, i, j);
            if (temp > max_res) max_res = temp;
        }
    }
    return max_res;
}