NeetCode 150

Complete Java Solutions

All 149 problems with Java solutions, organized by category

Arrays & Hashing
Contains Duplicate
Difficulty: Easy
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int n : nums) {
if () return true;
}
return false;
}
}

Valid Anagram
Difficulty: Easy
class Solution {
public boolean isAnagram(String s, String t) {
if ([Link]() != [Link]()) return false;
int[] count = new int[26];
for (char c : [Link]()) count[c - 'a']++;
for (char c : [Link]()) count[c - 'a']--;
for (int v : count) if (v != 0) return false;
return true;
}
}

Two Sum
Difficulty: Easy
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < [Link]; i++) {
int comp = target - nums[i];
if ([Link](comp)) return new int[]{[Link](comp), i};
[Link](nums[i], i);
}
return new int[]{};
}
}

Group Anagrams
Difficulty: Medium
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] arr = [Link]();
[Link](arr);
String key = new String(arr);
 [Link](key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>([Link]());
}
}

Top K Frequent Elements

Difficulty: Medium
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) [Link](n, 1, Integer::sum);
List<Integer>[] bucket = new List[[Link] + 1];
for (int key : [Link]()) {
int f = [Link](key);
if (bucket[f] == null) bucket[f] = new ArrayList<>();
bucket[f].add(key);
}
int[] res = new int[k];
int idx = 0;
for (int i = [Link] - 1; i >= 0 && idx < k; i--)
if (bucket[i] != null)
for (int n : bucket[i]) if (idx < k) res[idx++] = n;
return res;
}
}

Encode and Decode Strings

Difficulty: Medium
public class Codec {
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String s : strs) [Link]([Link]()).append('#').append(s);
return [Link]();
}
public List<String> decode(String s) {
List<String> res = new ArrayList<>();
int i = 0;
while (i < [Link]()) {
int j = [Link]('#', i);
int len = [Link]([Link](i, j));
[Link]([Link](j + 1, j + 1 + len));
i = j + 1 + len;
}
return res;
}
}

Product of Array Except Self

Difficulty: Medium
class Solution {
 public int[] productExceptSelf(int[] nums) {
int n = [Link];
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) res[i] = res[i-1] * nums[i-1];
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}
}

Valid Sudoku
Difficulty: Medium
class Solution {
public boolean isValidSudoku(char[][] board) {
Set<String> seen = new HashSet<>();
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
char ch = board[r][c];
if (ch == '.') continue;
String row = "r" + r + ch, col = "c" + c + ch;
String box = "b" + (r/3) + (c/3) + ch;
if ( ||  || )
return false;
}
}
return true;
}
}

Longest Consecutive Sequence

Difficulty: Medium
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) [Link](n);
int best = 0;
for (int n : set) {
if () {
int cur = n, len = 1;
while ([Link](cur + 1)) { cur++; len++; }
best = [Link](best, len);
}
}
return best;
}
}
Two Pointers
Valid Palindrome
Difficulty: Easy
class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = [Link]() - 1;
while (l < r) {
while (l < r && )) l++;
while (l < r && )) r--;
if ([Link]([Link](l)) != [Link]([Link](r)))
return false;
l++; r--;
}
return true;
}
}

Two Sum II - Input Array Is Sorted

Difficulty: Medium
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = [Link] - 1;
while (l < r) {
int sum = numbers[l] + numbers[r];
if (sum == target) return new int[]{l+1, r+1};
else if (sum < target) l++;
else r--;
}
return new int[]{};
}
}

3Sum
Difficulty: Medium
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
[Link](nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < [Link] - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i+1, r = [Link] - 1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s == 0) {
[Link]([Link](nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++; r--;
} else if (s < 0) l++;
else r--;
 }
}
return res;
}
}

Container With Most Water

Difficulty: Medium
class Solution {
public int maxArea(int[] height) {
int l = 0, r = [Link] - 1, max = 0;
while (l < r) {
max = [Link](max, [Link](height[l], height[r]) * (r - l));
if (height[l] < height[r]) l++;
else r--;
}
return max;
}
}

Trapping Rain Water

Difficulty: Hard
class Solution {
public int trap(int[] height) {
int l = 0, r = [Link] - 1, lMax = 0, rMax = 0, res = 0;
while (l < r) {
if (height[l] <= height[r]) {
lMax = [Link](lMax, height[l]);
res += lMax - height[l++];
} else {
rMax = [Link](rMax, height[r]);
res += rMax - height[r--];
}
}
return res;
}
}

Sliding Window
Best Time to Buy and Sell Stock
Difficulty: Easy
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, maxProfit = 0;
for (int p : prices) {
minPrice = [Link](minPrice, p);
maxProfit = [Link](maxProfit, p - minPrice);
}
return maxProfit;
 }
}

Longest Substring Without Repeating Characters

Difficulty: Medium
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int max = 0, l = 0;
for (int r = 0; r < [Link](); r++) {
char c = [Link](r);
if ([Link](c)) l = [Link](l, [Link](c) + 1);
[Link](c, r);
max = [Link](max, r - l + 1);
}
return max;
}
}

Longest Repeating Character Replacement

Difficulty: Medium
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int maxCount = 0, max = 0, l = 0;
for (int r = 0; r < [Link](); r++) {
maxCount = [Link](maxCount, ++count[[Link](r) - 'A']);
while ((r - l + 1) - maxCount > k) count[[Link](l++) - 'A']--;
max = [Link](max, r - l + 1);
}
return max;
}
}

Permutation in String
Difficulty: Medium
class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] c1 = new int[26], c2 = new int[26];
for (char c : [Link]()) c1[c-'a']++;
for (int i = 0; i < [Link](); i++) {
c2[[Link](i)-'a']++;
if (i >= [Link]()) c2[[Link]([Link]())-'a']--;
if ([Link](c1, c2)) return true;
}
return false;
}
}

Minimum Window Substring

Difficulty: Hard
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> need = new HashMap<>();
for (char c : [Link]()) [Link](c,1,Integer::sum);
int l=0, formed=0, req=[Link](), minLen=Integer.MAX_VALUE, minL=0;
Map<Character,Integer> window = new HashMap<>();
for (int r = 0; r < [Link](); r++) {
char c = [Link](r);
[Link](c,1,Integer::sum);
if ([Link](c) && [Link](c).equals([Link](c))) formed++;
while (formed == req) {
if (r-l+1 < minLen) { minLen=r-l+1; minL=l; }
char lc = [Link](l++);
[Link](lc,-1,Integer::sum);
if ([Link](lc) && [Link](lc) < [Link](lc)) formed--;
}
}
return minLen == Integer.MAX_VALUE ? "" : [Link](minL, minL+minLen);
}
}

Sliding Window Maximum

Difficulty: Hard
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = [Link];
int[] res = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (![Link]() && [Link]() < i - k + 1) [Link]();
while (![Link]() && nums[[Link]()] < nums[i]) [Link]();
[Link](i);
if (i >= k - 1) res[i - k + 1] = nums[[Link]()];
}
return res;
}
}

Stack
Valid Parentheses
Difficulty: Easy
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : [Link]()) {
if (c=='(' || c=='{' || c=='[') [Link](c);
else {
if ([Link]()) return false;
char top = [Link]();
 if (c==')' && top!='(') return false;
if (c=='}' && top!='{') return false;
if (c==']' && top!='[') return false;
}
}
return [Link]();
}
}

Min Stack
Difficulty: Medium
class MinStack {
private Deque<int[]> stack = new ArrayDeque<>();
public void push(int val) {
int min = [Link]() ? val : [Link](val, [Link]()[1]);
[Link](new int[]{val, min});
}
public void pop() { [Link](); }
public int top() { return [Link]()[0]; }
public int getMin() { return [Link]()[1]; }
}

Evaluate Reverse Polish Notation

Difficulty: Medium
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String t : tokens) {
if ("+-*/".contains(t)) {
int b = [Link](), a = [Link]();
switch(t) {
case "+": [Link](a+b); break;
case "-": [Link](a-b); break;
case "*": [Link](a*b); break;
case "/": [Link](a/b); break;
}
} else [Link]([Link](t));
}
return [Link]();
}
}

Generate Parentheses
Difficulty: Medium
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(res, "", 0, 0, n);
return res;
}
void backtrack(List<String> res, String s, int open, int close, int n) {
 if ([Link]() == 2*n) { [Link](s); return; }
if (open < n) backtrack(res, s+"(", open+1, close, n);
if (close < open) backtrack(res, s+")", open, close+1, n);
}
}

Daily Temperatures
Difficulty: Medium
class Solution {
public int[] dailyTemperatures(int[] temps) {
int n = [Link];
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (![Link]() && temps[i] > temps[[Link]()]) {
int idx = [Link]();
res[idx] = i - idx;
}
[Link](i);
}
return res;
}
}

Car Fleet
Difficulty: Medium
class Solution {
public int carFleet(int target, int[] pos, int[] speed) {
int n = [Link];
double[][] cars = new double[n][2];
for (int i = 0; i < n; i++) cars[i] = new double[]{pos[i], (double)(target-pos[i])/speed[i]};
[Link](cars, (a,b) -> [Link](b[0], a[0]));
int fleets = 0;
double maxTime = 0;
for (double[] car : cars) {
if (car[1] > maxTime) { fleets++; maxTime = car[1]; }
}
return fleets;
}
}

Binary Search
Binary Search
Difficulty: Easy
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = [Link] - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
 if (nums[mid] == target) return mid;
else if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
}
}

Search a 2D Matrix
Difficulty: Medium
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = [Link], n = matrix[0].length;
int l = 0, r = m*n - 1;
while (l <= r) {
int mid = l + (r-l)/2;
int val = matrix[mid/n][mid%n];
if (val == target) return true;
else if (val < target) l = mid+1;
else r = mid-1;
}
return false;
}
}

Koko Eating Bananas

Difficulty: Medium
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int l = 1, r = [Link](piles).max().getAsInt();
while (l < r) {
int mid = l + (r-l)/2;
long hours = 0;
for (int p : piles) hours += (p + mid - 1) / mid;
if (hours <= h) r = mid;
else l = mid+1;
}
return l;
}
}

Find Minimum in Rotated Sorted Array

Difficulty: Medium
class Solution {
public int findMin(int[] nums) {
int l = 0, r = [Link] - 1;
while (l < r) {
int mid = l + (r-l)/2;
if (nums[mid] > nums[r]) l = mid+1;
else r = mid;
}
 return nums[l];
}
}

Search in Rotated Sorted Array

Difficulty: Medium
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = [Link] - 1;
while (l <= r) {
int mid = l + (r-l)/2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) {
if (target >= nums[l] && target < nums[mid]) r = mid-1;
else l = mid+1;
} else {
if (target > nums[mid] && target <= nums[r]) l = mid+1;
else r = mid-1;
}
}
return -1;
}
}

Time Based Key-Value Store

Difficulty: Medium
class TimeMap {
Map<String, List<int[]>> map = new HashMap<>();
public void set(String key, String value, int timestamp) {
[Link](key, k->new ArrayList<>())
.add(new int[]{timestamp, [Link]()});
}
// Simplified: real solution stores strings
}

Median of Two Sorted Arrays

Difficulty: Hard
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if ([Link] > [Link]) return findMedianSortedArrays(nums2, nums1);
int m=[Link], n=[Link], half=(m+n+1)/2;
int l=0, r=m;
while (l <= r) {
int i=l+(r-l)/2, j=half-i;
if (i<m && nums2[j-1]>nums1[i]) l=i+1;
else if (i>0 && nums1[i-1]>nums2[j]) r=i-1;
else {
int maxLeft = [Link](i>0?nums1[i-1]:Integer.MIN_VALUE,
j>0?nums2[j-1]:Integer.MIN_VALUE);
if ((m+n)%2==1) return maxLeft;
int minRight = [Link](i<m?nums1[i]:Integer.MAX_VALUE,
 j<n?nums2[j]:Integer.MAX_VALUE);
return (maxLeft+minRight)/2.0;
}
}
return 0;
}
}

Linked List
Reverse Linked List
Difficulty: Easy
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = [Link];
[Link] = prev;
prev = cur;
cur = next;
}
return prev;
}
}

Merge Two Sorted Lists

Difficulty: Easy
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), cur = dummy;
while (l1 != null && l2 != null) {
if ([Link] <= [Link]) { [Link] = l1; l1 = [Link]; }
else { [Link] = l2; l2 = [Link]; }
cur = [Link];
}
[Link] = l1 != null ? l1 : l2;
return [Link];
}
}

Reorder List
Difficulty: Medium
class Solution {
public void reorderList(ListNode head) {
// Find middle
ListNode slow=head, fast=[Link];
while (fast != null && [Link] != null) { slow=[Link]; fast=[Link]; }
// Reverse second half
ListNode second=[Link], prev=null; [Link]=null;
while (second != null) { ListNode tmp=[Link]; [Link]=prev; prev=second; second=tmp; }
 // Merge
ListNode first=head; second=prev;
while (second != null) {
ListNode t1=[Link], t2=[Link];
[Link]=second; [Link]=t1;
first=t1; second=t2;
}
}
}

Remove Nth Node From End of List

Difficulty: Medium
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0); [Link] = head;
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) fast = [Link];
while (fast != null) { fast = [Link]; slow = [Link]; }
[Link] = [Link];
return [Link];
}
}

Copy List with Random Pointer

Difficulty: Medium
class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> map = new HashMap<>();
Node cur = head;
while (cur != null) { [Link](cur, new Node([Link])); cur = [Link]; }
cur = head;
while (cur != null) {
[Link](cur).next = [Link]([Link]);
[Link](cur).random = [Link]([Link]);
cur = [Link];
}
return [Link](head);
}
}

Add Two Numbers

Difficulty: Medium
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), cur = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) { sum += [Link]; l1 = [Link]; }
if (l2 != null) { sum += [Link]; l2 = [Link]; }
carry = sum / 10;
 [Link] = new ListNode(sum % 10);
cur = [Link];
}
return [Link];
}
}

Linked List Cycle

Difficulty: Easy
class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link]; fast = [Link];
if (slow == fast) return true;
}
return false;
}
}

Find the Duplicate Number

Difficulty: Medium
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);
slow = nums[0];
while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }
return slow;
}
}

LRU Cache
Difficulty: Medium
class LRUCache {
private final int cap;
private final Map<Integer, Integer> map;
public LRUCache(int capacity) {
[Link] = capacity;
[Link] = new LinkedHashMap<>(capacity, 0.75f, true) {
protected boolean removeEldestEntry([Link] e) { return size() > cap; }
};
}
public int get(int key) { return [Link](key, -1); }
public void put(int key, int value) { [Link](key, value); }
}

Merge K Sorted Lists

Difficulty: Hard
 class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->[Link]);
for (ListNode l : lists) if (l != null) [Link](l);
ListNode dummy = new ListNode(0), cur = dummy;
while (![Link]()) {
[Link] = [Link](); cur = [Link];
if ([Link] != null) [Link]([Link]);
}
return [Link];
}
}

Reverse Nodes in k-Group

Difficulty: Hard
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode cur = head; int count = 0;
while (cur != null && count < k) { cur = [Link]; count++; }
if (count < k) return head;
ListNode prev = null, node = head;
for (int i = 0; i < k; i++) { ListNode tmp = [Link]; [Link] = prev; prev = node; node = tmp; }
[Link] = reverseKGroup(node, k);
return prev;
}
}

Trees
Invert Binary Tree
Difficulty: Easy
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode tmp = [Link];
[Link] = invertTree([Link]);
[Link] = invertTree(tmp);
return root;
}
}

Maximum Depth of Binary Tree

Difficulty: Easy
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + [Link](maxDepth([Link]), maxDepth([Link]));
}
}
Diameter of Binary Tree
Difficulty: Easy
class Solution {
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root); return ans;
}
int depth(TreeNode node) {
if (node == null) return 0;
int l = depth([Link]), r = depth([Link]);
ans = [Link](ans, l + r);
return 1 + [Link](l, r);
}
}

Balanced Binary Tree

Difficulty: Easy
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
int height(TreeNode node) {
if (node == null) return 0;
int l = height([Link]), r = height([Link]);
if (l == -1 || r == -1 || [Link](l-r) > 1) return -1;
return 1 + [Link](l, r);
}
}

Same Tree
Difficulty: Easy
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null || [Link] != [Link]) return false;
return isSameTree([Link], [Link]) && isSameTree([Link], [Link]);
}
}

Subtree of Another Tree

Difficulty: Easy
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (isSame(root, subRoot)) return true;
return isSubtree([Link], subRoot) || isSubtree([Link], subRoot);
}
boolean isSame(TreeNode a, TreeNode b) {
if (a==null && b==null) return true;
if (a==null || b==null || [Link]!=[Link]) return false;
 return isSame([Link],[Link]) && isSame([Link],[Link]);
}
}

Lowest Common Ancestor of a BST

Difficulty: Medium
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if ([Link] < [Link] && [Link] < [Link]) return lowestCommonAncestor([Link], p, q);
if ([Link] > [Link] && [Link] > [Link]) return lowestCommonAncestor([Link], p, q);
return root;
}
}

Binary Tree Level Order Traversal

Difficulty: Medium
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
[Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level);
}
return res;
}
}

Binary Tree Right Side View

Difficulty: Medium
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
if (i == size-1) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
 if ([Link] != null) [Link]([Link]);
}
}
return res;
}
}

Count Good Nodes in Binary Tree

Difficulty: Medium
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, Integer.MIN_VALUE);
}
int dfs(TreeNode node, int maxSoFar) {
if (node == null) return 0;
int good = [Link] >= maxSoFar ? 1 : 0;
int newMax = [Link](maxSoFar, [Link]);
return good + dfs([Link], newMax) + dfs([Link], newMax);
}
}

Validate Binary Search Tree

Difficulty: Medium
class Solution {
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if ([Link] <= min || [Link] >= max) return false;
return validate([Link], min, [Link]) && validate([Link], [Link], max);
}
}

Kth Smallest Element in a BST

Difficulty: Medium
class Solution {
int k, result;
public int kthSmallest(TreeNode root, int k) {
this.k = k; inorder(root); return result;
}
void inorder(TreeNode node) {
if (node == null) return;
inorder([Link]);
if (--k == 0) result = [Link];
inorder([Link]);
}
}

Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer,Integer> idx = new HashMap<>();
for (int i = 0; i < [Link]; i++) [Link](inorder[i], i);
return build(preorder, idx, new int[]{0}, 0, [Link]-1);
}
TreeNode build(int[] pre, Map<Integer,Integer> idx, int[] pi, int l, int r) {
if (l > r) return null;
TreeNode node = new TreeNode(pre[pi[0]++]);
int mid = [Link]([Link]);
[Link] = build(pre, idx, pi, l, mid-1);
[Link] = build(pre, idx, pi, mid+1, r);
return node;
}
}

Binary Tree Maximum Path Sum

Difficulty: Hard
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
gain(root); return maxSum;
}
int gain(TreeNode node) {
if (node == null) return 0;
int l = [Link](gain([Link]), 0);
int r = [Link](gain([Link]), 0);
maxSum = [Link](maxSum, [Link] + l + r);
return [Link] + [Link](l, r);
}
}

Serialize and Deserialize Binary Tree

Difficulty: Hard
public class Codec {
public String serialize(TreeNode root) {
if (root==null) return "N,";
return [Link]+","+serialize([Link])+serialize([Link]);
}
public TreeNode deserialize(String data) {
Queue<String> q = new LinkedList<>([Link]([Link](",")));
return des(q);
}
TreeNode des(Queue<String> q) {
String val = [Link]();
if ([Link]("N")) return null;
TreeNode node = new TreeNode([Link](val));
[Link] = des(q); [Link] = des(q);
return node;
}
}
Heap / Priority Queue
Kth Largest Element in a Stream
Difficulty: Easy
class KthLargest {
PriorityQueue<Integer> pq;
int k;
public KthLargest(int k, int[] nums) {
this.k = k; pq = new PriorityQueue<>();
for (int n : nums) add(n);
}
public int add(int val) {
[Link](val);
if ([Link]() > k) [Link]();
return [Link]();
}
}

Last Stone Weight

Difficulty: Easy
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<>([Link]());
for (int s : stones) [Link](s);
while ([Link]() > 1) {
int a = [Link](), b = [Link]();
if (a != b) [Link](a - b);
}
return [Link]() ? 0 : [Link]();
}
}

K Closest Points to Origin

Difficulty: Medium
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->
(b[0]*b[0]+b[1]*b[1])-(a[0]*a[0]+a[1]*a[1]));
for (int[] p : points) {
[Link](p);
if ([Link]() > k) [Link]();
}
return [Link](new int[k][]);
}
}

Kth Largest Element in an Array

Difficulty: Medium
 class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) {
[Link](n);
if ([Link]() > k) [Link]();
}
return [Link]();
}
}

Task Scheduler
Difficulty: Medium
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char c : tasks) freq[c-'A']++;
int maxFreq = [Link](freq).max().getAsInt();
long maxCount = [Link](freq).filter(f->f==maxFreq).count();
return (int)[Link]([Link], (maxFreq-1)*(n+1)+maxCount);
}
}

Design Twitter
Difficulty: Medium
class Twitter {
private Map<Integer,Set<Integer>> following = new HashMap<>();
private List<int[]> tweets = new ArrayList<>();
private int time = 0;
public void postTweet(int userId, int tweetId) { [Link](new int[]{userId,tweetId,time++}); }
public List<Integer> getNewsFeed(int userId) {
Set<Integer> fl = [Link](userId, new HashSet<>());
return [Link]().filter(t->t[0]==userId||[Link](t[0]))
.sorted((a,b)->b[2]-a[2]).limit(10).map(t->t[1])
.collect([Link]());
}
public void follow(int f, int e) { [Link](f,k->new HashSet<>()).add(e); }
public void unfollow(int f, int e) { if ([Link](f)) [Link](f).remove(e); }
}

Find Median from Data Stream

Difficulty: Hard
class MedianFinder {
PriorityQueue<Integer> small = new PriorityQueue<>([Link]());
PriorityQueue<Integer> large = new PriorityQueue<>();
public void addNum(int num) {
[Link](num);
[Link]([Link]());
if ([Link]() < [Link]()) [Link]([Link]());
}
public double findMedian() {
 return [Link]() > [Link]() ? [Link]() : ([Link]()+[Link]())/2.0;
}
}

Backtracking
Subsets
Difficulty: Medium
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), nums, 0);
return res;
}
void backtrack(List<List<Integer>> res, List<Integer> curr, int[] nums, int start) {
[Link](new ArrayList<>(curr));
for (int i = start; i < [Link]; i++) {
[Link](nums[i]);
backtrack(res, curr, nums, i+1);
[Link]([Link]()-1);
}
}
}

Combination Sum
Difficulty: Medium
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), candidates, target, 0);
return res;
}
void backtrack(List<List<Integer>> res, List<Integer> curr, int[] cands, int remain, int start) {
if (remain == 0) { [Link](new ArrayList<>(curr)); return; }
for (int i = start; i < [Link]; i++) {
if (cands[i] <= remain) {
[Link](cands[i]);
backtrack(res, curr, cands, remain-cands[i], i);
[Link]([Link]()-1);
}
}
}
}

Permutations
Difficulty: Medium
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), nums);
 return res;
}
void backtrack(List<List<Integer>> res, List<Integer> curr, int[] nums) {
if ([Link]() == [Link]) { [Link](new ArrayList<>(curr)); return; }
for (int n : nums) {
if () {
[Link](n);
backtrack(res, curr, nums);
[Link]([Link]()-1);
}
}
}
}

Subsets II
Difficulty: Medium
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
[Link](nums);
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), nums, 0);
return res;
}
void backtrack(List<List<Integer>> res, List<Integer> curr, int[] nums, int start) {
[Link](new ArrayList<>(curr));
for (int i = start; i < [Link]; i++) {
if (i > start && nums[i] == nums[i-1]) continue;
[Link](nums[i]);
backtrack(res, curr, nums, i+1);
[Link]([Link]()-1);
}
}
}

Combination Sum II
Difficulty: Medium
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
[Link](candidates);
List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), candidates, target, 0);
return res;
}
void backtrack(List<List<Integer>> res, List<Integer> curr, int[] cands, int remain, int start) {
if (remain == 0) { [Link](new ArrayList<>(curr)); return; }
for (int i = start; i < [Link]; i++) {
if (i > start && cands[i] == cands[i-1]) continue;
if (cands[i] > remain) break;
[Link](cands[i]);
backtrack(res, curr, cands, remain-cands[i], i+1);
[Link]([Link]()-1);
}
 }
}

Word Search
Difficulty: Medium
class Solution {
public boolean exist(char[][] board, String word) {
int m=[Link], n=board[0].length;
for (int i=0;i<m;i++) for (int j=0;j<n;j++)
if (dfs(board,word,i,j,0)) return true;
return false;
}
boolean dfs(char[][] b, String w, int r, int c, int idx) {
if (idx==[Link]()) return true;
if (r<0||r>=[Link]||c<0||c>=b[0].length||b[r][c]!=[Link](idx)) return false;
char tmp=b[r][c]; b[r][c]='#';
boolean found=dfs(b,w,r+1,c,idx+1)||dfs(b,w,r-1,c,idx+1)||
dfs(b,w,r,c+1,idx+1)||dfs(b,w,r,c-1,idx+1);
b[r][c]=tmp;
return found;
}
}

Palindrome Partitioning
Difficulty: Medium
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), s, 0);
return res;
}
void backtrack(List<List<String>> res, List<String> curr, String s, int start) {
if (start == [Link]()) { [Link](new ArrayList<>(curr)); return; }
for (int end = start+1; end <= [Link](); end++) {
String sub = [Link](start, end);
if (isPalin(sub)) {
[Link](sub);
backtrack(res, curr, s, end);
[Link]([Link]()-1);
}
}
}
boolean isPalin(String s) {
int l=0,r=[Link]()-1;
while(l<r) if([Link](l++)!=[Link](r--)) return false;
return true;
}
}

Letter Combinations of a Phone Number

Difficulty: Medium
 class Solution {
String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
if ([Link]()) return new ArrayList<>();
List<String> res = new ArrayList<>();
backtrack(res, new StringBuilder(), digits, 0);
return res;
}
void backtrack(List<String> res, StringBuilder sb, String digits, int idx) {
if (idx == [Link]()) { [Link]([Link]()); return; }
for (char c : map[[Link](idx)-'0'].toCharArray()) {
[Link](c);
backtrack(res, sb, digits, idx+1);
[Link]([Link]()-1);
}
}
}

N-Queens
Difficulty: Hard
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) [Link](row, '.');
Set<Integer> cols=new HashSet<>(), diag1=new HashSet<>(), diag2=new HashSet<>();
solve(board, 0, cols, diag1, diag2, res);
return res;
}
void solve(char[][] board, int row, Set<Integer> cols, Set<Integer> d1, Set<Integer> d2, List<List<String>> res) {
if (row==[Link]) {
List<String> r=new ArrayList<>();
for (char[] row2:board) [Link](new String(row2));
[Link](r); return;
}
for (int col=0;col<[Link];col++) {
if ([Link](col)||[Link](row-col)||[Link](row+col)) continue;
board[row][col]='Q'; [Link](col); [Link](row-col); [Link](row+col);
solve(board,row+1,cols,d1,d2,res);
board[row][col]='.'; [Link](col); [Link](row-col); [Link](row+col);
}
}
}

Tries
Implement Trie (Prefix Tree)
Difficulty: Medium
class Trie {
private Trie[] children = new Trie[26];
private boolean isEnd = false;
public void insert(String word) {
 Trie cur = this;
for (char c : [Link]()) {
int i = c - 'a';
if ([Link][i] == null) [Link][i] = new Trie();
cur = [Link][i];
}
[Link] = true;
}
public boolean search(String word) {
Trie node = find(word);
return node != null && [Link];
}
public boolean startsWith(String prefix) { return find(prefix) != null; }
private Trie find(String s) {
Trie cur = this;
for (char c : [Link]()) {
if ([Link][c-'a'] == null) return null;
cur = [Link][c-'a'];
}
return cur;
}
}

Design Add and Search Words Data Structure

Difficulty: Medium
class WordDictionary {
private WordDictionary[] children = new WordDictionary[26];
private boolean isEnd = false;
public void addWord(String word) {
WordDictionary cur = this;
for (char c : [Link]()) {
if ([Link][c-'a']==null) [Link][c-'a']=new WordDictionary();
cur = [Link][c-'a'];
}
[Link] = true;
}
public boolean search(String word) { return searchFrom(word, 0, this); }
boolean searchFrom(String word, int idx, WordDictionary node) {
if (idx == [Link]()) return [Link];
char c = [Link](idx);
if (c == '.') {
for (WordDictionary child : [Link])
if (child != null && searchFrom(word, idx+1, child)) return true;
return false;
}
return [Link][c-'a'] != null && searchFrom(word, idx+1, [Link][c-'a']);
}
}

Word Search II
Difficulty: Hard
class Solution {
 public List<String> findWords(char[][] board, String[] words) {
Trie root = new Trie();
for (String w : words) [Link](w);
List<String> res = new ArrayList<>();
int m=[Link], n=board[0].length;
for (int i=0;i<m;i++) for (int j=0;j<n;j++)
dfs(board, root, i, j, res);
return res;
}
void dfs(char[][] b, Trie node, int r, int c, List<String> res) {
if (r<0||r>=[Link]||c<0||c>=b[0].length||b[r][c]=='#') return;
char ch=b[r][c]; Trie next=[Link][ch-'a'];
if (next==null) return;
if ([Link]!=null) { [Link]([Link]); [Link]=null; }
b[r][c]='#';
dfs(b,next,r+1,c,res); dfs(b,next,r-1,c,res);
dfs(b,next,r,c+1,res); dfs(b,next,r,c-1,res);
b[r][c]=ch;
}
}
class Trie {
Trie[] children=new Trie[26]; String word;
void insert(String w) {
Trie cur=this;
for (char c:[Link]()) { if([Link][c-'a']==null)[Link][c-'a']=new Trie(); cur=[Link][c-'a
[Link]=w;
}
}

Graphs
Number of Islands
Difficulty: Medium
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int r=0;r<[Link];r++) for (int c=0;c<grid[0].length;c++)
if (grid[r][c]=='1') { dfs(grid,r,c); count++; }
return count;
}
void dfs(char[][] grid, int r, int c) {
if (r<0||r>=[Link]||c<0||c>=grid[0].length||grid[r][c]!='1') return;
grid[r][c]='0';
dfs(grid,r+1,c); dfs(grid,r-1,c); dfs(grid,r,c+1); dfs(grid,r,c-1);
}
}

Max Area of Island

Difficulty: Medium
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int max = 0;
 for (int r=0;r<[Link];r++) for (int c=0;c<grid[0].length;c++)
max = [Link](max, dfs(grid,r,c));
return max;
}
int dfs(int[][] g, int r, int c) {
if (r<0||r>=[Link]||c<0||c>=g[0].length||g[r][c]==0) return 0;
g[r][c]=0;
return 1+dfs(g,r+1,c)+dfs(g,r-1,c)+dfs(g,r,c+1)+dfs(g,r,c-1);
}
}

Clone Graph
Difficulty: Medium
class Solution {
Map<Node,Node> map = new HashMap<>();
public Node cloneGraph(Node node) {
if (node==null) return null;
if ([Link](node)) return [Link](node);
Node clone = new Node([Link]);
[Link](node, clone);
for (Node n : [Link]) [Link](cloneGraph(n));
return clone;
}
}

Walls and Gates

Difficulty: Medium
class Solution {
public void wallsAndGates(int[][] rooms) {
Queue<int[]> q = new LinkedList<>();
for (int r=0;r<[Link];r++) for (int c=0;c<rooms[0].length;c++)
if (rooms[r][c]==0) [Link](new int[]{r,c});
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
while (![Link]()) {
int[] pos=[Link]();
for (int[] d:dirs) {
int nr=pos[0]+d[0], nc=pos[1]+d[1];
if (nr<0||nr>=[Link]||nc<0||nc>=rooms[0].length||rooms[nr][nc]!=Integer.MAX_VALUE) continue;
rooms[nr][nc]=rooms[pos[0]][pos[1]]+1;
[Link](new int[]{nr,nc});
}
}
}
}

Rotting Oranges
Difficulty: Medium
class Solution {
public int orangesRotting(int[][] grid) {
Queue<int[]> q = new LinkedList<>();
int fresh=0;
 for (int r=0;r<[Link];r++) for (int c=0;c<grid[0].length;c++) {
if (grid[r][c]==2) [Link](new int[]{r,c});
else if (grid[r][c]==1) fresh++;
}
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}}; int min=0;
while (![Link]() && fresh>0) {
min++;
for (int size=[Link]();size>0;size--) {
int[] pos=[Link]();
for (int[] d:dirs) {
int nr=pos[0]+d[0],nc=pos[1]+d[1];
if (nr<0||nr>=[Link]||nc<0||nc>=grid[0].length||grid[nr][nc]!=1) continue;
grid[nr][nc]=2; fresh--; [Link](new int[]{nr,nc});
}
}
}
return fresh==0?min:-1;
}
}

Pacific Atlantic Water Flow

Difficulty: Medium
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m=[Link], n=heights[0].length;
boolean[][] pac=new boolean[m][n], atl=new boolean[m][n];
for (int i=0;i<m;i++) { dfs(heights,pac,i,0); dfs(heights,atl,i,n-1); }
for (int j=0;j<n;j++) { dfs(heights,pac,0,j); dfs(heights,atl,m-1,j); }
List<List<Integer>> res=new ArrayList<>();
for (int r=0;r<m;r++) for (int c=0;c<n;c++)
if (pac[r][c]&&atl[r][c]) [Link]([Link](r,c));
return res;
}
void dfs(int[][] h, boolean[][] vis, int r, int c) {
vis[r][c]=true;
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
for (int[] d:dirs) {
int nr=r+d[0],nc=c+d[1];
if (nr<0||nr>=[Link]||nc<0||nc>=h[0].length||vis[nr][nc]||h[nr][nc]<h[r][c]) continue;
dfs(h,vis,nr,nc);
}
}
}

Surrounded Regions
Difficulty: Medium
class Solution {
public void solve(char[][] board) {
int m=[Link], n=board[0].length;
for (int r=0;r<m;r++) { dfs(board,r,0); dfs(board,r,n-1); }
for (int c=0;c<n;c++) { dfs(board,0,c); dfs(board,m-1,c); }
for (int r=0;r<m;r++) for (int c=0;c<n;c++) {
 if (board[r][c]=='O') board[r][c]='X';
else if (board[r][c]=='S') board[r][c]='O';
}
}
void dfs(char[][] b, int r, int c) {
if (r<0||r>=[Link]||c<0||c>=b[0].length||b[r][c]!='O') return;
b[r][c]='S';
dfs(b,r+1,c); dfs(b,r-1,c); dfs(b,r,c+1); dfs(b,r,c-1);
}
}

Course Schedule
Difficulty: Medium
class Solution {
public boolean canFinish(int n, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i=0;i<n;i++) [Link](new ArrayList<>());
for (int[] p:prerequisites) [Link](p[1]).add(p[0]);
int[] state = new int[n]; // 0=unvis, 1=visiting, 2=done
for (int i=0;i<n;i++) if (!dfs(adj,state,i)) return false;
return true;
}
boolean dfs(List<List<Integer>> adj, int[] state, int node) {
if (state[node]==1) return false;
if (state[node]==2) return true;
state[node]=1;
for (int nei:[Link](node)) if (!dfs(adj,state,nei)) return false;
state[node]=2;
return true;
}
}

Course Schedule II
Difficulty: Medium
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i=0;i<numCourses;i++) [Link](new ArrayList<>());
for (int[] p:prerequisites) [Link](p[1]).add(p[0]);
int[] state=new int[numCourses];
List<Integer> order = new ArrayList<>();
for (int i=0;i<numCourses;i++) if (!dfs(adj,state,i,order)) return new int[]{};
[Link](order);
return [Link]().mapToInt(Integer::intValue).toArray();
}
boolean dfs(List<List<Integer>> adj,int[] state,int node,List<Integer> order) {
if (state[node]==1) return false;
if (state[node]==2) return true;
state[node]=1;
for (int nei:[Link](node)) if (!dfs(adj,state,nei,order)) return false;
state[node]=2; [Link](node);
return true;
 }
}

Graph Valid Tree

Difficulty: Medium
class Solution {
public boolean validTree(int n, int[][] edges) {
if ([Link] != n-1) return false;
List<List<Integer>> adj = new ArrayList<>();
for (int i=0;i<n;i++) [Link](new ArrayList<>());
for (int[] e:edges) { [Link](e[0]).add(e[1]); [Link](e[1]).add(e[0]); }
Set<Integer> vis=new HashSet<>();
dfs(adj,vis,0);
return [Link]()==n;
}
void dfs(List<List<Integer>> adj,Set<Integer> vis,int node) {
if () return;
for (int nei:[Link](node)) dfs(adj,vis,nei);
}
}

Number of Connected Components in Undirected Graph

Difficulty: Medium
class Solution {
public int countComponents(int n, int[][] edges) {
int[] parent=new int[n];
for (int i=0;i<n;i++) parent[i]=i;
int components=n;
for (int[] e:edges) {
int p1=find(parent,e[0]), p2=find(parent,e[1]);
if (p1!=p2) { parent[p1]=p2; components--; }
}
return components;
}
int find(int[] p, int x) { return p[x]==x?x:(p[x]=find(p,p[x])); }
}

Redundant Connection
Difficulty: Medium
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n=[Link];
int[] parent=new int[n+1];
for (int i=0;i<=n;i++) parent[i]=i;
for (int[] e:edges) {
int p1=find(parent,e[0]), p2=find(parent,e[1]);
if (p1==p2) return e;
parent[p1]=p2;
}
return new int[]{};
}
 int find(int[] p, int x) { return p[x]==x?x:(p[x]=find(p,p[x])); }
}

Word Ladder
Difficulty: Hard
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if () return 0;
Queue<String> q = new LinkedList<>();
[Link](beginWord); int steps=1;
Set<String> visited = new HashSet<>(); [Link](beginWord);
while (![Link]()) {
for (int size=[Link]();size>0;size--) {
String word=[Link]();
if ([Link](endWord)) return steps;
char[] arr=[Link]();
for (int i=0;i<[Link];i++) {
char orig=arr[i];
for (char c='a';c<='z';c++) {
arr[i]=c; String next=new String(arr);
if ([Link](next)&&) { [Link](next); [Link](next); }
}
arr[i]=orig;
}
}
steps++;
}
return 0;
}
}

Advanced Graphs
Reconstruct Itinerary
Difficulty: Hard
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> adj = new HashMap<>();
for (List<String> t:tickets) [Link]([Link](0),k->new PriorityQueue<>()).offer([Link](1));
LinkedList<String> res=new LinkedList<>();
dfs("JFK", adj, res);
return res;
}
void dfs(String airport, Map<String,PriorityQueue<String>> adj, LinkedList<String> res) {
PriorityQueue<String> next=[Link](airport);
while (next!=null && ![Link]()) dfs([Link](),adj,res);
[Link](airport);
}
}
Min Cost to Connect All Points
Difficulty: Medium
class Solution {
public int minCostConnectPoints(int[][] points) {
int n=[Link], total=0, edges=0;
boolean[] inMST=new boolean[n];
int[] minCost=new int[n]; [Link](minCost,Integer.MAX_VALUE); minCost[0]=0;
while (edges<n) {
int u=-1;
for (int i=0;i<n;i++) if (!inMST[i]&&(u==-1||minCost[i]<minCost[u])) u=i;
inMST[u]=true; total+=minCost[u]; edges++;
for (int v=0;v<n;v++) if (!inMST[v]) {
int cost=[Link](points[u][0]-points[v][0])+[Link](points[u][1]-points[v][1]);
minCost[v]=[Link](minCost[v],cost);
}
}
return total;
}
}

Network Delay Time

Difficulty: Medium
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer,List<int[]>> adj=new HashMap<>();
for (int[] t:times) [Link](t[0],x->new ArrayList<>()).add(new int[]{t[1],t[2]});
PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[1]-b[1]);
[Link](new int[]{k,0});
Set<Integer> visited=new HashSet<>(); int maxTime=0;
while (![Link]()) {
int[] cur=[Link]();
if () continue;
maxTime=[Link](maxTime,cur[1]);
if ([Link](cur[0])) for (int[] nei:[Link](cur[0]))
if () [Link](new int[]{nei[0],cur[1]+nei[1]});
}
return [Link]()==n?maxTime:-1;
}
}

Swim in Rising Water

Difficulty: Hard
class Solution {
public int swimInWater(int[][] grid) {
int n=[Link];
PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);
[Link](new int[]{grid[0][0],0,0});
boolean[][] vis=new boolean[n][n]; vis[0][0]=true;
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
while (![Link]()) {
int[] cur=[Link]();
if (cur[1]==n-1&&cur[2]==n-1) return cur[0];
 for (int[] d:dirs) {
int nr=cur[1]+d[0],nc=cur[2]+d[1];
if (nr<0||nr>=n||nc<0||nc>=n||vis[nr][nc]) continue;
vis[nr][nc]=true;
[Link](new int[]{[Link](cur[0],grid[nr][nc]),nr,nc});
}
}
return -1;
}
}

Alien Dictionary
Difficulty: Hard
class Solution {
public String alienOrder(String[] words) {
Map<Character,Set<Character>> adj=new HashMap<>();
Map<Character,Integer> indegree=new HashMap<>();
for (String w:words) for (char c:[Link]()) { [Link](c,new HashSet<>()); [Link](c,0); }
for (int i=0;i<[Link]-1;i++) {
String w1=words[i],w2=words[i+1];
int len=[Link]([Link](),[Link]()); boolean found=false;
for (int j=0;j<len;j++) {
if ([Link](j)!=[Link](j)) {
if ().contains([Link](j))) {
[Link]([Link](j)).add([Link](j));
[Link]([Link](j),1,Integer::sum);
}
found=true; break;
}
}
if (!found&&[Link]()>[Link]()) return "";
}
Queue<Character> q=new LinkedList<>();
for (char c:[Link]()) if ([Link](c)==0) [Link](c);
StringBuilder sb=new StringBuilder();
while (![Link]()) {
char c=[Link](); [Link](c);
for (char nei:[Link](c)) { [Link](nei,-1,Integer::sum); if ([Link](nei)==0) [Link](nei); }
}
return [Link]()==[Link]()?[Link]():"";
}
}

Cheapest Flights Within K Stops

Difficulty: Medium
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[] prices=new int[n]; [Link](prices,Integer.MAX_VALUE); prices[src]=0;
for (int i=0;i<=k;i++) {
int[] tmp=[Link](prices,n);
for (int[] f:flights) {
if (prices[f[0]]!=Integer.MAX_VALUE&&prices[f[0]]+f[2]<tmp[f[1]])
 tmp[f[1]]=prices[f[0]]+f[2];
}
prices=tmp;
}
return prices[dst]==Integer.MAX_VALUE?-1:prices[dst];
}
}

1-D Dynamic Programming

Climbing Stairs
Difficulty: Easy
class Solution {
public int climbStairs(int n) {
if (n<=2) return n;
int a=1, b=2;
for (int i=3;i<=n;i++) { int c=a+b; a=b; b=c; }
return b;
}
}

Min Cost Climbing Stairs

Difficulty: Easy
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n=[Link], a=cost[0], b=cost[1];
for (int i=2;i<n;i++) { int c=cost[i]+[Link](a,b); a=b; b=c; }
return [Link](a,b);
}
}

House Robber
Difficulty: Medium
class Solution {
public int rob(int[] nums) {
int prev=0, cur=0;
for (int n:nums) { int tmp=[Link](cur, prev+n); prev=cur; cur=tmp; }
return cur;
}
}

House Robber II
Difficulty: Medium
class Solution {
public int rob(int[] nums) {
if ([Link]==1) return nums[0];
return [Link](robRange(nums,0,[Link]-2), robRange(nums,1,[Link]-1));
}
 int robRange(int[] nums, int l, int r) {
int prev=0, cur=0;
for (int i=l;i<=r;i++) { int tmp=[Link](cur,prev+nums[i]); prev=cur; cur=tmp; }
return cur;
}
}

Longest Palindromic Substring

Difficulty: Medium
class Solution {
public String longestPalindrome(String s) {
String res="";
for (int i=0;i<[Link]();i++) {
String odd=expand(s,i,i), even=expand(s,i,i+1);
if ([Link]()>[Link]()) res=odd;
if ([Link]()>[Link]()) res=even;
}
return res;
}
String expand(String s, int l, int r) {
while (l>=0&&r<[Link]()&&[Link](l)==[Link](r)) { l--; r++; }
return [Link](l+1,r);
}
}

Palindromic Substrings
Difficulty: Medium
class Solution {
public int countSubstrings(String s) {
int count=0;
for (int i=0;i<[Link]();i++) {
count+=expand(s,i,i);
count+=expand(s,i,i+1);
}
return count;
}
int expand(String s, int l, int r) {
int count=0;
while (l>=0&&r<[Link]()&&[Link](l)==[Link](r)) { count++; l--; r++; }
return count;
}
}

Decode Ways
Difficulty: Medium
class Solution {
public int numDecodings(String s) {
int n=[Link](), prev2=1, prev1=[Link](0)!='0'?1:0;
for (int i=1;i<n;i++) {
int cur=0;
if ([Link](i)!='0') cur=prev1;
 int two=[Link]([Link](i-1,i+1));
if (two>=10&&two<=26) cur+=prev2;
prev2=prev1; prev1=cur;
}
return prev1;
}
}

Coin Change
Difficulty: Medium
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp=new int[amount+1]; [Link](dp,amount+1); dp[0]=0;
for (int i=1;i<=amount;i++) for (int c:coins) if (c<=i) dp[i]=[Link](dp[i],dp[i-c]+1);
return dp[amount]>amount?-1:dp[amount];
}
}

Maximum Product Subarray

Difficulty: Medium
class Solution {
public int maxProduct(int[] nums) {
int max=nums[0], min=nums[0], res=nums[0];
for (int i=1;i<[Link];i++) {
int[] cands={nums[i], max*nums[i], min*nums[i]};
max=[Link](cands).max().getAsInt();
min=[Link](cands).min().getAsInt();
res=[Link](res,max);
}
return res;
}
}

Word Break
Difficulty: Medium
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict=new HashSet<>(wordDict);
boolean[] dp=new boolean[[Link]()+1]; dp[0]=true;
for (int i=1;i<=[Link]();i++)
for (int j=0;j<i;j++)
if (dp[j]&&[Link]([Link](j,i))) { dp[i]=true; break; }
return dp[[Link]()];
}
}

Longest Increasing Subsequence

Difficulty: Medium
class Solution {
 public int lengthOfLIS(int[] nums) {
List<Integer> sub=new ArrayList<>();
for (int n:nums) {
int pos=[Link](sub,n);
if (pos<0) pos=-(pos+1);
if (pos==[Link]()) [Link](n);
else [Link](pos,n);
}
return [Link]();
}
}

Partition Equal Subset Sum

Difficulty: Medium
class Solution {
public boolean canPartition(int[] nums) {
int sum=[Link](nums).sum();
if (sum%2!=0) return false;
int target=sum/2;
boolean[] dp=new boolean[target+1]; dp[0]=true;
for (int n:nums) for (int j=target;j>=n;j--) dp[j]|=dp[j-n];
return dp[target];
}
}

2-D Dynamic Programming

Unique Paths
Difficulty: Medium
class Solution {
public int uniquePaths(int m, int n) {
int[] dp=new int[n]; [Link](dp,1);
for (int i=1;i<m;i++) for (int j=1;j<n;j++) dp[j]+=dp[j-1];
return dp[n-1];
}
}

Longest Common Subsequence

Difficulty: Medium
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m=[Link](), n=[Link]();
int[][] dp=new int[m+1][n+1];
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) {
if ([Link](i-1)==[Link](j-1)) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=[Link](dp[i-1][j],dp[i][j-1]);
}
return dp[m][n];
}
}
Best Time to Buy and Sell Stock with Cooldown
Difficulty: Medium
class Solution {
public int maxProfit(int[] prices) {
int hold=Integer.MIN_VALUE, sold=0, rest=0;
for (int p:prices) {
int prevSold=sold;
sold=hold+p;
hold=[Link](hold,rest-p);
rest=[Link](rest,prevSold);
}
return [Link](sold,rest);
}
}

Coin Change II
Difficulty: Medium
class Solution {
public int change(int amount, int[] coins) {
int[] dp=new int[amount+1]; dp[0]=1;
for (int c:coins) for (int j=c;j<=amount;j++) dp[j]+=dp[j-c];
return dp[amount];
}
}

Target Sum
Difficulty: Medium
class Solution {
public int findTargetSumWays(int[] nums, int target) {
Map<Integer,Integer> dp=new HashMap<>(); [Link](0,1);
for (int n:nums) {
Map<Integer,Integer> next=new HashMap<>();
for (int sum:[Link]()) {
[Link](sum+n,[Link](sum),Integer::sum);
[Link](sum-n,[Link](sum),Integer::sum);
}
dp=next;
}
return [Link](target,0);
}
}

Interleaving String
Difficulty: Medium
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m=[Link](), n=[Link]();
if (m+n!=[Link]()) return false;
 boolean[][] dp=new boolean[m+1][n+1]; dp[0][0]=true;
for (int i=1;i<=m;i++) dp[i][0]=dp[i-1][0]&&[Link](i-1)==[Link](i-1);
for (int j=1;j<=n;j++) dp[0][j]=dp[0][j-1]&&[Link](j-1)==[Link](j-1);
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++)
dp[i][j]=(dp[i-1][j]&&[Link](i-1)==[Link](i+j-1))||
(dp[i][j-1]&&[Link](j-1)==[Link](i+j-1));
return dp[m][n];
}
}

Longest Increasing Path in a Matrix

Difficulty: Hard
class Solution {
int[][] dp;
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
public int longestIncreasingPath(int[][] matrix) {
int m=[Link], n=matrix[0].length, res=0;
dp=new int[m][n];
for (int r=0;r<m;r++) for (int c=0;c<n;c++) res=[Link](res,dfs(matrix,r,c));
return res;
}
int dfs(int[][] m, int r, int c) {
if (dp[r][c]!=0) return dp[r][c];
dp[r][c]=1;
for (int[] d:dirs) {
int nr=r+d[0], nc=c+d[1];
if (nr>=0&&nr<[Link]&&nc>=0&&nc<m[0].length&&m[nr][nc]>m[r][c])
dp[r][c]=[Link](dp[r][c],1+dfs(m,nr,nc));
}
return dp[r][c];
}
}

Distinct Subsequences
Difficulty: Hard
class Solution {
public int numDistinct(String s, String t) {
int m=[Link](), n=[Link]();
int[][] dp=new int[m+1][n+1];
for (int i=0;i<=m;i++) dp[i][0]=1;
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) {
dp[i][j]=dp[i-1][j];
if ([Link](i-1)==[Link](j-1)) dp[i][j]+=dp[i-1][j-1];
}
return dp[m][n];
}
}

Edit Distance
Difficulty: Medium
class Solution {
 public int minDistance(String word1, String word2) {
int m=[Link](), n=[Link]();
int[][] dp=new int[m+1][n+1];
for (int i=0;i<=m;i++) dp[i][0]=i;
for (int j=0;j<=n;j++) dp[0][j]=j;
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) {
if ([Link](i-1)==[Link](j-1)) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=1+[Link](dp[i-1][j-1],[Link](dp[i-1][j],dp[i][j-1]));
}
return dp[m][n];
}
}

Burst Balloons
Difficulty: Hard
class Solution {
public int maxCoins(int[] nums) {
int n=[Link];
int[] arr=new int[n+2]; arr[0]=arr[n+1]=1;
for (int i=0;i<n;i++) arr[i+1]=nums[i];
int N=n+2;
int[][] dp=new int[N][N];
for (int len=2;len<N;len++) for (int l=0;l<N-len;l++) {
int r=l+len;
for (int k=l+1;k<r;k++)
dp[l][r]=[Link](dp[l][r],dp[l][k]+dp[k][r]+arr[l]*arr[k]*arr[r]);
}
return dp[0][N-1];
}
}

Regular Expression Matching

Difficulty: Hard
class Solution {
public boolean isMatch(String s, String p) {
int m=[Link](), n=[Link]();
boolean[][] dp=new boolean[m+1][n+1]; dp[0][0]=true;
for (int j=1;j<=n;j++) if ([Link](j-1)=='*') dp[0][j]=dp[0][j-2];
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) {
if ([Link](j-1)=='*')
dp[i][j]=dp[i][j-2]||(dp[i-1][j]&&([Link](j-2)=='.'||[Link](j-2)==[Link](i-1)));
else
dp[i][j]=dp[i-1][j-1]&&([Link](j-1)=='.'||[Link](j-1)==[Link](i-1));
}
return dp[m][n];
}
}

Greedy
Maximum Subarray
Difficulty: Medium
class Solution {
public int maxSubArray(int[] nums) {
int maxSum=nums[0], curSum=nums[0];
for (int i=1;i<[Link];i++) {
curSum=[Link](nums[i], curSum+nums[i]);
maxSum=[Link](maxSum,curSum);
}
return maxSum;
}
}

Jump Game
Difficulty: Medium
class Solution {
public boolean canJump(int[] nums) {
int maxReach=0;
for (int i=0;i<[Link];i++) {
if (i>maxReach) return false;
maxReach=[Link](maxReach,i+nums[i]);
}
return true;
}
}

Jump Game II
Difficulty: Medium
class Solution {
public int jump(int[] nums) {
int jumps=0, curEnd=0, farthest=0;
for (int i=0;i<[Link]-1;i++) {
farthest=[Link](farthest,i+nums[i]);
if (i==curEnd) { jumps++; curEnd=farthest; }
}
return jumps;
}
}

Gas Station
Difficulty: Medium
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total=0, tank=0, start=0;
for (int i=0;i<[Link];i++) {
total+=gas[i]-cost[i]; tank+=gas[i]-cost[i];
if (tank<0) { start=i+1; tank=0; }
}
return total>=0?start:-1;
}
}
Hand of Straights
Difficulty: Medium
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
if ([Link]%groupSize!=0) return false;
TreeMap<Integer,Integer> map=new TreeMap<>();
for (int h:hand) [Link](h,1,Integer::sum);
while (![Link]()) {
int first=[Link]();
for (int i=0;i<groupSize;i++) {
if () return false;
int cnt=[Link](first+i);
if (cnt==1) [Link](first+i);
else [Link](first+i,cnt-1);
}
}
return true;
}
}

Merge Triplets to Form Target Triplet

Difficulty: Medium
class Solution {
public boolean mergeTriplets(int[][] triplets, int[] target) {
int[] res=new int[3];
for (int[] t:triplets) {
if (t[0]>target[0]||t[1]>target[1]||t[2]>target[2]) continue;
for (int i=0;i<3;i++) res[i]=[Link](res[i],t[i]);
}
return [Link](res,target);
}
}

Partition Labels
Difficulty: Medium
class Solution {
public List<Integer> partitionLabels(String s) {
int[] last=new int[26];
for (int i=0;i<[Link]();i++) last[[Link](i)-'a']=i;
List<Integer> res=new ArrayList<>();
int start=0, end=0;
for (int i=0;i<[Link]();i++) {
end=[Link](end,last[[Link](i)-'a']);
if (i==end) { [Link](end-start+1); start=i+1; }
}
return res;
}
}
Valid Parenthesis String
Difficulty: Medium
class Solution {
public boolean checkValidString(String s) {
int low=0, high=0;
for (char c:[Link]()) {
if (c=='(') { low++; high++; }
else if (c==')') { low--; high--; }
else { low--; high++; }
if (high<0) return false;
low=[Link](low,0);
}
return low==0;
}
}

Intervals
Insert Interval
Difficulty: Medium
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res=new ArrayList<>();
int i=0, n=[Link];
while (i<n&&intervals[i][1]<newInterval[0]) [Link](intervals[i++]);
while (i<n&&intervals[i][0]<=newInterval[1]) {
newInterval[0]=[Link](newInterval[0],intervals[i][0]);
newInterval[1]=[Link](newInterval[1],intervals[i++][1]);
}
[Link](newInterval);
while (i<n) [Link](intervals[i++]);
return [Link](new int[0][]);
}
}

Merge Intervals
Difficulty: Medium
class Solution {
public int[][] merge(int[][] intervals) {
[Link](intervals,(a,b)->a[0]-b[0]);
List<int[]> res=new ArrayList<>();
for (int[] cur:intervals) {
if ([Link]()||[Link]([Link]()-1)[1]<cur[0]) [Link](cur);
else [Link]([Link]()-1)[1]=[Link]([Link]([Link]()-1)[1],cur[1]);
}
return [Link](new int[0][]);
}
}

Non-overlapping Intervals
Difficulty: Medium
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
[Link](intervals,(a,b)->a[1]-b[1]);
int count=0, prevEnd=Integer.MIN_VALUE;
for (int[] in:intervals) {
if (in[0]>=prevEnd) prevEnd=in[1];
else count++;
}
return count;
}
}

Meeting Rooms
Difficulty: Easy
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
[Link](intervals,(a,b)->a[0]-b[0]);
for (int i=1;i<[Link];i++)
if (intervals[i][0]<intervals[i-1][1]) return false;
return true;
}
}

Meeting Rooms II
Difficulty: Medium
class Solution {
public int minMeetingRooms(int[][] intervals) {
[Link](intervals,(a,b)->a[0]-b[0]);
PriorityQueue<Integer> pq=new PriorityQueue<>();
for (int[] iv:intervals) {
if (![Link]()&&[Link]()<=iv[0]) [Link]();
[Link](iv[1]);
}
return [Link]();
}
}

Minimum Interval to Include Each Query

Difficulty: Hard
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
[Link](intervals,(a,b)->a[0]-b[0]);
int[][] qs=new int[[Link]][2];
for (int i=0;i<[Link];i++) qs[i]=new int[]{queries[i],i};
[Link](qs,(a,b)->a[0]-b[0]);
PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);
int[] res=new int[[Link]]; [Link](res,-1);
int i=0;
for (int[] q:qs) {
 while (i<[Link]&&intervals[i][0]<=q[0])
[Link](new int[]{intervals[i][1]-intervals[i][0]+1,intervals[i++][1]});
while (![Link]()&&[Link]()[1]<q[0]) [Link]();
if (![Link]()) res[q[1]]=[Link]()[0];
}
return res;
}
}

Math & Geometry

Rotate Image
Difficulty: Medium
class Solution {
public void rotate(int[][] matrix) {
int n=[Link];
// Transpose
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) {
int tmp=matrix[i][j]; matrix[i][j]=matrix[j][i]; matrix[j][i]=tmp;
}
// Reverse rows
for (int[] row:matrix) {
int l=0,r=n-1;
while (l<r) { int tmp=row[l]; row[l++]=row[r]; row[r--]=tmp; }
}
}
}

Spiral Matrix
Difficulty: Medium
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res=new ArrayList<>();
int top=0,bot=[Link]-1,left=0,right=matrix[0].length-1;
while (top<=bot&&left<=right) {
for (int c=left;c<=right;c++) [Link](matrix[top][c]); top++;
for (int r=top;r<=bot;r++) [Link](matrix[r][right]); right--;
if (top<=bot) { for (int c=right;c>=left;c--) [Link](matrix[bot][c]); bot--; }
if (left<=right) { for (int r=bot;r>=top;r--) [Link](matrix[r][left]); left++; }
}
return res;
}
}

Set Matrix Zeroes

Difficulty: Medium
class Solution {
public void setZeroes(int[][] matrix) {
int m=[Link], n=matrix[0].length;
boolean firstRow=false, firstCol=false;
 for (int j=0;j<n;j++) if (matrix[0][j]==0) firstRow=true;
for (int i=0;i<m;i++) if (matrix[i][0]==0) firstCol=true;
for (int i=1;i<m;i++) for (int j=1;j<n;j++) if (matrix[i][j]==0) { matrix[i][0]=matrix[0][j]=0; }
for (int i=1;i<m;i++) for (int j=1;j<n;j++) if (matrix[i][0]==0||matrix[0][j]==0) matrix[i][j]=0;
if (firstRow) [Link](matrix[0],0);
if (firstCol) for (int i=0;i<m;i++) matrix[i][0]=0;
}
}

Happy Number
Difficulty: Easy
class Solution {
public boolean isHappy(int n) {
Set<Integer> seen=new HashSet<>();
while (n!=1) {
if () return false;
int next=0;
while (n>0) { int d=n%10; next+=d*d; n/=10; }
n=next;
}
return true;
}
}

Plus One
Difficulty: Easy
class Solution {
public int[] plusOne(int[] digits) {
for (int i=[Link]-1;i>=0;i--) {
if (digits[i]<9) { digits[i]++; return digits; }
digits[i]=0;
}
int[] res=new int[[Link]+1]; res[0]=1;
return res;
}
}

Pow(x, n)
Difficulty: Medium
class Solution {
public double myPow(double x, int n) {
long N=n;
if (N<0) { x=1/x; N=-N; }
double res=1;
while (N>0) {
if ((N&1)==1) res*=x;
x*=x; N>>=1;
}
return res;
}
}
Multiply Strings
Difficulty: Medium
class Solution {
public String multiply(String num1, String num2) {
int m=[Link](), n=[Link]();
int[] pos=new int[m+n];
for (int i=m-1;i>=0;i--) for (int j=n-1;j>=0;j--) {
int mul=([Link](i)-'0')*([Link](j)-'0');
int p1=i+j, p2=i+j+1, sum=mul+pos[p2];
pos[p2]=sum%10; pos[p1]+=sum/10;
}
StringBuilder sb=new StringBuilder();
for (int p:pos) if (!([Link]()==0&&p==0)) [Link](p);
return [Link]()==0?"0":[Link]();
}
}

Detect Squares
Difficulty: Medium
class DetectSquares {
Map<String,Integer> pointCnt=new HashMap<>();
Map<Integer,Set<Integer>> xMap=new HashMap<>();
public void add(int[] point) {
String key=point[0]+","+point[1];
[Link](key,1,Integer::sum);
[Link](point[0],k->new HashSet<>()).add(point[1]);
}
public int count(int[] point) {
int ans=0, px=point[0], py=point[1];
if () return 0;
for (int y:[Link](px)) {
if (y==py) continue;
int d=y-py;
ans+=get(px+d,py)*get(px+d,y)*get(px,y);
ans+=get(px-d,py)*get(px-d,y)*get(px,y);
}
return ans;
}
int get(int x,int y) { return [Link](x+","+y,0); }
}

Bit Manipulation
Single Number
Difficulty: Easy
class Solution {
public int singleNumber(int[] nums) {
int res=0;
for (int n:nums) res^=n;
return res;
 }
}

Number of 1 Bits
Difficulty: Easy
class Solution {
public int hammingWeight(int n) {
int count=0;
while (n!=0) { n&=(n-1); count++; }
return count;
}
}

Counting Bits
Difficulty: Easy
class Solution {
public int[] countBits(int n) {
int[] dp=new int[n+1];
for (int i=1;i<=n;i++) dp[i]=dp[i>>1]+(i&1);
return dp;
}
}

Reverse Bits
Difficulty: Easy
class Solution {
public int reverseBits(int n) {
int res=0;
for (int i=0;i<32;i++) { res=(res<<1)|(n&1); n>>=1; }
return res;
}
}

Missing Number
Difficulty: Easy
class Solution {
public int missingNumber(int[] nums) {
int n=[Link], expected=n*(n+1)/2, actual=0;
for (int num:nums) actual+=num;
return expected-actual;
}
}

Sum of Two Integers

Difficulty: Medium
class Solution {
public int getSum(int a, int b) {
 while (b!=0) { int carry=a&b; a^=b; b=carry<<1; }
return a;
}
}

Reverse Integer
Difficulty: Medium
class Solution {
public int reverse(int x) {
long res=0;
while (x!=0) { res=res*10+x%10; x/=10; }
return (res>Integer.MAX_VALUE||res<Integer.MIN_VALUE)?0:(int)res;
}
}