aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_good_days_rob_bank.c62
-rw-r--r--find_good_days_rob_bank.py46
2 files changed, 108 insertions, 0 deletions
diff --git a/find_good_days_rob_bank.c b/find_good_days_rob_bank.c
new file mode 100644
index 0000000..a60cedc
--- /dev/null
+++ b/find_good_days_rob_bank.c
@@ -0,0 +1,62 @@
+// 2100. Find Good Days to Rob the Bank
+#include "leetcode.h"
+
+/*
+ * you and a gang of thieves are planning on robbing a bank. you are given a
+ * 0-indexed integer array 'security' where 'security[i]' is the number of
+ * guards on duty on the i'th day. the days are numbered starting from 0. you
+ * are also given an integer 'time'. the i'th day is a good day to rob the bank
+ * if there are at least 'time' days before and after the i'th day, the number
+ * of guards at the bank for the 'time' days before/after 'i' are
+ * non-increasing/non-decreasing. return a list of all days (0-indexed) that are
+ * good days to rob the bank. the order that the days are returned in does not
+ * matter
+ */
+
+int *goodDaysToRobBank(int *security, int securitySize, int time,
+ int *returnSize) {
+ int **duty = (int **)malloc(securitySize * sizeof(int *));
+ int *ans = (int *)malloc(securitySize * sizeof(int));
+ *returnSize = 0;
+ for (int i = 0; i < securitySize; i++)
+ duty[i] = (int *)calloc(1, sizeof(int) * 2);
+ for (int i = 1, guards = security[0], cnt = 0; i < securitySize; i++) {
+ cnt = guards >= security[i] ? cnt + 1 : 0;
+ guards = security[i];
+ duty[i][0] = cnt;
+ }
+ for (int i = securitySize - 2, guards = security[securitySize - 1], cnt = 0;
+ i >= 0; i--) {
+ cnt = guards >= security[i] ? cnt + 1 : 0;
+ guards = security[i];
+ duty[i][1] = cnt;
+ }
+ for (int i = 0; i < securitySize; i++) {
+ if (duty[i][0] >= time && duty[i][1] >= time) {
+ ans[*returnSize] = i;
+ (*returnSize)++;
+ }
+ free(duty[i]);
+ }
+ free(duty);
+ return ans;
+}
+
+int main() {
+ int s1[] = {5, 3, 3, 3, 5, 6, 2}, rs1;
+ int s2[] = {1, 1, 1, 1, 1}, rs2;
+ int s3[] = {1, 2, 3, 4, 5, 6}, rs3;
+ int *gdtrb1 = goodDaysToRobBank(s1, ARRAY_SIZE(s1), 2, &rs1);
+ int *gdtrb2 = goodDaysToRobBank(s2, ARRAY_SIZE(s2), 0, &rs2);
+ int *gdtrb3 = goodDaysToRobBank(s3, ARRAY_SIZE(s3), 2, &rs3);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", gdtrb1[i]); // expect: 2 3
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", gdtrb2[i]); // expect: 0 1 2 3 4
+ printf("\n");
+ for (int i = 0; i < rs3; i++)
+ printf("%d ", gdtrb3[i]); // expect: NULL
+ printf("\n");
+ free(gdtrb1), free(gdtrb2), free(gdtrb3);
+}
diff --git a/find_good_days_rob_bank.py b/find_good_days_rob_bank.py
new file mode 100644
index 0000000..ab5c808
--- /dev/null
+++ b/find_good_days_rob_bank.py
@@ -0,0 +1,46 @@
+# 2100. Find Good Days to Rob the Bank
+
+"""
+you and a gang of thieves are planning on robbing a bank. you are given a
+0-indexed integer array 'security' where 'security[i]' is the number of
+guards on duty on the i'th day. the days are numbered starting from 0. you
+are also given an integer 'time'. the i'th day is a good day to rob the bank
+if there are at least 'time' days before and after the i'th day, the number
+of guards at the bank for the 'time' days before/after 'i' are
+non-increasing/non-decreasing. return a list of all days (0-indexed) that are
+good days to rob the bank. the order that the days are returned in does not
+matter
+"""
+
+
+class Solution(object):
+ def goodDaysToRobBank(self, security, time):
+ """
+ :type security: List[int]
+ :type time: int
+ :rtype: List[int]
+ """
+ left, right = [1], [1]
+ n, curr = len(security), 1
+ for i in range(1, n):
+ if security[i] <= security[i - 1]:
+ curr += 1
+ else:
+ curr = 1
+ left.append(curr)
+ curr = 1
+ for i in range(n - 2, -1, -1):
+ if security[i] <= security[i + 1]:
+ curr += 1
+ else:
+ curr = 1
+ right.append(curr)
+ right.reverse()
+ return [i for i in range(n) if left[i] >= time + 1 and right[i] >= time + 1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.goodDaysToRobBank(security=[5, 3, 3, 3, 5, 6, 2], time=2))
+ print(obj.goodDaysToRobBank(security=[1, 1, 1, 1, 1], time=0))
+ print(obj.goodDaysToRobBank(security=[1, 2, 3, 4, 5, 6], time=2))