# 2115. Find All Possible Recipes from Given Supplies

Standard

## Problem

Given an array of integers `nums` and an integer `k`, return the total number of subarrays whose sum equals to `k`.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

```Input: nums = [1,1,1], k = 2
Output: 2
```

Example 2:

```Input: nums = [1,2,3], k = 3
Output: 2
```

Constraints:

• `1 <= nums.length <= 2 * 104`
• `-1000 <= nums[i] <= 1000`
• `-107 <= k <= 107`

## Solution

``````class Solution {
private HashMap<String, Integer> recipes;
private HashMap<String, Boolean> visitedAndFound; // false to detect cycle
private List<List<String>> ingredients;
private HashSet<String> supplies;

public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
this.recipes = new HashMap<>();
for (int i = 0; i < recipes.length; i++) {
this.recipes.put(recipes[i], i);
}
this.ingredients = ingredients;
this.visitedAndFound = new HashMap<>();
this.supplies = new HashSet<>();
for (String supply : supplies) {
}

for (String recipe : recipes) {
if (findRecipe(recipe)) {
}
}
return res;
}

public boolean findRecipe(String recipe) {
if (visitedAndFound.containsKey(recipe)) {
return visitedAndFound.get(recipe);
}
visitedAndFound.put(recipe, false);

if (supplies.contains(recipe)) {
visitedAndFound.put(recipe, true);
return true;
}
if (!recipes.containsKey(recipe)) {
return false;
}

for (String ingredient : ingredients.get(recipes.get(recipe))) {
if (findRecipe(ingredient) == false) {
return false;
}
}
visitedAndFound.put(recipe, true);
return true;
}
}``````

# 253. Meeting Rooms II

Standard

## Problem

Given an array of meeting time intervals `intervals` where `intervals[i] = [starti, endi]`, return the minimum number of conference rooms required.

Example 1:

```Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
```

Example 2:

```Input: intervals = [[7,10],[2,4]]
Output: 1
```

Constraints:

• `1 <= intervals.length <= 104`
• `0 <= starti < endi <= 106`

## Java Solution

``````class Solution {
public int minMeetingRooms(int[][] intervals) {
int[] starts = new int[intervals.length];
int[] ends = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int room = 0, endIdx = 0;
for (int i = 0; i < starts.length; i++) {
if (starts[i] < ends[endIdx]) {
room++;
} else {
endIdx++;
}
}
return room;
}
}``````

# 539. Minimum Time Difference

Standard

## Problem

Given a list of 24-hour clock time points in “HH:MM” format, return the minimum minutes difference between any two time-points in the list.

Example 1:

```Input: timePoints = ["23:59","00:00"]
Output: 1
```

Example 2:

```Input: timePoints = ["00:00","23:59","00:00"]
Output: 0
```

Constraints:

• `2 <= timePoints.length <= 2 * 104`
• `timePoints[i]` is in the format “HH:MM”.

## Java Solution

``````class Solution {
public int findMinDifference(List<String> timePoints) {
int[] exist = new int[24 * 60];
for (String time : timePoints) {
int minutes = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3, 5));
if (exist[minutes] != 0) {
return 0;
} else {
exist[minutes] = 1;
}
}

int prev = -1;
int res = Integer.MAX_VALUE, start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
for (int i = 0; i < 24 * 60; i++) {
if (exist[i] == 1) {
if (prev == -1) {
prev = i;
} else {
res = Math.min(res, i - prev);
}
prev = i;
start = Math.min(start, i);
end = Math.max(end, i);
}
}
return Math.min(res, 24 * 60 - (end - start));
}
}``````

# 1048. Longest String Chain

Standard

## Problem

You are given an array of `words` where each word consists of lowercase English letters.

`wordA` is a predecessor of `wordB` if and only if we can insert exactly one letter anywhere in `wordA` without changing the order of the other characters to make it equal to `wordB`.

• For example, `"abc"` is a predecessor of `"abac"`, while `"cba"` is not a predecessor of `"bcad"`.

word chain is a sequence of words `[word1, word2, ..., wordk]` with `k >= 1`, where `word1` is a predecessor of `word2``word2` is a predecessor of `word3`, and so on. A single word is trivially a word chain with `k == 1`.

Return the length of the longest possible word chain with words chosen from the given list of `words`.

Example 1:

```Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].
```

Example 2:

```Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
```

Example 3:

```Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
```

Constraints:

• `1 <= words.length <= 1000`
• `1 <= words[i].length <= 16`
• `words[i]` only consists of lowercase English letters.

## Java Solution

``````class Solution {
public int longestStrChain(String[] words) {
HashMap<String, Integer> longestPre = new HashMap<>(); // Including the word itself
TreeMap<Integer, List<String>> wordsByCharLength = new TreeMap<>();
int res = 1;
for (String word : words) {
}
int longest = wordsByCharLength.lastKey();
for (int i = 1; i <= longest; i++) {
if (!wordsByCharLength.containsKey(i)) {
continue;
}
for (String curWord : wordsByCharLength.get(i)) {
if (!wordsByCharLength.containsKey(i - 1)) {
longestPre.put(curWord, 1);
continue;
}
int prevLongest = 0;
for (String prevWord : wordsByCharLength.get(i - 1)) {
if (isPredecessorOf(prevWord, curWord)) {
prevLongest = Math.max(prevLongest, longestPre.get(prevWord));
}
}
longestPre.put(curWord, prevLongest + 1);
res = Math.max(res, prevLongest + 1);
}
}
return res;
}

private boolean isPredecessorOf(String prevWord, String curWord) {
int skipped = 0;
int i = 0;
while (i < prevWord.length() && i + skipped < curWord.length()) {
if (prevWord.charAt(i) != curWord.charAt(i + skipped)) {
if (skipped == 0) {
skipped = 1;
continue;
} else {
return false;
}
}
i++;
}
return true;
}
}``````

# 110. Balanced Binary Tree￼

Standard

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Java Solution:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Result {
boolean val;
Result() {
this.val = true;
}
public void setValue(boolean val) {
this.val = val;
}
public boolean getValue() {
return val;
}
}
class Solution {
public boolean isBalanced(TreeNode root) {
Result isBalanced = new Result();
getHeight(root, isBalanced);
return isBalanced.getValue();
}

private int getHeight(TreeNode node, Result isBalanced) {
if (node == null) return 0;
int leftHeight = getHeight(node.left, isBalanced);
int rightHeight = getHeight(node.right, isBalanced);
if (Math.abs(leftHeight - rightHeight) > 1) {
isBalanced.setValue(false);
}
return Math.max(leftHeight, rightHeight) + 1;
}
}``````

Essentially, trying to “hack” the pass-by-reference C++ has into the Java solution. But it solves the problem in one pass.