Today I have done leetcode's January LeetCoding Challenge with cpp.

January LeetCoding Challenge 19

Description

Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 104
• 0 <= threshold <= 105

Solution

class Solution {
  const int MOD = 1e9 + 7;
  unordered_set<int> getLengths(vector<int> &fences, int border) {
    unordered_set<int> st;
    fences.push_back(1);
    fences.push_back(border);
    sort(fences.begin(), fences.end());
    int sz = fences.size();
    for(int i = 0; i < sz - 1; ++i) {
      for(int j = i + 1; j < sz; ++j) {
        st.insert(fences[j] - fences[i]);
      }
    }
    return st;
  }
public:
  int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
    auto hLengths = getLengths(hFences, m);
    auto vLengths = getLengths(vFences, n);
    int side = 0;
    for(auto hl : hLengths) {
      if(vLengths.count(hl)) side = max(side, hl);
    }
    if(side == 0) return -1;
    return 1LL * side * side % MOD;
  }
};

// Accepted
// 648/648 cases passed (1806 ms)
// Your runtime beats 22.88 % of cpp submissions
// Your memory usage beats 9.8 % of cpp submissions (445.9 MB)