Problem Explanation

In this problem, you're given the size of a square matrix (width and height), the size of submatrices that it can contain (sideLength), and the maximum number of ones that each submatrix can contain (maxOnes). Your task is to calculate the maximum total number of ones that the whole matrix can hold, while respecting the submatrix constraints.

Walk-through Example

Let's take a look at a real example to illustrate this:

width = 3, height = 3, sideLength = 2, maxOnes = 2

In this case, a matrix of size 3x3 could potentially hold 9 ones. However, since the maximal number of ones for each 2x2 submatrix is 2, your actual configuration will look like this:

1
2
31 0 1
41 0 1
51 0 1

If you add all these 1s, you'll get a total count of 6, which is the maximum amount of ones you can possibly have.

Approach

There is a simple algorithm that can solve this problem.

1. Start by keeping track of how many potential places for 1s exist in each cell of the submatrices. This can easily be done by iteratively checking each cell in the original matrix and then using the modulo operator with the sideLength size to find out which cell of the submatrix it belongs to.

2. Then put all the counts into a maximum heap(priority queue), which will automatically keep the highest counts at the top of the heap.

3. Finally, you can keep popping elements from the top of the heap until you've depleted your maxOnes count. Add these top elements (counts of potential places for 1s) to a result variable, which will be your answer.

This approach utilizes a data structure commonly known as a heap or priority queue, which is an efficient way of automatically sorting elements while adding or removing them.

Python Solution

1
2python
3import heapq
4class Solution:
5    def maxOnes(self, width: int, height: int, side: int, maxOnes: int) -> int:
6        counts = [
7            [0] * side for _ in range(side)
8        ]
9        heap = []
10
11        for i in range(width):
12            for j in range(height):
13                counts[i % side][j % side] += 1
14
15        for i in range(side):
16            for j in range(side):
17                heapq.heappush(heap, -counts[i][j])
18
19        return sum(-heapq.heappop(heap) for _ in range(maxOnes))

Java Solution

1
2java
3import java.util.*;
4
5class Solution {
6    public int maxOnes(int width, int height, int side, int maxOnes) {
7        int[][] counts = new int[side][side];
8        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
9
10        for(int i=0; i<width; i++) {
11            for(int j=0; j<height; j++) {
12                counts[i % side][j % side]++;
13            }
14        }
15
16        for(int i=0; i<side; i++) {
17            for(int j=0; j<side; j++) {
18                heap.add(counts[i][j]);
19            }
20        }
21
22        int sum = 0;
23
24        for(int i=0; i<maxOnes; i++) {
25            sum += heap.poll();
26        }
27
28        return sum;
29    }
30}

JavaScript Solution

1
2javascript
3class Solution {
4    maxOnes(width, height, side, maxOnes) {
5        let counts = Array(side).fill().map(() => Array(side).fill(0));
6        let heap = [];
7
8        for(let i=0; i<width; i++) {
9            for(let j=0; j<height; j++) {
10                counts[i % side][j % side]++;
11            }
12        }
13
14        for(let i=0; i<side; i++) {
15            for(let j=0; j<side; j++) {
16                heap.push(counts[i][j]);
17            }
18        }
19
20        heap.sort((a, b) => b - a);
21
22        let sum = 0;
23
24        for(let i=0; i<maxOnes; i++) {
25            sum += heap[i];
26        }
27
28        return sum;
29    }
30}

C++ Solution

1
2cpp
3#include <queue>
4using namespace std;
5
6class Solution {
7public:
8    int maxOnes(int width, int height, int side, int maxOnes) {
9        vector<vector<int>> counts(side, vector<int>(side));
10        priority_queue<int> heap;
11
12        for(int i=0; i<width; i++) {
13            for(int j=0; j<height; j++) {
14                counts[i % side][j % side]++;
15            }
16        }
17
18        for(int i=0; i<side; i++) {
19            for(int j=0; j<side; j++) {
20                heap.push(counts[i][j]);
21            }
22        }
23
24        int sum = 0;
25
26        for(int i=0; i<maxOnes; i++) {
27            sum += heap.top();
28            heap.pop();
29        }
30
31        return sum;
32    }
33};

C# Solution

1
2cs
3using System;
4using System.Collections.Generic;
5public class Solution {
6    public int MaxOnes(int width, int height, int side, int maxOnes) {
7        int[,] counts = new int[side, side];
8        List<int> heap = new List<int>();
9
10        for(int i=0; i<width; i++) {
11            for(int j=0; j<height; j++) {
12                counts[i % side, j % side]++;
13            }
14        }
15
16        for(int i=0; i<side; i++) {
17            for(int j=0; j<side; j++) {
18                heap.Add(counts[i, j]);
19            }
20        }
21
22        heap.Sort();
23        heap.Reverse();
24
25        int sum = 0;
26
27        for(int i=0; i<maxOnes; i++) {
28            sum += heap[i];
29        }
30
31        return sum;
32    }
33}

Remember that heap data structure is not directly supported in JavaScript and C#, we use an array or list and sort them to simulate a heap. In Python, Java and C++, we can use the built-in data types (HeapQ, PriorityQueue and Priority_queue respectively).While the above is a great approach, it may not work as efficiently when there are large numbers involved especially if the width and height of the matrix are large. This is because the time complexity for the approach is O(n^2 logn) which can lead to slower executions when n is large. However, this can be solved by taking an optimized mathematical approach.

Optimized Approach

Let's say side is 3, and we have square 3x3. Then we put first nine numbers according to pattern:

1
2
30,0  0,1  0,2
41,0  1,1  1,2
52,0  2,1  2,2

Then next nine numbers we will put in the same places, just will put in cells with smaller coordinates. For the total sum we just need to calculate how many times we put next number in each cell, and calculate the sum.

Python Solution

1
2python
3class Solution:
4    def maxOnes(self, width: int, height: int, side: int, maxOnes: int) -> int:
5        counts = sorted((i % side) * (j % side) for i in range(width) for j in range(height), reverse=True)
6        return sum(counts[:maxOnes])

We calculate counts for all the cells first and then sort in descending order. Finally we sum up the maximal values from the count array, which would give us the maximum total number of ones in the grid.

Java Solution

1
2java
3import java.util.*;
4
5class Solution {
6    public int maxOnes(int width, int height, int side, int maxOnes) {
7        List<Integer> counts = new ArrayList<>();
8        for(int i=0; i<width; i++) {
9            for(int j=0; j<height; j++) {
10                counts.add((i % side) * (j % side));
11            }
12        }
13
14        counts.sort(Collections.reverseOrder());
15
16        int sum = 0;
17
18        for(int i=0; i<maxOnes; i++) {
19            sum += counts.get(i);
20        }
21
22        return sum;
23    }
24}

In Java, creating a list of counts and sorting them in descending order to take the sum of the maxOnes might end in Java heap memory errors for large enough width and height of the grid. Try to avoid creating huge lists in Java wherever possible.

JavaScript Solution

1
2javascript
3class Solution {
4    maxOnes(width, height, side, maxOnes) {
5        let counts = [];
6        for(let i=0; i<width; i++) {
7            for(let j=0; j<height; j++) {
8                counts.push((i % side) * (j % side));
9            }
10        }
11
12        counts.sort((a, b) => b - a);
13
14        let sum = 0;
15
16        for(let i=0; i<maxOnes; i++) {
17            sum += counts[i];
18        }
19
20        return sum;
21    }
22}

In case of JavaScript, there are no threading issues like Java but creating such large arrays can slow down the program significantly, it is recommended to use some other optimized approach if the grid size is very large.