FastPrepBleeding Ink
Problems/Bleeding Ink

Bleeding Ink

Indeed logoIndeed● MediumINTERNNEW GRADOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The screenshots show the full test question but end before the sample's output. Other reports give the answers as 3046 and 217, and those match the rules.

The original test reads several papers from standard input and prints one total per paper. Here you get one paper per call and return its total. One later report shows an extra sample with a dot of darkness 4000, which is above the stated limit of 255. This version keeps the limit of 255. The test also asked you to explain your time and space complexity and how you would improve it. That part is not judged here, and the editorial covers it.

The judged task matches the source at about 95%.

A sheet of paper is a grid with height rows and width columns. Every cell starts white, with darkness 0.

You drop ink dots onto the paper. dots[i] = [row, col, darkness] means a dot with that darkness lands on cell (row, col). Rows and columns are numbered from 0.

The ink then bleeds:

  • It spreads to the cells above, below, left and right of a cell, never diagonally. It never leaves the paper.
  • Each cell it moves into lowers its darkness by 1. Once the ink reaches darkness 0, it stops spreading.
  • So a dot dropped at (dot_row, dot_col) can give cell (row, col) the darkness dot_darkness - abs(dot_row - row) - abs(dot_col - col).
  • When several dots reach the same cell, or several dots land on the same cell, the cell keeps the highest value. A cell that no ink reaches stays at 0.

After every dot has finished bleeding, return the total darkness of the paper: the sum of the darkness of all its cells.

Function

totalDarkness(height: int, width: int, dots: int[][]) → int

Examples

Example 1

height = 3width = 4dots = [[0,0,255],[1,2,255]]return = 3046

Both dots have darkness 255. Each cell keeps the higher of 255 - distance to the two dots:

cellcol 0col 1col 2col 3
row 0255254254253
row 1254254255254
row 2253253254253

For example, cell (0, 2) is 2 steps from the first dot (253) and 1 step from the second (254), so it keeps 254. The rows add up to 1016 + 1017 + 1013 = 3046.

Example 2

height = 5width = 6dots = [[1,0,10],[2,2,9],[2,3,5],[4,2,9]]return = 217

After bleeding, the paper looks like this:

cellcol 0col 1col 2col 3col 4col 5
row 0987654
row 11098765
row 2989876
row 3878765
row 4789876

The dot [2,3,5] adds nothing: the dot [2,2,9] is one step away and already gives that cell 8, which is more than 5. The rows add up to 39 + 45 + 47 + 41 + 45 = 217.

Example 3

height = 2width = 3dots = [[0,1,3],[0,1,1],[1,2,2]]return = 12

Two dots land on cell (0, 1). It keeps the darker one, 3, even though the dot with darkness 1 comes later. The paper ends up as:

cellcol 0col 1col 2
row 0232
row 1122

Cell (1, 2) gets 2 from its own dot (the first dot would give it only 1). The total is 7 + 5 = 12.

Constraints

  • 1 <= height <= 500
  • 1 <= width <= 500
  • 1 <= dots.length <= 10^4
  • dots[i].length == 3
  • 0 <= dots[i][0] < height
  • 0 <= dots[i][1] < width
  • 0 <= dots[i][2] <= 255

More Indeed problems

  • Insert into an Unrolled Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Course Completion OrderPHONE SCREEN · Seen May 2025
  • Recipes You Can PreparePHONE SCREEN · Seen May 2025
All Indeed interview questionsSee Indeed hiring insights
Saved
class Solution {
    public int totalDarkness(int height, int width, int[][] dots) {
        // Write your code here.
    }
}
Checking account…