# Given a large rectangular 2D grid of arbitrarily-placed 1's and 0's, write a service that answers
# the query "how many 1's in a given subgrid?". You should assume that the grid is large, doesn't
# change, and is given to you ahead of time. The query will be called many times, so it needs to be fast.
# Example
# Grid:
# 0 0 0 1
# 1 0 1 0
# 1 1 1 0
# int getOnes(x1, y1, x2, y2)
# Input: 0, 0, 1, 3
# Output: 3
# Input: 1, 1, 2, 3
# Output: 3
This is the 2D extension of the range counting problem. Build a 2D prefix-sum matrix pre[i][j] for ones in the rectangle from (0,0) to (i,j), then answer any subgrid query in O(1) time using the inclusion–exclusion formula. It tests understanding of 2D prefix sums and careful boundary handling
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Meta, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for these companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
END
