aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--most_beautiful_item_query.c82
-rw-r--r--most_beautiful_item_query.py36
2 files changed, 118 insertions, 0 deletions
diff --git a/most_beautiful_item_query.c b/most_beautiful_item_query.c
new file mode 100644
index 0000000..42749fd
--- /dev/null
+++ b/most_beautiful_item_query.c
@@ -0,0 +1,82 @@
+// 2070. Most Beautiful Item for Each Query
+#include "leetcode.h"
+
+/*
+ * you are given a 2d integer array 'items' where 'items[i] = [price_i,
+ * beauty_i]' denotes the price and beauty of an item respectively. you are also
+ * given a 0-indexed integer array 'queries'. for each 'queries[i]' you want to
+ * determine the maximum beauty of an item whose price is less than or equal to
+ * 'queries[i]'. if no such item exists, then the answer to this query is 0.
+ * return an array 'answer' of the same length as 'queries' where 'answer[i]' is
+ * the answer to the i'th query.
+ */
+
+int cmp(const void *a, const void *b) {
+ int *aa = *(int **)a;
+ int *bb = *(int **)b;
+ if (aa[0] != bb[0])
+ return aa[0] - bb[0];
+ return aa[1] - bb[1];
+}
+
+int binsearch(int **items, int n, int target) {
+ int left = 0, right = n - 1, res = -1;
+ while (left <= right) {
+ int mid = left + (right - left) / 2;
+ if (items[mid][0] <= target) {
+ res = mid;
+ left = mid + 1;
+ } else
+ right = mid - 1;
+ }
+ return res;
+}
+
+int *maximumBeauty(int **items, int itemsSize, int *itemsColSize, int *queries,
+ int queriesSize, int *returnSize) {
+ int *ans = (int *)malloc(queriesSize * sizeof(int));
+ qsort(items, itemsSize, sizeof(items), cmp);
+ int *max = (int *)malloc(itemsSize * sizeof(int)), curr_max = -1;
+ for (int i = 0; i < itemsSize; i++) {
+ max[i] = fmax(curr_max, items[i][1]);
+ curr_max = max[i];
+ }
+ for (int i = 0; i < queriesSize; i++) {
+ int valid = binsearch(items, itemsSize, queries[i]);
+ if (valid == -1) {
+ ans[i] = 0;
+ continue;
+ }
+ ans[i] = max[valid];
+ }
+ *returnSize = queriesSize;
+ return ans;
+}
+
+int main() {
+ int i1i[5][2] = {{1, 2}, {3, 2}, {2, 4}, {5, 6}, {3, 5}},
+ q1[] = {1, 2, 3, 4, 5, 6}, rs1;
+ int i2i[4][2] = {{1, 2}, {1, 2}, {1, 3}, {1, 4}}, q2[] = {1}, rs2;
+ int i3i[1][2] = {{10, 1000}}, q3[] = {5}, rs3;
+ struct two_d_arr i1, i2, i3;
+ two_d_arr_init(&i1, 5, 2, i1i);
+ two_d_arr_init(&i2, 4, 2, i2i);
+ two_d_arr_init(&i3, 1, 2, i3i);
+ int *mb1 =
+ maximumBeauty(i1.arr, i1.row_size, i1.col_size, q1, ARRAY_SIZE(q1), &rs1);
+ int *mb2 =
+ maximumBeauty(i2.arr, i2.row_size, i2.col_size, q2, ARRAY_SIZE(q2), &rs2);
+ int *mb3 =
+ maximumBeauty(i3.arr, i3.row_size, i3.col_size, q3, ARRAY_SIZE(q3), &rs3);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", mb1[i]); // expect: 2 4 5 5 6 6
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", mb2[i]); // expect: 4
+ printf("\n");
+ for (int i = 0; i < rs3; i++)
+ printf("%d ", mb3[i]); // expect: 0
+ printf("\n");
+ free(mb1), free(mb2), free(mb3);
+ two_d_arr_free(&i1), two_d_arr_free(&i2), two_d_arr_free(&i3);
+}
diff --git a/most_beautiful_item_query.py b/most_beautiful_item_query.py
new file mode 100644
index 0000000..abf8d53
--- /dev/null
+++ b/most_beautiful_item_query.py
@@ -0,0 +1,36 @@
+# 2070. Most Beautiful Item for Each Query
+from bisect import bisect
+
+"""
+you are given a 2d integer array 'items' where 'items[i] = [price_i,
+beauty_i]' denotes the price and beauty of an item respectively. you are also
+given a 0-indexed integer array 'queries'. for each 'queries[i]' you want to
+determine the maximum beauty of an item whose price is less than or equal to
+'queries[i]'. if no such item exists, then the answer to this query is 0.
+return an array 'answer' of the same length as 'queries' where 'answer[i]' is
+the answer to the i'th query.
+"""
+
+
+class Solution(object):
+ def maximumBeauty(self, items, queries):
+ """
+ :type items: List[List[int]]
+ :type queries: List[int]
+ :rtype: List[int]
+ """
+ items = sorted(items + [[0, 0]])
+ for i in range(len(items) - 1):
+ items[i + 1][1] = max(items[i][1], items[i + 1][1])
+ return [items[bisect(items, [q + 1]) - 1][1] for q in queries]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maximumBeauty(
+ items=[[1, 2], [3, 2], [2, 4], [5, 6], [3, 5]], queries=[1, 2, 3, 4, 5, 6]
+ )
+ )
+ print(obj.maximumBeauty(items=[[1, 2], [1, 2], [1, 3], [1, 4]], queries=[1]))
+ print(obj.maximumBeauty(items=[[10, 1000]], queries=[5]))