commit a958ff5dc52c59f758b36477694d692b4e3b3b61
parent cc659873f5697b32e5a17eeca6cef8d7116216c4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Tue, 30 Jan 2024 21:27:07 +0000
2 Random Problems
Diffstat:
3 files changed, 69 insertions(+), 0 deletions(-)
diff --git a/Problems/0930.cpp b/Problems/0930.cpp
@@ -0,0 +1,37 @@
+class Solution {
+ public:
+ int numSubarraysWithSum(const vector<int> &nums, int goal) const {
+ unordered_map<int, int> um = {{0, 1}};
+ int res = 0, crnt = 0;
+
+ for (const int n : nums) {
+ crnt += n;
+ res += um[crnt - goal];
+ um[crnt]++;
+ }
+
+ return res;
+ }
+};
+
+// O(1) space
+class Solution {
+ int atMost(const vector<int> &nums, int goal) const {
+ if (goal < 0) return 0;
+
+ int res = 0, crnt = 0, i = 0;
+ for (int j = 0; j < size(nums); j++) {
+ goal -= nums[j];
+ while (goal < 0)
+ goal += nums[i++];
+ res += j - i + 1;
+ }
+
+ return res;
+ }
+
+ public:
+ int numSubarraysWithSum(const vector<int> &nums, int goal) const {
+ return atMost(nums, goal) - atMost(nums, goal - 1);
+ }
+};
diff --git a/Problems/2201.cpp b/Problems/2201.cpp
@@ -0,0 +1,30 @@
+class Solution {
+ public:
+ int digArtifacts(int n, const vector<vector<int>> &artifacts, const vector<vector<int>> &dig) const {
+ vector<vector<int>> grid(n, vector(n, 0));
+ for (const auto &d : dig)
+ grid[d[0]][d[1]] = 1;
+
+ for (int i = 0, acc = 0; i < n; i++)
+ grid[i][0] = acc += grid[i][0];
+ for (int i = 0, acc = 0; i < n; i++)
+ grid[0][i] = acc += grid[0][i];
+ for (int i = 1; i < n; i++) {
+ for (int j = 1; j < n; j++) {
+ grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
+ }
+ }
+
+ int res = 0;
+ for (const auto &art : artifacts) {
+ const int goal = (art[2] - art[0] + 1) * (art[3] - art[1] + 1);
+ int crnt = grid[art[2]][art[3]];
+ crnt -= art[0] > 0 ? grid[art[0] - 1][art[3]] : 0;
+ crnt -= art[1] > 0 ? grid[art[2]][art[1] - 1] : 0;
+ crnt += art[0] > 0 && art[1] > 0 ? grid[art[0] - 1][art[1] - 1] : 0;
+ res += goal == crnt;
+ }
+
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -531,6 +531,7 @@ for solving problems.
| 0920 | Hard | [Number of Music Playlists](Problems/0920.cpp) |
| 0921 | Medium | [Minimum Add to Make Parentheses Valid](Problems/0921.cpp) |
| 0926 | Medium | [Flip String to Monotone Increasing](Problems/0926.cpp) |
+| 0930 | Medium | [Binary Subarrays With Sum](Problems/0930.cpp) |
| 0931 | Medium | [Minimum Falling Path Sum](Problems/0931.cpp) |
| 0932 | Medium | [Beautiful Array](Problems/0932.cpp) |
| 0933 | Easy | [Number of Recent Calls](Problems/0933.cpp) |
@@ -976,6 +977,7 @@ for solving problems.
| 2187 | Medium | [Minimum Time to Complete Trips](Problems/2187.cpp) |
| 2192 | Medium | [All Ancestors of a Node in a Directed Acyclic Graph](Problems/2192.cpp) |
| 2196 | Medium | [Create Binary Tree From Descriptions](Problems/2196.cpp) |
+| 2201 | Medium | [Count Artifacts That Can Be Extracted](Problems/2201.cpp) |
| 2215 | Easy | [Find the Difference of Two Arrays](Problems/2215.cpp) |
| 2218 | Hard | [Maximum Value of K Coins From Piles](Problems/2218.cpp) |
| 2221 | Medium | [Find Triangular Sum of an Array](Problems/2221.cpp) |
