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) {
            this.supplies.add(supply);
        }

        List<String> res = new LinkedList<>();
        for (String recipe : recipes) {
            if (findRecipe(recipe)) {
                res.add(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;
    }
}

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;
    }
}

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));
    }
}

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".

A 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) {
            wordsByCharLength.putIfAbsent(word.length(), new LinkedList<>());
            wordsByCharLength.get(word.length()).add(word);
        }
        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;
    }
}

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.