# Project Euler: #11 - Largest product in a grid

### **Problem**

In the `20×20` grid below, four numbers along a diagonal line have been marked in yellow.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08  
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00  
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65  
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91  
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80  
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50  
32 98 81 28 64 23 67 10 **<mark>26</mark>** 38 40 67 59 54 70 66 18 38 64 70  
67 26 20 68 02 62 12 20 95 **<mark>63</mark>** 94 39 63 08 40 91 66 49 94 21  
24 55 58 05 66 73 99 26 97 17 **<mark>78</mark>** 78 96 83 14 88 34 89 63 72  
21 36 23 09 75 00 76 44 20 45 35 **<mark>14</mark>** 00 61 33 97 34 31 33 95  
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92  
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57  
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58  
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40  
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66  
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69  
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36  
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16  
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54  
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is `26 × 63 × 78 × 14 = 1788696`.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the `20×20` grid?

---

### **Problem Description**

In this problem, given the numbers are in a `20 x 20` grid.

We need to find the greatest product of `4` adjacent numbers.

The `4` adjacent numbers should be in the same direction - UP or DOWN or LEFT or RIGHT or DIAGONAL, in the grid.

The example is highlighted in yellow in the above grid.

---

### **Approach**

Well, this one hit me hard. I had two sleepless nights before solving this with the help of Scrimba and some comments in hacker rank.

We convert the given grid into an Array of arrays. We have an array of 20 items and each item is again an array of 20 numbers.

Then, we loop through the array horizontally, vertically and diagonally.

I have linked the Scrimba video [here](https://scrimba.com/learn/projecteuler/largest-product-in-a-grid-cg3reDA4).

---

### **Solution**

```javascript
const grid = [
    [8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8],
    [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0],
    [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65],
    [52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91],
    [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
    [24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
    [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
    [67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21],
    [24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
    [21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95],
    [78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92],
    [16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57],
    [86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
    [19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40],
    [4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
    [88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
    [4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36],
    [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16],
    [20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54],
    [1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48]
];

function largestGridProduct(arr) {
    let maxProduct = 0;

    const maxProductChecker = n => {
        if (n > maxProduct) {
            return maxProduct = n;
        }
    }

    for (let r = 0; r < arr.length; r++) {
        for (let c = 0; c < arr.length; c++) {
            let currProduct = 0;
            const limit = arr.length - 3;

            // Horizontal Check - Left/Right adjacent numbers 
            if (c < limit) {
                currProduct = arr[r][c] * arr[r][c + 1] * arr[r][c + 2] * arr[r][c + 3];
                maxProductChecker(currProduct);
            }

            // Verticle Check - Up/Down adjacent check
            if (r < limit) {
                currProduct = arr[r][c] * arr[r + 1][c] * arr[r + 2][c] * arr[r + 3][c];
                maxProductChecker(currProduct);
            }

            // Right Diagonal check
            if (c < limit && r < limit) {
                currProduct = arr[r][c] * arr[r + 1][c + 1] * arr[r + 2][c + 2] * arr[r + 3][c + 3];
                maxProductChecker(currProduct);
            }

            // Left Diagonal Check
            if (c >= 3 && r < limit) {
                currProduct = arr[r][c] * arr[r + 1][c - 1] * arr[r + 2][c - 2] * arr[r + 3][c - 3];
                maxProductChecker(currProduct);
            }
        }
    }

    console.log(maxProduct);
    return maxProduct;
}

largestGridProduct(grid);
```

You can find my solution on GitHub [11](https://github.com/sansk/project-euler-solutions-javascript/tree/main/11).

This particular solution was executed in Hacker rank without failing a single test case.

If you have another or a better solution, please leave it in the comments below.

For the other Project Euler Solutions, please follow the series [**Project Euler Solutions in JS.**](https://theintrovertcoder.hashnode.dev/series/project-euler)

Thank you!