Round 1
Questions: You are given a grid of size r × c and n objects located at specific coordinates. You need to find the number of axis-parallel rectangular subgrids that contain at least k of these objects.
Two rectangles are considered different if their coordinates are different.
def count_rectangles(r: int, c: int, n: int, k: int, positions: List[Tuple[int, int]]) -> int:
Examples:
1. r = 2, c = 2, n = 1, k = 1, positions = [(1, 2)] ans: 4 2. r = 3, c = 2, n = 3, k = 3, positions = [(1, 1), (3, 1), (2, 2)] ans: 1 3. r = 3, c = 2, n = 3, k = 2, positions = [(1, 1), (3, 1), (2, 2)] ans: 4
Candidate's Approach
The candidate was able to solve the problem efficiently using the following approach:
- Initialize the answer variable
ansto 0. - Iterate through each row as the starting point.
- Initialize arrays to store left (
l), right (r), count (cnt), and temporary values (to). - Count occurrences of objects in each column.
- Find the left and right bounds for the current row.
- Process the rectangles starting at position 0, adjusting counts and bounds as necessary.
- Define a remove function to update counts when necessary.
- Iterate backwards from the last row to the starting row, accumulating results.
The final result is returned as ans.
Interviewer's Feedback
No feedback provided.