Matrix intro

Hackerrank problems involving matrixes.

What is a Matrix

Its a grid!

Its got a top, right, bottom, left! What more do you want!??!?! Its a matrix!

-1. Hourglass Sum ::1:: - Easy

Topics: Array, Matrix, Simulation

Intro

Given a 6x6 2D integer array arr, an hourglass is a subset of values with indices falling in this pattern:
a b c
  d
e f g
There are 16 hourglasses in a 6x6 array. The hourglass sum is the sum of the values in an hourglass. Calculate the hourglass sum for every hourglass in arr, then return the maximum hourglass sum.

Example Input	Output
arr = [[1,1,1,0,0,0],[0,1,0,0,0,0],[1,1,1,0,0,0],[0,0,2,4,4,0],[0,0,0,2,0,0],[0,0,1,2,4,0]]	19
arr = [[-9,-9,-9,1,1,1],[0,-9,0,4,3,2],[-9,-9,-9,1,2,3],[0,0,8,6,6,0],[0,0,0,-2,0,0],[0,0,1,2,4,0]]	28

Constraints:

arr.length == 6

arr[i].length == 6

-9 ≤ arr[i][j] ≤ 9

Given a fixed 6x6 matrix, slide a 3x3 hourglass-shaped stencil (top row, middle center cell, bottom row) across every valid top-left starting position (rows 0-3, cols 0-3), sum the 7 cells covered by the stencil at each position, and return the largest sum found.

Pseudocode

  oh! pseudocode hasn't been written yet, try another card! :)

Solution 1: Fixed-Window Stencil Scan Over 4x4 Valid Positions - Basic DSA/Matrix

    def hourglassSum(self, arr: List[List[int]]) -> int:

        # An hourglass covers a 3x3 footprint but only 7 of the 9 cells:
        # a b c
        #   d
        # e f g
        # (the two side-middle cells, matrix[r+1][c] and matrix[r+1][c+2], are excluded)

        # Fixed 6x6 grid:
        # Since the grid is always 6 rows by 6 cols, the top-left corner
        # of an hourglass can only start at rows 0-3 and cols 0-3
        # (any further and the hourglass would run off the grid).
        # This gives exactly 4 * 4 = 16 possible hourglasses, matching the problem statement.

        # Hourglass Ex:
        # [ 2  4  4]
        # [   2   ]   ==> sum = 2+4+4 + 2 + 1+2+4 = 19
        # [ 1  2  4]

        # Note:
        # 1. Iterate every valid top-left position (row, col) in range 0-3
        # 2. At each position, sum the 3 top cells, the 1 middle cell,
        #    and the 3 bottom cells
        # 3. Track the running maximum across all 16 hourglasses

        # Track the best sum seen so far.
        # Start at -inf since all values could be negative
        # (constraints allow -9 to 9), so 0 is not a safe default.
        max_sum = float('-inf')

        # Valid starting corners:
        # row+2 and col+2 never exceed index 5 (last valid index)
        # since row, col only range 0-3
        # tc: O(1) — fixed 16 iterations regardless of input (grid size is constant)

        for row in range(4):
            for col in range(4):
                top    = arr[row][col] + arr[row][col+1] + arr[row][col+2]
                middle = arr[row+1][col+1]
                bottom = arr[row+2][col] + arr[row+2][col+1] + arr[row+2][col+2]

                current_sum = top + middle + bottom
                max_sum = max(max_sum, current_sum)


        # overall: tc O(1) (constant 6x6 input) / O(n^2) if generalized to n x n grid
        # overall: sc O(1) — no extra structures beyond a running max
        return max_sum

Hackerrank: Matrix