aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-09 22:29:19 +0100
committerJack Sangdahl <[email protected]>2025-01-09 22:29:19 +0100
commit8050c7264ba4487a1e64b150633961097382ac5b (patch)
tree940e0429a5caf113d28a171b2365e79df0af5af4
parent2d159f42638f87dfca97a0ab50099b0eef651e5e (diff)
downloadleetcode-8050c7264ba4487a1e64b150633961097382ac5b.tar.gz
leetcode-8050c7264ba4487a1e64b150633961097382ac5b.zip
354. russian doll envelopes
-rw-r--r--russian_doll_envelopes.c60
-rw-r--r--russian_doll_envelopes.cpp28
-rw-r--r--russian_doll_envelopes.py33
3 files changed, 93 insertions, 28 deletions
diff --git a/russian_doll_envelopes.c b/russian_doll_envelopes.c
new file mode 100644
index 0000000..0849180
--- /dev/null
+++ b/russian_doll_envelopes.c
@@ -0,0 +1,60 @@
+// 354. Russian Doll Envelopes
+#include "leetcode.h"
+
+/*
+ * you are given a 2d array of integers 'envelopes' where 'envelopes[i] = [w_i,
+ * h_i]' represents the width and height of an envelope. one envelope can fit
+ * into another if and only if both the width and height of one envelope are
+ * greater than the other envelope's width and height. return the maximum number
+ * of envelopes you can russian doll (ie. put one inside the other).
+ */
+
+int bin_search(int *dp, int start, int end, int target) {
+ while (start < end) {
+ int mid = start + (end - start) / 2;
+ if (dp[mid] == target)
+ return mid;
+ else if (dp[mid] > target)
+ end = mid;
+ else
+ start = mid + 1;
+ }
+ return start;
+}
+
+int cmp(const void *a, const void *b) {
+ if ((*(int **)a)[0] == (*(int **)b)[0])
+ return (*(int **)b)[1] - (*(int **)a)[1];
+ else
+ return (*(int **)a)[0] - (*(int **)b)[0];
+}
+
+int maxEnvelopes(int **envelopes, int envelopesSize, int *envelopesColSize) {
+ qsort(envelopes, envelopesSize, sizeof(int **), cmp);
+ int *dp = (int *)malloc(envelopesSize * sizeof(int)), ans = 0;
+ dp[0] = envelopes[0][1];
+ for (int i = 1; i < envelopesSize; i++) {
+ if (envelopes[i][1] > dp[ans - 1])
+ dp[ans++] = envelopes[i][1];
+ else {
+ int idx = bin_search(dp, 0, ans, envelopes[i][1]);
+ dp[idx] = envelopes[i][1];
+ if (idx == ans)
+ ans++;
+ }
+ }
+ free(dp);
+ return ans;
+}
+
+int main() {
+ int e1i[4][2] = {{5, 4}, {6, 4}, {6, 7}, {2, 3}},
+ e2i[3][2] = {{1, 1}, {1, 1}, {1, 1}};
+ struct two_d_arr e1, e2;
+ two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
+ two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
+ printf("%d\n", maxEnvelopes(e1.arr, e1.row_size, e1.col_size)); // expect: 3
+ printf("%d\n", maxEnvelopes(e2.arr, e2.row_size, e2.col_size)); // expect: 1
+ two_d_arr_free(&e1);
+ two_d_arr_free(&e2);
+}
diff --git a/russian_doll_envelopes.cpp b/russian_doll_envelopes.cpp
deleted file mode 100644
index fce0aa3..0000000
--- a/russian_doll_envelopes.cpp
+++ /dev/null
@@ -1,28 +0,0 @@
-#include "leetcode.h"
-
-class Solution {
-public:
- int maxEnvelopes(vector<vector<int>> &envelopes) {
- int n = envelopes.size();
- sort(envelopes.begin(), envelopes.end(), compare);
- vector<int> ans;
- for (int i = 0; i < envelopes.size(); i++) {
- int candidate = envelopes[i][1];
- int idx = lower_bound(ans.begin(), ans.end(), candidate) - ans.begin();
- if (idx >= ans.size())
- ans.push_back(candidate);
- else
- ans[idx] = candidate;
- }
- return ans.size();
- }
-
-private:
- static bool compare(vector<int> &a, vector<int> &b) {
- if (a[0] == b[0])
- return a[1] > b[1];
- return a[0] < b[0];
- }
-};
-
-int main() {}
diff --git a/russian_doll_envelopes.py b/russian_doll_envelopes.py
new file mode 100644
index 0000000..99731e7
--- /dev/null
+++ b/russian_doll_envelopes.py
@@ -0,0 +1,33 @@
+# 354. Russian Doll envelopesnvelopes
+from bisect import bisect_left
+
+"""
+you are given a 2d array of integers 'envelopes' where 'envelopes[i] = [w_i,
+h_i]' represents the width and height of an envelope. one envelope can fit
+into another if and only if both the width and height of one envelope are
+greater than the other envelope's width and height. return the maximum number
+of envelopes you can russian doll (ie. put one inside the other).
+"""
+
+
+class Solution(object):
+ def maxenvelopesnvelopes(self, envelopes):
+ """
+ :type envelopes: List[List[int]]
+ :rtype: int
+ """
+ envelopes.sort(key=lambda x: (x[0], -x[1]))
+ dp = []
+ for _, height in envelopes:
+ left = bisect_left(dp, height)
+ if left == len(dp):
+ dp.append(height)
+ else:
+ dp[left] = height
+ return len(dp)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxenvelopesnvelopes(envelopes=[[5, 4], [6, 4], [6, 7], [2, 3]]))
+ print(obj.maxenvelopesnvelopes(envelopes=[[1, 1], [1, 1], [1, 1]]))