Leet Code Weekly Contest 290

1. Intersection of Multiple Arrays

Take a hash-map to count the frequency of numbers.
The numbers with frequency $n$ should be part of the answer.

c++

class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        int n = nums.size();
        unordered_map<int, int> cnt;
        for (auto &row : nums) {
            for (auto &x : row) {
                cnt[x]++;
            }
        }
        vector<int> ans;
        for (int i = 1; i <= 1000; i++) {
            if (cnt[i] == n) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

2. Count Lattice Points Inside a Circle

Brute-force, enumerate every possible lattice point.

c++

class Solution {
public:
    int countLatticePoints(vector<vector<int>>& circles) {
        int ans = 0;
        for (int x = -100; x <= 200; x++) {
            for (int y = -100; y <= 200; y++) {
                bool contained = false;
                for (auto &circle : circles) {
                    int dx = abs(x - circle[0]);
                    int dy = abs(y - circle[1]);
                    int r = circle[2];
                    if (dx * dx + dy * dy <= r * r) {
                        contained = true;
                        break;
                    }
                }
                if (contained) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

3. Count Number of Rectangles Containing Each Point

As we know from the constraints, the range of h or y is very short.
So we can construct a hashmap from h to l[] (the values of l should be sorted).
For each point (x, y), enumerate h (h >= y) and binary search l.
Time complexity: $O(n \times h \times log(l))$ .

c++

class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        unordered_map<int, vector<int>> m;
        for (auto &rect : rectangles) {
            m[rect[1]].push_back(rect[0]);
        }
        for (auto &pair : m) {
            sort(pair.second.begin(), pair.second.end());
        }
        vector<int> ans;
        for (auto point : points) {
            int x = point[0], y = point[1], cnt = 0;
            for (int h = y; h <= 100; h++) {
                if (m.find(h) != m.end()) {
                    cnt += m[h].end() - lower_bound(m[h].begin(), m[h].end(), x);
                }
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

4. Number of Flowers in Full Bloom

Give a range [start, end], we can represent it into [(start, +1), (end + 1, -1)].
Thus, we can change the flowers array into a preffix-sum format.
Since the positions are discrete, we hold them into a BST.
For each person, find the closest previous preffix-sum record.
Time complexity: $O(n \times log(n))$ .

c++

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        map<int, int> cnt;
        for (auto &flower : flowers) {
            cnt[flower[0]]++;
            cnt[flower[1] + 1]--;
        }
        int prev = 0;
        for (auto &pair : cnt) {
            pair.second += prev;
            prev = pair.second;
        }
        vector<int> ans;
        for (auto &person : persons) {
            auto p = cnt.upper_bound(person);
            if (p == cnt.begin()) {
                ans.push_back(0);
            }
            else {
                p--;
                ans.push_back(p->second);
            }
        }
        return ans;
    }
};

Leet Code Weekly Contest 290

1. Intersection of Multiple Arrays

2. Count Lattice Points Inside a Circle

3. Count Number of Rectangles Containing Each Point

4. Number of Flowers in Full Bloom

COMMAND INTERFACE

:help aguang.xyz