Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/750.html

750. Number Of Corner Rectangles (Medium)

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

 

Example 1:

Input: grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

 

Example 2:

Input: grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
Output: 9
Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

 

Example 3:

Input: grid = 
[[1, 1, 1, 1]]
Output: 0
Explanation: Rectangles must have four distinct corners.

 

Note:

  1. The number of rows and columns of grid will each be in the range [1, 200].
  2. Each grid[i][j] will be either 0 or 1.
  3. The number of 1s in the grid will be at most 6000.

 

Companies:
Google

Related Topics:
Dynamic Programming

Solution 1.

  • class Solution {
        public int countCornerRectangles(int[][] grid) {
            Map<String, Integer> map = new HashMap<String, Integer>();
            int rows = grid.length, columns = grid[0].length;
            for (int i = 0; i < rows; i++) {
                List<Integer> onesColumns = new ArrayList<Integer>();
                for (int j = 0; j < columns; j++) {
                    if (grid[i][j] == 1)
                        onesColumns.add(j);
                }
                if (onesColumns.size() > 1) {
                    int size = onesColumns.size();
                    for (int j = 0; j < size; j++) {
                        for (int k = j + 1; k < size; k++) {
                            int[] array = {onesColumns.get(j), onesColumns.get(k)};
                            String arrayStr = Arrays.toString(array);
                            int count = map.getOrDefault(arrayStr, 0);
                            count++;
                            map.put(arrayStr, count);
                        }
                    }
                }
            }
            int totalCount = 0;
            Set<String> set = map.keySet();
            for (String key : set) {
                int count = map.getOrDefault(key, 0);
                totalCount += count * (count - 1) / 2;
            }
            return totalCount;
        }
    }
    
  • // OJ: https://leetcode.com/problems/number-of-corner-rectangles/
    // Time: O(MN)
    // Space: O(C^2) where C is the count of 1s.
    class Solution {
    public:
        int countCornerRectangles(vector<vector<int>>& grid) {
            int M = grid.size(), N = grid[0].size(), ans = 0;
            map<int, set<int>> m;
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (!grid[i][j]) continue;
                    m[i].insert(j);
                }
            }
            for (auto i = m.begin(); i != m.end(); ++i) {
                for (auto j = next(i); j != m.end(); ++j) {
                    int cnt = 0;
                    for (int y : i->second) {
                        if (j->second.find(y) == j->second.end()) continue;
                        ++cnt;
                    }
                    ans += cnt * (cnt - 1) / 2;
                }
            }
            return ans;
        }
    };
    

All Problems

All Solutions