FastPrepDiagonal Robot Path Sum
Problem · Array

Diagonal Robot Path Sum

Learn this problem
● MediumCapital One logoCapital OneINTERNOA

Problem statement

You are given an integer matrix matrix and a starting cell (cellX, cellY). Coordinates are zero-based: cellX is the row and cellY is the column.

A robot starts at that cell, includes its value in a running sum, and initially moves diagonally in direction (+1, +1).

  1. Before each move, consider the next row and column. Reverse the row direction if the next row would leave the matrix. Independently reverse the column direction if the next column would leave the matrix.
  2. Move one cell diagonally using the resulting directions.
  3. If the destination was visited earlier, stop without adding its value again.
  4. Otherwise add the destination value. Stop if it is one of the four corners; if it is not, mark it visited and continue.

Return the collected sum. The starting cell is guaranteed not to be a corner.

Function

solution(matrix: int[][], cellX: int, cellY: int) → long

Examples

Example 1

matrix = [[1,2,3],[4,5,6],[7,8,9]]cellX = 1cellY = 1return = 14

The start (1,1) contributes 5. The next cell (2,2) is a corner, so add 9 and stop: 14.

Example 2

matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]cellX = 1cellY = 1return = 28

The distinct visited cells (1,1), (2,2), (1,3), (0,2) contribute 6 + 11 + 8 + 3 = 28. The next cell is the previously visited start, whose value is not counted twice.

Constraints

  • 2 ≤ matrix.length ≤ 500
  • 2 ≤ matrix[0].length ≤ 500
  • Every row has the same length.
  • -1000000000 ≤ matrix[r][c] ≤ 1000000000
  • The starting coordinates identify a valid non-corner cell.
  • Use a signed 64-bit integer for the sum.

More Capital One problems

drafts saved locally
public long solution(int[][] matrix, int cellX, int cellY) {
  // Write your code here.
}
matrix[[1,2,3],[4,5,6],[7,8,9]]
cellX1
cellY1
expected14
checking account