3
\$\begingroup\$

Challenge

Using the C++ language, have the function MaximalSquare(strArr) take the strArr parameter being passed which will be a 2D matrix of 0 and 1's, and determine the area of the largest square submatrix that contains all 1's. A square submatrix is one of equal width and height, and your program should return the area of the largest submatrix that contains only 1's. For example: if strArr is ["10100", "10111", "11111", "10010"] then this looks like the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0 

For the input above, you can see the bolded 1's create the largest square submatrix of size 2x2, so your program should return the area which is 4. You can assume the input will not be empty.

Sample Test Cases

Input:"0111", "1111", "1111", "1111"
Output:9

Input:"0111", "1101", "0111"
Output:1

How can I make improvements to my code? Is there any STL that I might not know of that might make the code simpler and/or efficient?

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

 bool check_Same_Length(std::vector< std::vector<int> > maximalSquareInput)
{
    bool state;

    size_t length = maximalSquareInput[0].size();

    for (int i = 0; i < maximalSquareInput.size(); ++i)
    {
        if (length == maximalSquareInput[i].size())
        {
            state = true;
        }
        else
        {
            state = false;

            return state;
        }
    }

    return state;
}

bool only_1_And_0(std::vector< std::vector<int> > maximalSquareInput)
{
    for (int i = 0; i < maximalSquareInput.size(); ++i)
    {
        if (!(std::all_of(maximalSquareInput[i].begin(), maximalSquareInput[i].end(),
                          [] (int digit) { return digit == 1 || digit == 0; })))
        {
            return false;
        }
    }

    return true;
}

int findBiggestElement(std::vector< std::vector<int> > maximalSquareOutput)
{
    int biggestElement = 0;

    for (int i = 0; i < maximalSquareOutput.size(); ++i)
    {
        auto itr = std::max_element(maximalSquareOutput[i].begin(), maximalSquareOutput[i].end());

        if (*itr > biggestElement)
        {
            biggestElement = *itr;
        }
    }

    return biggestElement;
}

std::string findLargestSubmatrix(const std::vector< std::vector<int> > maximalSquareInput)
{
    std::vector< std::vector<int> > maximalSquareOutput (maximalSquareInput.size(), std::vector<int>(maximalSquareInput[0].size()) );

    if(check_Same_Length(maximalSquareInput) && only_1_And_0(maximalSquareInput))
    {
        for (int row = 0; row < maximalSquareInput.size(); ++row)
        {
            for (int column = 0; column < maximalSquareInput[row].size(); ++column)
            {
                if (row == 0 || column == 0 || maximalSquareInput[row][column] == 0)
                {
                    maximalSquareOutput[row][column] = maximalSquareInput[row][column];
                }
                else
                {
                    int minElement = std::min({maximalSquareOutput[row-1][column], maximalSquareOutput[row-1][column-1], maximalSquareOutput[row][column-1]});

                    maximalSquareOutput[row][column] = maximalSquareInput[row][column] + minElement;
                }
            }
        }
    }

    unsigned long long int biggestElement = findBiggestElement(maximalSquareOutput);

    return std::to_string(biggestElement * biggestElement);
}
\$\endgroup\$
3
\$\begingroup\$
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

Do you need <iostream>?


bool check_Same_Length(std::vector< std::vector<int> > maximalSquareInput)

Space in the typename isn't required since .

Not thrilled with the naming. The function could be better named to signal that you are checking the column counts. The parameter doesn't have to be your maximal input, but any 2D container.

You copy the vector of vectors every time you call a function. Pass your matrix by reference (and to const if immutable).

bool has_equal_column_counts(const std::vector<std::vector<int>>& matrix)

    size_t length = maximalSquareInput[0].size();

size_t is missing its std:: namespace prefix. Consider auto.

What happens if maximalSquareInput is empty? If you are not going to check the preconditions yourself, you should at least document them.

    for (int i = 0; i < maximalSquareInput.size(); ++i) {
        if (length == maximalSquareInput[i].size()) {
            state = true;
        } else {
            state = false;
            return state;
        }
    }
    return state;

When you are accessing elements by an index and you are not using any index arithmetic, consider using range-based for.

    for (const auto& row : maximalSquareInput) {
        if (length == row.size()) {
            state = true;
        } else {
            state = false;
            return state;
        }
    }
    return state;

If you are returning false the first time you encounter an invalid length, just return false.

    for (const auto& row : maximalSquareInput) {
        if (length != row.size()) {
            return false;
        }
    }
    return true;

It turns out, the standard library has two functions that will do what you want here. You could use std::find or std::all_of, but std::adjacent_find works as well.

    auto not_equal_size = [](const auto& v1, const auto& v2) { 
        return v1.size() != v2.size(); 
    };
    return matrix.end()
        == std::adjacent_find(maximalSquareInput.begin(), 
                              maximalSquareInput.end(),
                              not_equal_size)

bool only_1_And_0(std::vector< std::vector<int> > maximalSquareInput)

Function should be named all_are_one_or_zero.

    for (int i = 0; i < maximalSquareInput.size(); ++i) {
        if (!(std::all_of(maximalSquareInput[i].begin(), maximalSquareInput[i].end(),
                          [] (int digit) { return digit == 1 || digit == 0; })))
        {
            return false;
        }
    }
    return true;

Again, range-based for would be better than index-based for.

Consider adding more tools to your toolbox to reduce repetition (DRY - Don't repeat yourself). You have a couple functions iterating over collections of iterables. An iterator that chains those collections (essentially "flattening" the collection) would allow you to simplify your function. Consider the following code (exposition-only):

bool all_are_one_or_zero(const std::vector<std::vector<int>>& matrix) {
    return std::all_of(make_flatten_iterator{matrix},
                       make_flatten_iterator{},
                       [](int digit) { return digit == 1 || digit == 0; });
}

auto find_biggest_element(const std::vector<std::vector<int>>& matrix) {
    return std::max_element(make_flatten_iterator{matrix},
                            make_flatten_iterator{});
}

int findBiggestElement(std::vector< std::vector<int> > maximalSquareOutput)

Be consistent with your formatting/style. You're function names have mixed snake_Camel_Case and camelCase. Pick one, stick with it.

If this was meant to be a generalized max element finder for a matrix, you should consider (a) what happens if the matrix is empty, and (b) is 0 the minimum element value for type int?


std::string findLargestSubmatrix(const std::vector< std::vector<int> > maximalSquareInput)

Why return a string? Consider just returning either the square length or the square area and let the caller convert it to a string if they want it formatted.

You've used "Biggest" and "Largest" but you've always called the input parameter "maximal" (for maximum). Just call it maximum and you can cut down on the parameter name.

std::size_t max_length_of_square_submatrix(const std::vector<std::vector<int>>& matrix)

    if(check_Same_Length(maximalSquareInput) && only_1_And_0(maximalSquareInput))

Back to being consistent, you have spaces to distinguish between language constructs (if, for) and functions and in this instance you don't.

Avoid unnecessary code nesting by returning early.

    if (!check_Same_Length(maximalSquareInput) || !only_1_And_0(maximalSquareInput)) 
    {
        return 0;
    }

    for (...)

Do you even need to check? Should that be the responsibility of some other function?


        for (int row = 0; row < maximalSquareInput.size(); ++row)
        {
            for (int column = 0; column < maximalSquareInput[row].size(); ++column)
            {
                if (row == 0 || column == 0 || maximalSquareInput[row][column] == 0)
                {

You check to see if you are on either the first row or first column. When in either the first row or first column, you already know you can't make a square towards the northwest. Therefore, you can just copy those values into your matrix of sums before calculating the entire matrix. Then you check from [1,row][1,col].

std::size_t max_area_of_square_submatrix(const std::vector<std::vector<int>>& matrix)
{
    auto sums = matrix;

    for (std::size_t row = 1; row < matrix.size(); ++row)
    {
        for (std::size_t col = 1; col < matrix.size(); ++col)
        {
            if (matrix[row][col]) {
                sum[row][col] = 1 + std::min({sum[row-1][col],
                                              sum[row][col-1],
                                              sum[row-1][col-1]});
            } 
            else 
            {
                sum[row][col] = 0;
            }
        }
    }
    auto max_length = find_maximum_element(sums);
    return max_length * max_length;
}

std::string MaximalSquare(std::string strArr)
{
    auto matrix = to_matrix2i(strArr);
    if (!has_equal_column_counts(matrix) ||
        !all_are_one_or_zero(matrix)) 
    {
        return "0";
    }
    return std::to_string(max_area_of_square_submatrix(matrix));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.