All challenges
Medium 0 solved 0% acceptance

Largest Product in a Grid

Find the largest product of k numbers in a straight line in a grid.

What you'll learn

  • Walk a grid in four directions with step pairs
  • Check bounds before reading a run
  • Track a running maximum

Problem

A run is k cells in a straight line: left to right along a row, top to bottom down a column, or along either diagonal. Multiply the numbers in a run and find the run with the largest product.

Implement largest_product_in_grid(grid, k).

Input

grid: A rectangular grid of numbers; every row has the same length.

k: The length of a run.

Output

Return the largest product over all runs of length k. If no run of length k fits in the grid in any direction, return 0.

Constraints

1 ≤ rows, columns ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5

Examples

Example 1
Input:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 2

Expected output:
expected = 72
Input:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 2;

Expected output:
long long expected = 72;
Input:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 2;

Expected output:
long expected = 72;

Explanation

The best run is 8 and 9 on the bottom row: 8 × 9 = 72. The diagonal 5, 9 only gives 45.

Example 2
Input:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 3

Expected output:
expected = 504
Input:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 3;

Expected output:
long long expected = 504;
Input:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 3;

Expected output:
long expected = 504;

Explanation

The bottom row gives 7 × 8 × 9 = 504, larger than the right column 3 × 6 × 9 = 162 or any diagonal.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Four directions are enough: right, down, down-right and down-left. The others repeat the same runs backwards.

Hint 2

From each start cell, check that the last cell of the run is still inside the grid.

Hint 3

Return 0 only when no run of length k fits at all.

Expected complexity

O(rows × cols × k) time, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.