Added 2 solutions

varunu28 · varunu28 · commit b0e07ae7dbae · 2020-02-02T20:24:19.000-08:00
diff --git a/Easy/The K Weakest Rows in a Matrix.java b/Easy/The K Weakest Rows in a Matrix.java
@@ -0,0 +1,40 @@
+class Solution {
+  public int[] kWeakestRows(int[][] mat, int k) {
+    Map<Integer, Integer> map = new HashMap<>();
+    for (int i = 0; i < mat.length; i++) {
+      map.put(i, getLastIndex(mat[i], 0, mat[i].length - 1) + 1);
+    }
+    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
+      public int compare(Integer o1, Integer o2) {
+        int c = map.get(o1) - map.get(o2);
+        if (c != 0) {
+          return c;
+        }
+        return o1 - o2;
+      }
+    });
+    for (int i = 0; i < mat.length; i++) {
+      pq.add(i);
+    }
+    int[] ans = new int[k];
+    for (int i = 0; i < k; i++) {
+      ans[i] = pq.poll();
+    }
+    return ans;
+  }
+  
+  private int getLastIndex(int[] arr, int start, int end) {
+    int idx = -1;
+    while (start <= end) {
+      int mid = (start + end) / 2;
+      if (arr[mid] == 1) {
+        idx = Math.max(idx, mid);
+        start = mid + 1;
+      }
+      else {
+        end = mid - 1;
+      }
+    }
+    return idx;
+  }
+}
diff --git a/Medium/Reduce Array Size to The Half.java b/Medium/Reduce Array Size to The Half.java
@@ -0,0 +1,24 @@
+class Solution {
+  public int minSetSize(int[] arr) {
+    Map<Integer, Integer> map = new HashMap<>();
+    for (int num : arr) {
+      map.put(num, map.getOrDefault(num, 0) + 1);
+    }
+    PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
+      public int compare(Integer o1, Integer o2) {
+        return map.get(o2) - map.get(o1);
+      }
+    });
+    for (Integer key : map.keySet()) {
+      pq.add(key);
+    }
+    int n = arr.length / 2;
+    int currSize = 0;
+    int count = 0;
+    while (currSize < n) {
+      currSize += map.get(pq.poll());
+      count++;
+    }
+    return count;
+  }
+}
