Maximum Number of Ones

Hard

Qualcomm

4 views

Topics:

Greedy Algorithms

Given four integers width, height, sideLength and maxOnes, you are asked to place some 1s into a width x height grid and obtain the maximum number of ones on it.

You are allowed to place a 1 into any cell (i, j) if and only if i % sideLength == j % sideLength.

Return the maximum number of ones you can put on the grid.

Example 1:

Input: width = 3, height = 3, sideLength = 2, maxOnes = 1
Output: 4
Explanation:
In this example, the cells where you can place a 1 are shown in light blue.
The number of ones in each 2x2 square is at most 1.  
In the 3x3 board, there are four 2x2 subgrids.
Placing a 1 on the dark blue cells is the optimal way to reach the maximum number of ones on the board.

Example 2:

Input: width = 2, height = 2, sideLength = 2, maxOnes = 2
Output: 4
Explanation:
There is only one 2x2 grid in this case, and you can place 1s on all the cells.

Constraints:

1 <= width, height <= 10⁵
1 <= sideLength <= min(width, height)
1 <= maxOnes <= 10⁹

Try coding it in LeetCode

Maximum Number of Ones

Hard

Qualcomm

4 views

Topics:

Greedy Algorithms

Given four integers width, height, sideLength and maxOnes, you are asked to place some 1s into a width x height grid and obtain the maximum number of ones on it.

You are allowed to place a 1 into any cell (i, j) if and only if i % sideLength == j % sideLength.

Return the maximum number of ones you can put on the grid.

Example 1:

Input: width = 3, height = 3, sideLength = 2, maxOnes = 1
Output: 4
Explanation:
In this example, the cells where you can place a 1 are shown in light blue.
The number of ones in each 2x2 square is at most 1.  
In the 3x3 board, there are four 2x2 subgrids.
Placing a 1 on the dark blue cells is the optimal way to reach the maximum number of ones on the board.

Example 2:

Input: width = 2, height = 2, sideLength = 2, maxOnes = 2
Output: 4
Explanation:
There is only one 2x2 grid in this case, and you can place 1s on all the cells.

Constraints:

1 <= width, height <= 10⁵
1 <= sideLength <= min(width, height)
1 <= maxOnes <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints for width, height, sideLength, and maxOnes? What is the maximum possible value for each of these?
Can width, height, or sideLength ever be zero?
If maxOnes is greater than the total number of cells in the grid (width * height), what should I return?
If sideLength is larger than either width or height, how should I handle that case?
Are width, height, and sideLength guaranteed to be positive integers?

Brute Force Solution

Approach

Imagine you have a grid filled with zeros and ones. Our goal is to find a smaller rectangle that contains the most ones. The brute force method is like checking every possible rectangle size and location to see which one has the most ones.

Here's how the algorithm would work step-by-step:

First, consider every possible top-left corner for the rectangle in the grid.
For each of those corners, try every possible width and height for the rectangle.
For each rectangle you define, count how many ones are inside it.
Keep track of the rectangle that had the largest number of ones so far.
After checking every possible rectangle, the one you kept track of is the answer.

Code Implementation

def find_maximum_ones_brute_force(grid):
    rows = len(grid)
    cols = len(grid[0])
    maximum_ones_found = 0

    for top_row in range(rows):
        for left_col in range(cols):
            # Iterate through all possible top-left corners.

            for height in range(1, rows - top_row + 1):
                for width in range(1, cols - left_col + 1):
                    # Iterate through all possible rectangle sizes.

                    current_ones = 0
                    for row in range(top_row, top_row + height):
                        for col in range(left_col, left_col + width):
                            current_ones += grid[row][col]

                    # Track the rectangle with max ones.
                    if current_ones > maximum_ones_found:
                        maximum_ones_found = current_ones

    return maximum_ones_found

Big(O) Analysis

Time Complexity

O(n^4) – Let n be the number of rows and m be the number of columns in the grid. The brute force approach iterates through all possible top-left corners, which takes O(n*m) time. For each top-left corner, it iterates through all possible widths and heights, taking another O(n*m) time in the worst case. For each rectangle defined by the top-left corner, width, and height, we need to count the number of ones inside, which takes O(n*m) in the worst case to traverse the rectangle. Therefore, the total time complexity is O(n*m * n*m). Assuming n and m are roughly equal (a square grid), this simplifies to O(n^4).

Space Complexity

O(1) – The provided brute force algorithm only requires a few constant space variables to keep track of the current rectangle's dimensions, its top-left corner coordinates, the current count of ones, and the maximum count of ones found so far. No auxiliary data structures that scale with the input grid's dimensions are utilized. Therefore, the algorithm's space complexity is independent of the input size, N, and is constant. Thus, the space complexity is O(1).

Optimal Solution

Approach

The goal is to place rectangles of a specific size within a larger grid to maximize the number of smaller squares that can fit. The best approach focuses on efficiently placing the rectangles and understanding how they interact with each other without trying every possible position. This allows us to arrive at the optimal answer by using math and logic instead of brute force.

Here's how the algorithm would work step-by-step:

Understand the overall size of the grid, the size of the rectangle, and the number of rectangles you can place.
Calculate how many rectangles fit perfectly in each row and column if there were no overlaps.
Figure out the best way to arrange these rectangles to minimize the wasted space. Start by aligning rectangles along the edge to use space efficiently.
Account for the overlap: determine how many of the smaller squares in the rectangles fall within the boundaries of the grid.
Because each rectangle has the same number of ones, the best arrangement is the one that lets us fit in the most rectangles.
Adjust the numbers if the rectangles don't fit perfectly. You might need to shift them slightly to get more into the grid.
Use math to find the theoretical maximum. After you’ve gotten the layout using an efficient approach, compare it to this maximum to ensure you didn't miss anything.

Code Implementation

def maximum_number_of_ones(grid_row_size, grid_column_size, rectangle_row_size, rectangle_column_size, max_rectangles):
    row_fit = grid_row_size // rectangle_row_size
    column_fit = grid_column_size // rectangle_column_size

    max_fit = row_fit * column_fit

    actual_rectangles = min(max_rectangles, max_fit)

    #We choose to use row_fit * column_fit rectangles
    total_ones = actual_rectangles * rectangle_row_size * rectangle_column_size

    row_remainder = grid_row_size % rectangle_row_size
    column_remainder = grid_column_size % rectangle_column_size

    # We want to determine the optimal offset
    row_offset = (grid_row_size + rectangle_row_size - 1) // rectangle_row_size
    column_offset = (grid_column_size + rectangle_column_size - 1) // rectangle_column_size

    num_rows = grid_row_size // rectangle_row_size
    num_cols = grid_column_size // rectangle_column_size

    remaining_rectangles = min(max_rectangles, row_offset * column_offset)

    #Greedily put as many rectangles as possible.
    if row_remainder != 0 and column_remainder != 0:
        remaining_rectangles = min(max_rectangles, num_rows * column_offset + row_offset * num_cols + row_offset * column_offset - num_rows * num_cols)

    number_of_rectangles_placed = min(max_rectangles,
                                      (grid_row_size // rectangle_row_size) * (grid_column_size // rectangle_column_size) +
                                      max(0, (grid_row_size % rectangle_row_size) * (grid_column_size // rectangle_column_size) // rectangle_column_size) +
                                      max(0, (grid_column_size % rectangle_column_size) * (grid_row_size // rectangle_row_size) // rectangle_row_size) +
                                      max(0, (grid_row_size % rectangle_row_size) * (grid_column_size % rectangle_column_size) // (rectangle_row_size * rectangle_column_size)))

    total_ones = number_of_rectangles_placed * rectangle_row_size * rectangle_column_size

    return number_of_rectangles_placed * rectangle_row_size * rectangle_column_size

Big(O) Analysis

Time Complexity

O(1) – The proposed solution focuses on mathematical calculations rather than iterative placement of rectangles. It calculates the number of rectangles that can fit based on grid and rectangle dimensions. These calculations involve a fixed number of arithmetic operations regardless of the grid size. Therefore, the time complexity is constant, denoted as O(1).

Space Complexity

O(1) – The plain English explanation focuses on calculations and arrangements without introducing auxiliary data structures that scale with the input grid size, rectangle size, or number of rectangles. The steps involve calculating how many rectangles fit, aligning them, and accounting for overlap, all performed using a fixed number of variables. There are no lists, maps, or recursion involved. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
width, height, or sideLength is zero	Return 0 immediately as no grid or subgrids can exist, preventing division by zero errors.
maxOnes is zero	Return 0 immediately since no ones can be placed.
width and height are smaller than sideLength	Effectively only one subgrid exists, so place min(width * height, maxOnes) ones.
width * height is smaller than maxOnes	Return width * height, because we cannot place more ones than there are cells in the grid.
width or height is a very large number (potential integer overflow in calculations)	Use long integers for intermediate calculations to prevent integer overflow when calculating areas or counts.
sideLength is 1	Place 'maxOnes' number of 1s but no more than width * height in total, i.e. return min(width * height, maxOnes).
maxOnes is greater than the number of subgrids	The final solution accounts for this by limiting the number of ones placed to the available grid cells.
width, height, and sideLength are all 1	Return min(1, maxOnes), since we have a 1x1 grid.