leetcode

commit f2301f8ab0267347bf106cffd38a443e48a8484f
parent 30d838aed5651a917c0180269fddcf3971aa195f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 15 Jan 2024 23:29:17 +0000

2 Random Problems

Diffstat:
A
Problems/1452.cpp
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++
A
Problems/2966.cpp
 | 
12
++++++++++++
M
README.md
 | 
2
++

3 files changed, 59 insertions(+), 0 deletions(-)
diff --git a/Problems/1452.cpp b/Problems/1452.cpp
@@ -0,0 +1,45 @@
+class Solution {
+  public:
+    vector<int> peopleIndexes(const vector<vector<string>> &favoriteCompanies) const {
+        const int n = size(favoriteCompanies);
+        vector<unordered_set<int>> companies(n);
+        unordered_map<string, int> um;
+
+        for (int i = 0; i < n; i++) {
+            for (const auto &company : favoriteCompanies[i]) {
+                const auto it = um.find(company);
+                const int key = it == um.end() ? um.size() : it->second;
+                if (it == um.end()) um.emplace(company, key);
+                companies[i].insert(key);
+            }
+        }
+
+        static int candidates[101];
+        vector<int> res;
+        for (int i = 0; i < n; i++) {
+            int elems = 0;
+            for (int j = 0; j < n; j++) {
+                if (i == j) continue;
+                if (size(companies[i]) >= size(companies[j])) continue;
+                candidates[elems++] = j;
+            }
+
+            for (const auto &company : companies[i]) {
+                int t = 0;
+                for (int j = 0; j < elems; j++) {
+                    const int candidate = candidates[j];
+                    if (companies[candidate].count(company)) {
+                        candidates[t++] = candidate;
+                    }
+                }
+
+                if (!t) {
+                    res.push_back(i);
+                    break;
+                }
+                elems = t;
+            }
+        }
+        return res;
+    }
+};
diff --git a/Problems/2966.cpp b/Problems/2966.cpp
@@ -0,0 +1,12 @@
+class Solution {
+  public:
+    vector<vector<int>> divideArray(vector<int> &nums, int k) const {
+        vector<vector<int>> res;
+        sort(begin(nums), end(nums));
+        for (int i = 0; i < size(nums); i += 3) {
+            if (nums[i + 2] - nums[i] > k) return {};
+            res.push_back({nums[i], nums[i + 1], nums[i + 2]});
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -723,6 +723,7 @@ for solving problems.
 |  1447  |   Medium   | [Simplified Fractions](Problems/1447.cpp)                                                          |
 |  1448  |   Medium   | [Count Good Nodes in Binary Tree](Problems/1448.cpp)                                               |
 |  1451  |   Medium   | [Rearrange Words in a Sentence](Problems/1451.cpp)                                                 |
+|  1452  |   Medium   | [People Whose List of Favorite Companies Is Not a Subset of Another List](Problems/1452.cpp)       |
 |  1456  |   Medium   | [Maximum Number of Vowels in a Substring of Given Length](Problems/1456.cpp)                       |
 |  1457  |   Medium   | [Pseudo-Palindromic Paths in a Binary Tree](Problems/1457.cpp)                                     |
 |  1458  |    Hard    | [Max Dot Product of Two Subsequences](Problems/1458.cpp)                                           |
@@ -1059,4 +1060,5 @@ for solving problems.
 |  2900  |   Medium   | [Longest Unequal Adjacent Groups Subsequence I](Problems/2900.cpp)                                 |
 |  2914  |   Medium   | [Minimum Number of Changes to Make Binary String Beautiful](Problems/2914.cpp)                     |
 |  2947  |   Medium   | [Count Beautiful Substrings I](Problems/2947.cpp)                                                  |
+|  2966  |   Medium   | [Divide Array Into Arrays With Max Difference](Problems/2966.cpp)                                  |
 |  2997  |   Medium   | [Minimum Number of Operations to Make Array XOR Equal to K](Problems/2997.cpp)                     |