Loading...
Loading...
Loading...
A photo-editing club project stores a brightness change for every pixel of an r × c image. A positive value makes the pixel brighter and a negative value makes it darker.
A rectangle is any block of pixels from row r1 to row r2 and from column c1 to column c2 (one pixel is also a rectangle). Count the rectangles whose total brightness change is exactly k.
Example 1
Input
2 2 0 1 -1 -1 1
Output
5
Both rows, both columns and the whole image add up to 0: five rectangles.
Example 2
Input
3 3 4 1 1 1 1 1 1 1 1 1
Output
4
Only the four 2 × 2 blocks add up to 4.
Try the problem first. Open one hint at a time.
Checking every rectangle means about (r²/2) × (c²/2) rectangles, around 2 × 10^9 for a 300 × 300 image.
Fix a top row and a bottom row. Squash the band between them into one array of column totals.
Now each rectangle in that band is a stretch of consecutive columns. Count stretches with total k using a running total and a HashMap, as in the one-row version.
When the bottom row moves down by one, add that row to the column totals instead of rebuilding them. Reset them only when the top row changes.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor