Inclusive Rectangle Coverage Counts
Updated
Problem statement
You are given an integer n and an array rectangles. Start with an n x n matrix of zeros.
Each rectangle is represented as [top, left, bottom, right] using zero-based row and column indices. Its boundaries are inclusive. For every rectangle, add 1 to every matrix cell whose row is between top and bottom and whose column is between left and right.
Return the completed matrix of coverage counts.
Function
countRectangleCoverage(n: int, rectangles: int[][]) → int[][]Examples
Example 1
n = 3rectangles = [[0,0,1,1],[1,1,2,2]]return = [[1,1,0],[1,2,1],[0,1,1]]The two rectangles overlap only at (1,1), so that cell has count 2. Cells covered by one rectangle have count 1.
Example 2
n = 4rectangles = [[0,1,3,2],[1,0,2,3],[2,2,2,2]]return = [[0,1,1,0],[1,2,2,1],[1,2,3,1],[0,1,1,0]]The vertical and horizontal rectangles overlap across rows 1 and 2, columns 1 and 2. The one-cell rectangle raises (2,2) to 3.
Example 3
n = 2rectangles = []return = [[0,0],[0,0]]With no rectangles, every cell keeps its initial coverage count of 0.
Constraints
1 <= n <= 5000 <= rectangles.length <= 100000rectangles[i].length == 4- For every rectangle,
0 <= top <= bottom < nand0 <= left <= right < n. - Rectangle boundaries are inclusive.
More Google Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Centered K-by-K Submatrix SumsCitadel · ONSITE INTERVIEWCitadel interview questions
- Restaurant Delivery HeatmapDoorDash · ONSITE INTERVIEWDoorDash interview questions
- Shortest Path Around Rectangular ObstaclesDRW · OADRW interview questions
- Largest Square Sub-Grid Within a Sum LimitC3.ai · OAC3.ai interview questions
- Matrix Region and Ring SumsNVIDIA · PHONE SCREENNVIDIA interview questions
- Count Non-Overlapping Pairs of Rectangles That Sum to KWisdomAI · PHONE SCREEN
- Maximum Sum RectangleDeloitte · OADeloitte interview questions
- Rotting OrangesSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Search a Row- and Column-Sorted MatrixByteDance · ONSITE INTERVIEWByteDance interview questions
- Minimum Time to Spread Through a GridAmazon · PHONE SCREEN · ONSITE INTERVIEW
Google interview experiences
- Google L4 SWE Phone Screen: 1 Experience
- Google ML Engineering Manager Onsite: 1 Experience
- Google Experienced SWE First Round and Onsite: 1 Experience
- Google AI Coding Interview and AI OA: 2 Experiences
- Google SWE Intern Interview Results Timeline: 13 Experiences
- Google L4 SWE Phone Screen and Kirkland Onsite: 1 Experience