JPMORGAN Coding Question – Solved

11 Live

Determine the highest value after executing n steps on an infinite 2D grid that initially contains all zeros. The grid is indexed from (1,1) at the bottom-left corner with coordinates increasing upwards and to the right. For each given coordinate pair (r, c), increment every cell in the rectangle from (1,1) to (r,c) inclusive by 1. After processing all coordinates, return the number of cells that contain the maximum value in the grid. Example: `upRight = ["1 4", "2 3", "4 1"]` Each string contains two space-separated integers representing the row (r) and column (c). The process: - Step 1: Increment cells in rectangle (1,1) to (1,4) - Step 2: Increment cells in rectangle (1,1) to (2,3) - Step 3: Increment cells in rectangle (1,1) to (4,1) The overlapping region across all three rectangles is the intersection of: - Rows: min(1, 2, 4) = 1 - Columns: min(4, 3, 1) = 1 Thus, cell (1,1) is the only cell included in all three updates. So the max value in the grid is 3, and it occurs once. Output: `1` Function Description: Complete the function `countMax` in the editor below. `countMax` has the following parameter: - `string upRight[n]`: an array of strings where each contains two space-separated integers representing the up-right corner of a rectangle. Return: - `long`: the number of occurrences of the final grid's maximum value. Constraints: - 1 ≤ n ≤ 100 - 1 ≤ number of rows, number of columns ≤ 10^6 Sample Input: `upRight = ["2 3", "3 7", "4 1"]` In this case: - Minimum of rows = min(2, 3, 4) = 2 - Minimum of columns = min(3, 7, 1) = 1 So the overlapping region is of size `2 × 1 = 2` Output: `2`

Asked in: JPMORGAN

Image of the Question

All Testcases Passed ✔

Solution

def countMax(upRight):
    columns = [list(map(int, row.split())) for row in upRight]
    mxrow = float('inf')
    mxcolumns = float('inf')
// ... rest of solution available after purchase

🔒 Please login to view the solution

Explanation

```
To understand how to solve this problem efficiently, let’s start by examining what each operation is doing and how it affects the grid. You are working with an infinite 2D grid, where every cell is initialized with the value zero. Each operation is defined by a pair (r, c), and for every such pair, you increment all cells from coordinate (1,1) to (r,c) inclusive by 1. This means that with every step, you are increasing the value of a rectangular block of the grid defined from the bottom-left corner (1,1) to the given top-right corner (r,c).

If you visualize the grid as a matrix, each operation marks a rectangle that begins at the origin (1,1) and extends up to some row r and column c. After applying all these rectangle updates, the cell or group of cells that has been included in the most rectangles will hold the maximum value. The value in any given cell will simply be equal to the number of rectangles that include that cell.

Therefore, the core of the problem is to identify how many cells exist in the intersection of all the given rectangles — because those are the only cells that will be updated in every operation, and thus will have the maximum value.

This observation allows you to completely avoid building the grid, which would be impossible due to its potentially massive size (up to a million in each dimension). Instead, you can focus purely on the overlap of all rectangles.

Let’s think about this step by step:

1. **Understand the update pattern**: Each operation (r, c) increases all values from (1,1) to (r,c). So with each update, a rectangular area from the origin to the point (r,c) is being incremented by 1.

2. **Visualize overlap**: The maximum value after all operations is the number of times a single cell has been updated. That will only happen to the cells that exist in the overlapping region of all the rectangles. This means that the intersection of all rectangles determines which cells are incremented every time, and thus will hold the highest value.

3. **Identify the overlapping region**: The only cells that are affected in all updates are those that lie in the overlapping area across all the defined rectangles. The overlap of rectangles from (1,1) to (r,c) across all updates is itself a rectangle from (1,1) to (min_r, min_c), where min_r is the smallest row limit and min_c is the smallest column limit among all given rectangle operations. This is because the intersection of multiple rectangles defined by (1,1) to (r,c) is bounded by the smallest r and c.

4. **Count the number of such cells**: Once you determine the boundaries of the overlapping rectangle, the number of cells that lie in that region is simply min_r × min_c. These are the only cells that are guaranteed to be incremented in every operation, and therefore, they are the only ones with the maximum value.

5. **Result interpretation**: Since all other cells outside of the overlapping region are not updated in every operation, they will have lower values. The count of the maximum value in the grid is then simply the number of cells within the overlapping region.

6. **Algorithm design**:
- Initialize min_row and min_col to very large values (e.g., set them to the maximum possible row and column based on the problem constraints).
- Iterate through the input list of rectangle corners.
- For each rectangle defined by a string like "r c", parse the row and column values.
- Continuously update min_row and min_col to reflect the minimum seen so far.
- After processing all rectangle corners, the count of maximum value cells is simply min_row × min_col.

This approach is highly efficient. Instead of dealing with a potentially massive grid, you are only comparing numbers and performing simple arithmetic. This ensures that the time complexity of the solution is linear in relation to the number of operations, i.e., O(n), and the space complexity is constant, i.e., O(1), since no large data structures are needed.

Also, edge cases are straightforward. For instance, if all rectangles are the same, the entire rectangle is the overlapping region. If rectangles only share a single cell at (1,1), then only that cell will have the maximum value.

In summary, this problem reduces to finding the intersection of all the given rectangles defined from (1,1) to (r,c), and computing the area of that intersecting rectangle. That area gives the count of cells that received the maximum number of updates.
```