Problem statement

https://leetcode.com/problems/maximum-number-of-ones/

Solution 1

The idea is to put ones with regular pattern: if we do M[i, j] = M[i%side, j%side], then we can be sure, that there will be no conflicts if we do not have confict in top left square. We can count number of cells in each group and then choose maxOnes groups with bigest number of elements. In fact what we build here is example, the question is how to prove that we can not do better.

Complexity

Time complexity is O(W*H*log(WH)), space is O(s^2).

Code

class Solution:
    def maximumNumberOfOnes(self, W, H, side, maxOnes):
        if maxOnes == 0: return 0
        freqs = Counter()
        for i, j in product(range(H), range(W)):
            freqs[i%side, j%side] += 1

        return sum(sorted(freqs.values())[-maxOnes:])

Solution 2

In fact we have only 4 different groups: with frequencies. Let R = H//side, r = H%side, C = W//side, c = W%side. Then we have

  1. First group with frequencies (R+1)(C+1), we have r*c such elements.
  2. Second group with frequencies (R+1)C, we have r*(side - c) such elements.
  3. Third group with frequncies R(C+1), we have (side - r)*c such elements.
  4. Fourth group with frequenceis RC, we have (side - r)*(side - c) such elements.

What we need to need to take to have optimal algorithm is first as much elements from first group, then second, then third and then fourth, because we already have frequencies in decreasing order (we changed places for W and H in the beginning if it is not the case). Now, we iterate through areas and take elements in greedy way.

Complexity

Time and space complexity is just O(1).

Code

class Solution:
    def maximumNumberOfOnes(self, W, H, side, maxOnes):
        if W < H: W, H = H, W
        R, r = divmod(H, side)
        C, c = divmod(W, side)

        areas = [(r*c, (R+1)*(C+1)), (r*(side-c), (R+1)*C), ((side-r)*c, R*(C+1)), ((side-r)*(side-c), R*C)]
        ans = 0
        for area, count in areas:
            area = min(maxOnes, area)
            ans += count*area
            maxOnes -= area
            if not maxOnes: break
        return ans