1183. Maximum Number of Ones

Problem Description

The problem presents us with a task to figure out the maximum number of 1s that can be placed in a matrix of dimensions width * height such that any square sub-matrix with size sideLength * sideLength contains at most maxOnes ones. We need to consider that the value of each cell in the matrix can either be 0 or 1. The main goal is to place the 1s in such a way that we can maximize their count without violating the condition placed on the square sub-matrices.

Intuition

To solve this problem, we need to recognize that the constraints on sub-matrices of size sideLength * sideLength create a repeating pattern across the larger matrix. The idea is that we only need to figure out the placement of 1s within a section of the matrix that is the size of sideLength * sideLength, and then repeat this pattern throughout the entire matrix.

The intuition behind the solution is to:

Create a pattern within a single square block of sideLength * sideLength that maximizes the 1s without exceeding maxOnes.
Make sure that when the pattern is repeated, we still adhere to the constraints (with regards to maxOnes) at the edges where two repeating patterns meet.
Calculate the frequency of each position within the square block throughout the entire matrix and fill the positions with the highest frequency with 1s first.
After placing 1s in the positions with the highest frequency, we continue doing so in descending order until we reach the limit set by maxOnes.
Sum up the most frequent positions that we filled with 1s to determine the maximum number of 1s in the whole matrix.

The solution code implements this approach effectively by first initializing a counter array cnt to keep track of how many times each position within a sideLength square would appear in the whole matrix. It then iterates over every cell in the matrix, calculating the position's index in the cnt array by using modulo arithmetic. After populating cnt, we sort it in reverse order to prioritize positions with the highest frequency. Finally, we sum up the maxOnes highest values in cnt to find the maximum number of 1s the matrix can have.

Learn more about Greedy and Heap (Priority Queue) patterns.

Solution Approach

The implementation of the solution involves several steps that use basic programming constructs and straightforward arithmetic operations. Here's how the solution is carried out:

Initialize a counter array: A list cnt of size x * x (where x is sideLength) is created to keep track of the number of times each position within a sideLength x sideLength block can be filled throughout the entire matrix (M). The size of this array corresponds to all possible positions in a block of the size sideLength * sideLength.
Fill the counter array: We iterate over each cell in the matrix using nested loops. Each cell's position is determined using the module operation to find its equivalent position within the block pattern. The index in cnt for any given cell at position (i, j) is calculated using (i % x) * x + (j % x), which effectively maps the 2D coordinates to a 1D array index.
Sort the counter array: Once the entire matrix has been scanned and the cnt array has been filled with the frequency of each position, we sort cnt in descending order. This ensures that the positions with the highest frequency (i.e., positions that will be included in the maximum number of sideLength x sideLength squares) are at the start of the cnt array.
Sum up the top frequencies: Finally, since we need to place a maximum of maxOnes 1s in any sideLength x sideLength block, we just take the first maxOnes elements of the sorted cnt array. These elements indicate the highest possible frequency for the 1s that can be placed in those positions without violating the constraints. The sum of these top frequencies will give us the maximum count of 1s that can be placed in the whole matrix.

The solution employs the [greedy](/problems/greedy_intro) algorithm concept by always prioritizing the positions that will appear most frequently across the matrix and filling those with 1s before considering positions with lower frequency. This ensures the optimal distribution of the 1s within the constraints given.

The data structure used is a simple list to keep track of the frequency counts. The sorting algorithm, which could be any efficient in-place sorting algorithm, is utilized to arrange the counts in descending order. Finally, the modulo operation and arithmetic are used to map positions and calculate frequencies.

The reference solution code provided above encapsulates this approach within the maximumNumberOfOnes method of the Solution class. This method is parameterized by the matrix dimensions (width and height), the block size (sideLength), and the constraint (maxOnes), and it returns the calculated maximum number of 1s accordingly.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider a matrix of dimensions width = 3, height = 3, sideLength = 2, and maxOnes = 2. This means we want to fill a 3x3 matrix with ones and zeros, but any 2x2 sub-matrix within it can contain at most 2 ones.

Initialize counter array: Since our sideLength is 2, we create a list cnt of size 2 * 2 or 4 to keep track of each position's frequency within such a block. The cnt list starts as [0, 0, 0, 0].
Fill the counter array: We iterate over the 3x3 matrix's cells. For each cell at position (i, j), we use the formula (i % sideLength) * sideLength + (j % sideLength) to increment the corresponding index in cnt. After this step, cnt looks like this:
- The cell at (0, 0) maps to cnt[0], increment it (cnt: [1, 0, 0, 0]).
- The cell at (0, 1) maps to cnt[1], increment it (cnt: [1, 1, 0, 0]).
- The cell at (0, 2) also maps to cnt[0] (because (0 % 2)*2 + (2 % 2) equals 0), increment it (cnt: [2, 1, 0, 0]).
- Continue this for all cells and cnt ends up as [2, 2, 1, 1].
Sort the counter array: We sort cnt in descending order, resulting in [2, 2, 1, 1]. This tells us the frequency of each position across the whole matrix.
Sum up the top frequencies: Since maxOnes is 2, we take the largest 2 values from cnt, which are both 2. We sum these to get the maximum number of 1s we can place, which is 2 + 2 = 4.

By following these steps, the pattern within a single block would be to place ones in the first two positions because they have the highest frequency, and the resulting matrix might look something like:

1 1 1
1 0 0
0 0 0

This matrix has the maximum number of 1s (which is 4 in this case) while adhering to the constraint of a maximum of 2 ones in any 2x2 sub-matrix.

Solution Implementation

1class Solution:
2    def maximumNumberOfOnes(self, width: int, height: int, side_length: int, max_ones: int) -> int:
3        # `side_length` is the length of one side of the square in the grid
4        cell_count = [0] * (side_length * side_length)  # Initialize a list to count occurrence of '1's in the grid cells
5
6        # Iterate over each cell in the grid
7        for i in range(width):
8            for j in range(height):
9                # Calculate the position of the cell in the side_length x side_length square
10                # This identifies the repeating pattern within the submatrix
11                cell_index = (i % side_length) * side_length + (j % side_length)
12                # Increment the count for this position
13                cell_count[cell_index] += 1
14
15        # Sort the cell counts in descending order to get the cells with the most '1's first
16        cell_count.sort(reverse=True)
17
18        # Sum the counts of the top `max_ones` cells to get the maximum number of '1's
19        return sum(cell_count[:max_ones])
20
21# Example Usage:
22# sol = Solution()
23# result = sol.maximumNumberOfOnes(3, 3, 2, 1)
24# print(result)  # Should print the maximum number of '1's possible with the given constraints
25

1import java.util.Arrays; // Import necessary for the Arrays.sort() method.
2
3class Solution {
4    // Method calculates the maximum number of ones that can be placed
5    // in a width by height grid, with a maximum of maxOnes ones per
6    // sideLength by sideLength subgrid.
7    public int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
8        // Initialize the counter array.
9        // Each element represents the number of times a cell is visited in the tiling process.
10        int[] count = new int[sideLength * sideLength];
11      
12        // Iterate over each cell in the grid.
13        for (int i = 0; i < width; ++i) {
14            for (int j = 0; j < height; ++j) {
15                // Calculate the position in the subgrid (modular arithmetic).
16                int index = (i % sideLength) * sideLength + (j % sideLength);
17                // Increment the count for this position in subgrid.
18                ++count[index];
19            }
20        }
21
22        // Sort the count array in ascending order to find the positions
23        // with the highest counts.
24        Arrays.sort(count);
25
26        // Initialize the answer variable, which will hold the maximum number of ones.
27        int answer = 0;
28      
29        // Add the highest values from the sorted count array. The highest values correspond
30        // to the positions most frequently visited, and thus should be prioritized to
31        // place the ones.
32        for (int i = 0; i < maxOnes; ++i) {
33            answer += count[count.length - i - 1]; // Take values from the end of the sorted array.
34        }
35      
36        // Return the calculated maximum number of ones.
37        return answer;
38    }
39}
40

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Calculates the maximum number of 1's that can be placed in a grid, 
7    // with constraints on the number of 1's in any subgrid of a certain side length
8    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
9        // Count frequency of 1s for each position in subgrid
10        std::vector<int> frequency_count(sideLength * sideLength, 0);
11
12        // Iterate through the entire grid using modular arithmetic 
13        // to map positions to subgrid positions
14        for (int i = 0; i < width; ++i) {
15            for (int j = 0; j < height; ++j) {
16                // Calculate the position in the subgrid
17                int position_in_subgrid = (i % sideLength) * sideLength + (j % sideLength);
18                // Increment the frequency count for this subgrid position
19                ++frequency_count[position_in_subgrid];
20            }
21        }
22
23        // Sort the frequency count in descending order 
24        // to get the most frequent positions first
25        std::sort(frequency_count.rbegin(), frequency_count.rend());
26
27        // Calculate the maximum number of 1's by adding up the highest frequencies
28        int max_ones_count = 0;
29        for (int i = 0; i < maxOnes; ++i) {
30            max_ones_count += frequency_count[i];
31        }
32
33        // Return the maximum number of 1's
34        return max_ones_count;
35    }
36};
37

1/**
2 * This function calculates the maximum number of ones that can be distributed
3 * in a sub-matrix pattern within a larger matrix while ensuring that
4 * each sub-matrix has no more than the specified maximum number of ones.
5 *
6 * @param {number} width - The width of the main matrix
7 * @param {number} height - The height of the main matrix
8 * @param {number} sideLength - The side length of the sub-matrix
9 * @param {number} maxOnes - The maximum number of ones allowed in each sub-matrix
10 * @returns {number} - The maximum number of ones that can be placed in the main matrix
11 */
12function maximumNumberOfOnes(width: number, height: number, sideLength: number, maxOnes: number): number {
13    // Create an array to store the count of potential ones for each position in the sub-matrix
14    const subMatrixCounts: number[] = new Array(sideLength * sideLength).fill(0);
15  
16    // Iterate over each position in the main matrix
17    for (let i = 0; i < width; ++i) {
18        for (let j = 0; j < height; ++j) {
19            // Determine the corresponding position within the sub-matrix
20            const positionIndex: number = (i % sideLength) * sideLength + (j % sideLength);
21            // Increment the count for this position
22            ++subMatrixCounts[positionIndex];
23        }
24    }
25  
26    // Sort the counts in descending order
27    subMatrixCounts.sort((a, b) => b - a);
28  
29    // Sum up to the maxOnes most frequent positions to find the maximum number of ones
30    const maxOnesSum: number = subMatrixCounts.slice(0, maxOnes).reduce((sum, count) => sum + count, 0);
31  
32    return maxOnesSum;
33}
34
35// Example usage
36const maxWidth: number = 4;
37const maxHeight: number = 4;
38const subMatrixSideLength: number = 1;
39const maxSubMatrixOnes: number = 2;
40const result: number = maximumNumberOfOnes(maxWidth, maxHeight, subMatrixSideLength, maxSubMatrixOnes);
41
42console.log(result); // Output the result
43

Time and Space Complexity

Time Complexity

The given code has mainly two parts that contribute to the total time complexity: the nested for loop and the sorting operation.

Nested for Loop: The nested loop runs once for every cell in the width x height grid. A single iteration of the inner loop results in a constant-time operation. Therefore, the total time taken by the nested loop would be O(width * height).
Sorting Operation: The sort() method is called on the cnt list, which here can have at most sideLength * sideLength elements. The sorting operation using the default TimSort algorithm implemented in Python has a worst-case time complexity of O(n log n), where n is the number of elements in the list. This step would have a complexity of O(sideLength^2 log(sideLength^2)).

The overall time complexity would be the sum of these two parts, which would be: O(width * height + sideLength^2 log(sideLength^2)).

Space Complexity

The space complexity of the given code is determined principally by the storage required for the cnt list.

cnt List: The list cnt has sideLength * sideLength elements, so the space required is O(sideLength^2).

Additionally, a fixed amount of extra space is used by counters and indices in the for loops, but this does not depend on the input size and thus contributes only a constant factor.

Hence, the total space complexity is: O(sideLength^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know