Welcome to Subscribe On Youtube

1183. Maximum Number of Ones

Description

Consider a matrix M with dimensions width * height, such that every cell has value 0 or 1, and any square sub-matrix of M of size sideLength * sideLength has at most maxOnes ones.

Return the maximum possible number of ones that the matrix M can have.

 

Example 1:

Input: width = 3, height = 3, sideLength = 2, maxOnes = 1
Output: 4
Explanation:
In a 3*3 matrix, no 2*2 sub-matrix can have more than 1 one.
The best solution that has 4 ones is:
[1,0,1]
[0,0,0]
[1,0,1]

Example 2:

Input: width = 3, height = 3, sideLength = 2, maxOnes = 2
Output: 6
Explanation:
[1,0,1]
[1,0,1]
[1,0,1]

 

Constraints:

• 1 <= width, height <= 100
• 1 <= sideLength <= width, height
• 0 <= maxOnes <= sideLength * sideLength

Solutions

Solution 1: Count Equivalent Positions

For convenience, let’s denote $x = sideLength$.

Consider a $x \times x$ square, we need to select at most $maxOnes$ points inside the square and set them to 1. Note that when the point at coordinate $(i, j)$ is selected, all points at coordinates $(i\pm k_1 \times x, j\pm k_2 \times x)$ can be equivalently set to 1. Therefore, we calculate the number of equivalent positions of the coordinate $(i, j)$ in the matrix, and select the top $maxOnes$ with the most quantities.

The time complexity is $O(m \times n)$, where $m$ and $n$ are the number of rows and columns of the matrix, respectively.

• Java
• C++
• Python
• Go
• Javascript

• class Solution {
      public int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
          int x = sideLength;
          int[] cnt = new int[x * x];
          for (int i = 0; i < width; ++i) {
              for (int j = 0; j < height; ++j) {
                  int k = (i % x) * x + (j % x);
                  ++cnt[k];
              }
          }
          Arrays.sort(cnt);
          int ans = 0;
          for (int i = 0; i < maxOnes; ++i) {
              ans += cnt[cnt.length - i - 1];
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
          int x = sideLength;
          vector<int> cnt(x * x);
          for (int i = 0; i < width; ++i) {
              for (int j = 0; j < height; ++j) {
                  int k = (i % x) * x + (j % x);
                  ++cnt[k];
              }
          }
          sort(cnt.rbegin(), cnt.rend());
          int ans = 0;
          for (int i = 0; i < maxOnes; ++i) {
              ans += cnt[i];
          }
          return ans;
      }
  };
  

• class Solution:
      def maximumNumberOfOnes(
          self, width: int, height: int, sideLength: int, maxOnes: int
      ) -> int:
          x = sideLength
          cnt = [0] * (x * x)
          for i in range(width):
              for j in range(height):
                  k = (i % x) * x + (j % x)
                  cnt[k] += 1
          cnt.sort(reverse=True)
          return sum(cnt[:maxOnes])
  
  

• func maximumNumberOfOnes(width int, height int, sideLength int, maxOnes int) int {
  	x := sideLength
  	cnt := make([]int, x*x)
  	for i := 0; i < width; i++ {
  		for j := 0; j < height; j++ {
  			k := (i%x)*x + (j % x)
  			cnt[k]++
  		}
  	}
  	sort.Ints(cnt)
  	ans := 0
  	for i := range cnt[:maxOnes] {
  		ans += cnt[len(cnt)-i-1]
  	}
  	return ans
  }
  

• /**
   * @param {number} width
   * @param {number} height
   * @param {number} sideLength
   * @param {number} maxOnes
   * @return {number}
   */
  var maximumNumberOfOnes = function (width, height, sideLength, maxOnes) {
      const x = sideLength;
      const cnt = new Array(x * x).fill(0);
      for (let i = 0; i < width; ++i) {
          for (let j = 0; j < height; ++j) {
              const k = (i % x) * x + (j % x);
              ++cnt[k];
          }
      }
      cnt.sort((a, b) => b - a);
      return cnt.slice(0, maxOnes).reduce((a, b) => a + b, 0);
  };
  
  

All Problems

All Solutions