Medium

![https://leetcode.com/problems/largest-values-from-labels/] We have a set of items: the i-th item has value values[i] and label labels[i]. Then, we choose a subset S of these items, such that: |S| <= num_wanted For every label L, the number of items in S with label L is <= use_limit. Return the largest possible sum of the subset S. Example 1: Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1 Output: 9 Explanation: The subset chosen is the first, third, and fifth item. Example 2: Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2 Output: 12 Explanation: The subset chosen is the first, second, and third item. Example 3: Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1 Output: 16 Explanation: The subset chosen is the first and fourth item. Example 4: Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2 Output: 24 Explanation: The subset chosen is the first, second, and fourth item. Note: ...

![https://leetcode.com/problems/search-a-2d-matrix-ii/] Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Example 1: Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true Example 2: Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false Constraints: ...

![https://leetcode.com/problems/widest-vertical-area-between-two-points-containing-no-points/] Given n points on a 2D plane where points[i] = [xi, yi], Return the widest vertical area between two points such that no points are inside the area. A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width. Note that points on the edge of a vertical area are not considered included in the area. ...

![https://leetcode.com/problems/k-closest-points-to-origin/] We have a list of points on the plane. Find the K closest points to the origin (0, 0). (Here, the distance between two points on a plane is the Euclidean distance.) You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.) Example 1: Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]]. Example 2: Input: points = [[3,3],[5,-1],[-2,4]], K = 2 Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.) Note: ...

![https://leetcode.com/problems/majority-element/] Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 Constraints: n == nums.length 1 <= n <= 5 * 104 -231 <= nums[i] <= 231 - 1 Follow-up: Could you solve the problem in linear time and in O(1) space? ...

![https://leetcode.com/problems/kth-largest-element-in-an-array/] Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2: Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 Note: You may assume k is always valid, 1 ≤ k ≤ array’s length. class Solution { public int findKthLargest(int[] nums, int k) { int lo = 0; int hi = nums.length - 1; k = nums.length - k; while (lo < hi) { int j = partition(nums, lo, hi); if (j < k) { lo = j + 1; } else if (j > k) { hi = j - 1; } else { return nums[k]; } } return nums[k]; } int partition(int[] a, int lo, int hi) { int i = lo; int j = hi + 1; while (true) { while (a[++i] < a[lo]) { if (i == hi) break; } while (a[lo] < a[--j]) { if (j == lo) break; } if (i >= j) break; swap(a, i, j); } swap(a, lo, j); return j; } void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }

![https://leetcode.com/problems/remove-outermost-parentheses/] There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [a, b] represents a connection between computers a and b. Any computer can reach any other computer directly or indirectly through the network. Given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it’s not possible, return -1. ...

![https://leetcode.com/problems/evaluate-reverse-polish-notation/] Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation. Example 1: Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Example 2: Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Example 3: Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 class Solution { public int evalRPN(String[] tokens) { int[] stack = new int[tokens.length]; int size = 0; for (String token: tokens) { if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/") ) { int b = stack[--size]; int a = stack[--size]; int c; switch (token) { case "+": c = a + b; break; case "-": c = a - b; break; case "*": c = a * b; break; case "/": c = a / b; break; default: throw new RuntimeException(); } stack[size++] = c; } else { stack[size++] = Integer.valueOf(token); } } return stack[0]; } }

![https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/] Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together. We repeatedly make k duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique. Example 1: Input: s = "abcd", k = 2 Output: "abcd" Explanation: There's nothing to delete. Example 2: Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation: First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa" Example 3: Input: s = "pbbcggttciiippooaais", k = 2 Output: "ps" Constraints: ...

![https://leetcode.com/problems/basic-calculator-ii/] Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. Example 1: Input: s = "3+2*2" Output: 7 Example 2: Input: s = " 3/2 " Output: 1 Example 3: Input: s = " 3+5 / 2 " Output: 5 Constraints: 1 <= s.length <= 3 * 105 s consists of integers and operators (’+’, ‘-’, ‘*’, ‘/’) separated by some number of spaces. s represents a valid expression. All the integers in the expression are non-negative integers in the range [0, 231 - 1]. The answer is guaranteed to fit in a 32-bit integer. class Solution { public int calculate(String s) { var values = new int[s.length()]; var signs = new char[s.length()]; int valuesSize = 0; int signsSize = 0; char[] symbols = s.toCharArray(); for (int i = 0; i < symbols.length; i++) { char c = symbols[i]; if (c == ' ') { continue; } if (Character.isDigit(c)) { int j = i; int val = 0; while (j < symbols.length && Character.isDigit(symbols[j])) { val = (val * 10) + (symbols[j] - '0'); j++; } i = j - 1; if (signsSize > 0) { char op = signs[signsSize - 1]; if (op == '*' || op == '/') { signsSize--; int prev = values[valuesSize - 1]; valuesSize--; if (op == '*') { val = val * prev; } else { val = prev / val; } } } values[valuesSize++] = val; } else { signs[signsSize++] = c; } // System.out.println("signs = " + Arrays.toString(signs)); // System.out.println("values = " + Arrays.toString(values)); } int j = 0; int res = values[0]; for (int i = 0; i < valuesSize - 1; i++) { char op = signs[j++]; int a = values[i]; int b = values[i + 1]; res = (op == '+') ? a + b : a - b; values[i + 1] = res; } return res; } }