Problem 11: Largest Product in a Grid

Mathematical Development

Definitions

Definition 1. For a direction vector $(d_r, d_c) \in \{(0,1),(1,0),(1,1),(1,-1)\}$, define the $(d_r,d_c)$-product of length $\ell$ starting at $(i,j)$ as

provided all indices $i + kd_r, j + kd_c \in [0, n-1]$ for $k = 0, \ldots, \ell-1$.

Definition 2. The feasible set for direction $(d_r,d_c)$ is

Theorems

Theorem 1 (Completeness of four directions). The four direction vectors $(0,1)$, $(1,0)$, $(1,1)$, $(1,-1)$ suffice to enumerate every set of $\ell$ collinear adjacent entries in the grid. No products are missed and none are double-counted.

Proof. An arbitrary direction vector for collinear adjacency has the form $(d_r, d_c)$ with $(d_r, d_c) \in \{(\pm 1, 0), (0, \pm 1), (\pm 1, \pm 1)\}$. Consider any line segment of $\ell$ cells in direction $(d_r, d_c)$ starting at $(i,j)$. Its reverse, in direction $(-d_r, -d_c)$, starts at $(i + (\ell-1)d_r,\, j + (\ell-1)d_c)$ and traverses the same multiset of cells. Since multiplication is commutative, the product is identical. We pair directions:

• $(0,1) \leftrightarrow (0,-1)$ (horizontal),
• $(1,0) \leftrightarrow (-1,0)$ (vertical),
• $(1,1) \leftrightarrow (-1,-1)$ (main diagonal),
• $(1,-1) \leftrightarrow (-1,1)$ (anti-diagonal).

Each pair is represented by exactly one of our four chosen directions. Thus every product appears exactly once in $\bigcup_{(d_r,d_c)} \{P_{d_r,d_c}(i,j) : (i,j) \in \mathcal{F}_{d_r,d_c}\}$. $\square$

Lemma 1 (Product count). For $n = 20$ and $\ell = 4$, the total number of products is $1258$.

Proof. We compute $|\mathcal{F}_{d_r,d_c}|$ for each direction:

Total: $340 + 340 + 289 + 289 = 1258$. $\square$

Theorem 2 (Correctness of brute-force search). The algorithm below computes $\max_{(d_r,d_c)}\, \max_{(i,j) \in \mathcal{F}_{d_r,d_c}} P_{d_r,d_c}(i,j)$ by exhaustive enumeration over all $1258$ products.

Proof. The nested loops iterate over every $(i,j) \in \mathcal{F}_{d_r,d_c}$ for each of the four directions, computing each product exactly once and tracking the running maximum. By Theorem 1, this covers all possible products. $\square$

Editorial

We exhaustively evaluate the product of four adjacent entries in each relevant direction. The algorithm traverses every grid position, tests the horizontal, vertical, main-diagonal, and anti-diagonal directions whenever four cells remain in bounds, multiplies those four entries, and retains the largest product seen. This is sufficient because these four directions cover every possible set of four collinear adjacent cells.

Pseudocode

Algorithm: Maximum Grid Product Over Four Directions
Require: A rectangular grid G and a segment length 4.
Ensure: The greatest product of four adjacent grid entries in any allowed direction.
1: Initialize best ← 0.
2: For each cell (i, j) of G and each direction v in {(0, 1), (1, 0), (1, 1), (1, -1)} do:
3:     If the 4-term segment starting at (i, j) in direction v stays inside the grid, compute its product P.
4:     If P > best, set best ← P.
5: Return best.

Complexity Analysis

Proposition. The algorithm runs in $\Theta(n^2 \ell)$ time and $\Theta(n^2)$ space.

Proof. There are $|\mathcal{F}| = O(n^2)$ starting positions across all directions (precisely $4n(n-\ell+1) - 2(n-\ell+1)^2$ by Lemma 1, which is $\Theta(n^2)$ for fixed $\ell$). Each product requires $\ell - 1$ multiplications, so total work is $\Theta(n^2 \ell)$. The grid occupies $\Theta(n^2)$ space, and the algorithm uses $O(1)$ auxiliary variables. $\square$

For $n = 20$, $\ell = 4$: exactly $1258 \times 3 = 3774$ multiplications and $1258$ comparisons.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    int G[20][20] = {
        { 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}
    };

    const int N = 20, L = 4;
    int dirs[][2] = {{0,1},{1,0},{1,1},{1,-1}};
    long long best = 0;

    for (auto& d : dirs)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                int ei = i + (L-1)*d[0], ej = j + (L-1)*d[1];
                if (ei < 0 || ei >= N || ej < 0 || ej >= N) continue;
                long long p = 1;
                for (int k = 0; k < L; k++)
                    p *= G[i + k*d[0]][j + k*d[1]];
                best = max(best, p);
            }

    cout << best << endl;
    return 0;
}

"""Project Euler Problem 11: Largest Product in a Grid"""


def solve():

    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],
    ]

    N, L = 20, 4
    best = 0
    for dr, dc in [(0, 1), (1, 0), (1, 1), (1, -1)]:
        for i in range(N):
            for j in range(N):
                if not (0 <= i + (L - 1) * dr < N and 0 <= j + (L - 1) * dc < N):
                    continue
                p = 1
                for k in range(L):
                    p *= GRID[i + k * dr][j + k * dc]
                best = max(best, p)

    return best


answer = solve()
assert answer == 70600674
print(answer)