Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Largest Product in a Grid

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

Das lernst du

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

Problem

Übersetzung anzeigen

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.

Einschränkungen

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

Beispiele

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

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

Erwartete Ausgabe:
long long expected = 72;
Eingabe:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 2;

Erwartete Ausgabe:
long expected = 72;

Erläuterung

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

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

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

Erwartete Ausgabe:
long long expected = 504;
Eingabe:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 3;

Erwartete Ausgabe:
long expected = 504;

Erläuterung

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

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

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

Hinweis 2

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

Hinweis 3

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

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.