Project Euler 11: Largest product in a grid

Largest product in a grid

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

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 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 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?

Official Problem

Solution Approach

In this problem of the Largest product in a grid, we are supposed to find the product of the diagonal numbers which is the largest.

We are given a 2D grid of numbers from which we have to find the largest product of diagonal. To achieve this we can iterate through each element and find out the product of the number in all directions (up, down, left, right, or diagonally) keeping the selected element at the pivot. Suppose, we have element “a” we have to consider every pattern in which “a” appears as the first element. We can keep this product in intermediate variables. These intermediate variables need to be checked with a global product which will also be the Largest product in a grid. Edge cases need to be handled which can appear for elements at the periphery of the 2D array.

The time complexity of this approach is O(N²) as we iterate through all elements of the 2D array once for computation. We need space to store intermediate products and the final largest product in a grid but that will be constant. Hence the space complexity is O(1).

Coming to the code of this approach, we will have to initialize a variable with the value -1 which will store the maximum value. Then we need to iterate through the matrix, one element at a time. We find the product taking it as the main element. The product part can be modularised in a new method. Similarly, the bounds can also be modularised using a method. We find the 4 products in all directions (up, down, left, right, or diagonally), while changing the value of max if there is any product greater than the max variable’s value. In the end, we return the max’s value which will be our answer.

Solution Code

Java Solution

Python Solution

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding.