dsa/src/algorithms/arrays/2d-array-ds/2d-array-ds.ts at main · ragmha/dsa · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * Given a 6 x 6 2D Array, arr:
 *
 * 1 1 1 0 0 0
    0 1 0 0 0 0
    1 1 1 0 0 0
    0 0 0 0 0 0
    0 0 0 0 0 0
    0 0 0 0 0 0
    An hourglass in  is a subset of values with indices falling in this pattern in 's graphical representation:

    a b c
    d
    e f g
    There are  hourglasses in . An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in , then print the maximum hourglass sum. The array will always be .

    Example


    -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
    The  hourglass sums are:

    -63, -34, -9, 12,
    -10,   0, 28, 23,
    -27, -11, -2, 10,
    9,  17, 25, 18
    The highest hourglass sum is  from the hourglass beginning at row , column :

    0 4 3
    1
    8 6 6
 */

export function hourglassSum(arr: number[][]): number {
  let maxSum = -Infinity

  for (let i = 0; i < arr.length - 2; i++) {
    for (let j = 0; j < arr.length - 2; j++) {
      const sum =
        arr[i][j] +
        arr[i][j + 1] +
        arr[i][j + 2] +
        arr[1 + i][1 + j] +
        arr[2 + i][j] +
        arr[2 + i][1 + j] +
        arr[2 + i][2 + j]

      if (sum > maxSum) maxSum = sum
    }
  }

  return maxSum
}