We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Ones

Number: 1152

Difficulty: Hard

Paid? Yes

Companies: Qualcomm

Problem Description

Given a matrix M of dimensions width x height with each cell either 0 or 1, every sub-matrix that is a square of size sideLength x sideLength is constrained to have at most maxOnes ones. The goal is to determine the maximum total number of ones that can be placed in M while satisfying the constraint.

Key Insights

  • The constraint applies to every square sub-matrix of fixed sideLength, which means a repeating pattern can be used.
  • Since the matrix is filled by a periodic pattern of size sideLength x sideLength, the decision of where to place ones can be reduced to choosing positions in this small pattern.
  • Each cell (i, j) in the pattern will appear multiple times in the full matrix; count for each is computed by how many times that position gets repeated.
  • The idea is to calculate the frequency for every cell in the sideLength x sideLength block, sort them in descending order, and select the top maxOnes frequencies. The sum of these frequencies gives the maximum ones that can be placed.
  • Key trick: The frequency for a position (i, j) is given by: ( (width - i - 1) // sideLength + 1 ) * ( (height - j - 1) // sideLength + 1 ).
  • Greedy selection of the cells with the highest contribution amounts to the overall maximum ones.

Space and Time Complexity

Time Complexity: O((sideLength^2) * log(sideLength^2)) due to sorting the frequency array. Space Complexity: O(sideLength^2) to store the frequency counts for the pattern.

Solution

We leverage the observation that the matrix can be formed by repeating a pattern of size sideLength x sideLength. For each cell in this block, we compute the number of times it appears in the final matrix. Then, since every sideLength x sideLength sub-matrix can have at most maxOnes ones, we only select maxOnes number of positions (from the pattern) to fill with ones. Choosing the cells with the highest frequency ensures that the total number of ones is maximized. Sorting the frequencies and summing up the highest maxOnes values gives the desired answer.

Code Solutions

# Python solution for Maximum Number of Ones

def maximumNumberOfOnes(width, height, sideLength, maxOnes):
    # List to store frequencies for each cell position in the repeating block [0, sideLength-1] x [0, sideLength-1]
    freq = []
    
    # Compute frequency for each cell (i, j) in the block
    for i in range(sideLength):
        for j in range(sideLength):
            # Frequency for cell (i, j): how many times it appears in the matrix
            times_i = (width - i - 1) // sideLength + 1
            times_j = (height - j - 1) // sideLength + 1
            freq.append(times_i * times_j)
    
    # Sort frequencies in descending order so that highest frequency cells are chosen first
    freq.sort(reverse=True)
    
    # Sum the top maxOnes frequencies to get maximum total ones
    max_total_ones = sum(freq[:maxOnes])
    return max_total_ones

# Example usage
print(maximumNumberOfOnes(3, 3, 2, 1))  # Expected output: 4
print(maximumNumberOfOnes(3, 3, 2, 2))  # Expected output: 6
← Back to All Questions