91. Decode Ways

三刷 06/2022

Version #1 DP - 1D array

Can be optimized to constant space

Time O(N)

Space O(N)

Runtime: 1 ms, faster than 98.23% of Java online submissions for Decode Ways.

Memory Usage: 42.6 MB, less than 29.83% of Java online submissions for Decode Ways.

class Solution {

    public int numDecodings(String s) {

        int[] dp = new int[s.length() + 1];

        dp[0] = 1;

        if (s.length() == 0 || s.charAt(0) == '0') {

            return 0;

        }

        dp[1] = 1;

        for (int i = 2; i <= s.length(); i++) {

            int prev = s.charAt(i - 2) - '0';

            int curr = s.charAt(i - 1) - '0';

            if (curr != 0) {

                dp[i] += dp[i - 1]; // single digit decode is possible

            }

            if (prev == 0 && curr == 0) {

                return 0;

            }

            int twoDigit = prev * 10 + curr;

            if (twoDigit >= 10 && twoDigit <= 26) {

                dp[i] += dp[i - 2];

            }

        }

        return dp[s.length()];

    }

}

二刷

90.97 %
class Solution {
    public int numDecodings(String s) {
        // dp[i] -> number of ways to decode s.substring[0, i]
        if (s == null || s.length() == 0) return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            int curr = s.charAt(i - 1) - '0';
            if (i == 1) { // first position
                if (curr == 0) return 0;
                dp[i] = 1;
            } else {
                // decode by itself
                // decode with its previous digit
                int prev = s.charAt(i - 2) - '0';
                if (prev != 0 && prev * 10 + curr <= 26) {
                    dp[i] += dp[i - 2];
                }
                if (curr != 0) {
                    dp[i] += dp[i - 1];
                }
            }
        }
        return dp[s.length()];
    }
}

一刷
Space can be optimized

96.96 %
class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // dp[i] -> ways to decode substring [0, i)
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        int prev = 0;
        for (int i = 1; i <= s.length(); i++) {
            int curr = s.charAt(i - 1) - '0';
            int num = prev * 10 + curr;
            if (i > 1 && num >= 10 && num < 27) {
                dp[i] += dp[i - 2];
            }
            if (curr > 0) {
                dp[i] += dp[i - 1];
            }
            prev = curr;
        }
        return dp[s.length()];
    }
}

45. Jump Game II

二刷

Version #2 Greedy

Exit early when step end reaches the last index

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 99.93% of Java online submissions for Jump Game II.

Memory Usage: 43.1 MB, less than 84.43% of Java online submissions for Jump Game II.

class Solution {

    public int jump(int[] nums) {

        // furthest defines the furthest index that we can reach

        // Every time the furthest is updated, we need to make an extra jump

        int furthest = 0;

        int stepEnd = 0; // The furthest that we can reach within current number of steps

        int step = 0;

        for (int i = 0; i < nums.length; i++) {

            if (i > furthest) {

                return -1;

            }

            if (i > stepEnd) {

                step++;

                stepEnd = furthest;

            }

            furthest = Math.max(furthest, i + nums[i]);

            

            if (stepEnd >= nums.length - 1) {

                return step;

            }

        }

        return -1;

    }

}

一刷

Version #2 Greedy

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 99.90% of Java online submissions for Jump Game II.

Memory Usage: 49.9 MB, less than 23.57% of Java online submissions for Jump Game II.

class Solution {

    public int jump(int[] nums) {

        int steps = 0;

        int furthest = 0;

        int currEnd = 0;

        for (int i = 0; i < nums.length - 1; i++) {

            // With a steps, we can reach the range

            // [start, end]

            // Update the next furthest index until we reach end

            furthest = Math.max(furthest, nums[i] + i);

            if (i == currEnd) {

                steps++;

                currEnd = furthest;

            }

        }

        return steps;

    }

}

Version #1 BFS

23.54 %
class Solution {
    public int jump(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int step = 0;
Set<Integer> visited = new HashSet<>();
visited.add(0);
int len = nums.length;
Queue<Integer> que = new LinkedList<>();
        que.offer(0);
while (!que.isEmpty()) {
int size = que.size();
// [2,3,1,1,4] curr = 0 next = 1 i = 1, 2
step++;
while (size-- > 0) {
int curr = que.poll();
int next = curr + nums[curr];
for (int i = 0; i < nums[curr]; i++) {
if (next >= len - 1) {
return step;
}
if (!visited.contains(next)) {
visited.add(next);
que.offer(next);
}
next--;
}
}
}
return -1;
}

}

55. Jump Game

三刷 06/2022

Version #1 Greedy

跟二刷写的稍微有点不一样

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 91.43% of Java online submissions for Jump Game.

Memory Usage: 67.9 MB, less than 53.75% of Java online submissions for Jump Game.

class Solution {

    public boolean canJump(int[] nums) {

        // If at index we can jump n steps, then all indices between [index + 1, index + n] can be reached

        // We can iterate over the nums and keep track of the furthest index that we can reach

        // If current index > furthest index, then return false

        int furthest = 0;

        for (int i = 0; i < nums.length; i++) {

            if (furthest < i) {

                return false;

            }

            furthest = Math.max(furthest, i + nums[i]);

        }

        return true;

    }

}

二刷 06/2022

Version #1 Greedy

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 88.45% of Java online submissions for Jump Game.

Memory Usage: 68.8 MB, less than 14.63% of Java online submissions for Jump Game.

class Solution {

    public boolean canJump(int[] nums) {

        int p = 0;

        int i = 0;

        for (i = 0; i <= p && i < nums.length; i++) {

            p = Math.max(p, i + nums[i]);

        }

        return i == nums.length;

    }

}

一刷

Version #1 Greedy
Iterate through the array, doing 2 things
1. Check if current index can be reached
2.Update the furthest index we can reach so far
As long as the furthest index is larger than the last index, we know we can reach

Time O(n)
97.15 %
class Solution {
    public boolean canJump(int[] nums) {
if (nums == null || nums.length <= 1) {
return true;
}
int furthest = nums[0];
for (int i = 0; i < nums.length; i++) {
if (i > furthest) {
return false;
}
furthest = Math.max(furthest, i + nums[i]);
if (furthest >= nums.length - 1) {
return true;
}
}
return false;
}
}

752. Open the Lock

二刷 07/2022

Version #1 BFS level order traversal

犯了一个错误就是每次只有一个bit可以rotate，我想成每次4个bits都可以freely地变成上一个或者下一个，然后傻了吧唧的写了一个dfs来generate next code

另外一个错误就是deadend有可能包含init state，我只讨论了target等于init state的请况却漏了deadend包含init state的情况

还有一个就是char虽然可以直接做加减法，但是做完加减法之后会变成int，然后再赋值给char就会报loss of accuracy的错，必须explicitly cast成char才行

Time O(4^2 * 10^4) - 如果4是N的话getNextCode这个function是O(N^2)的复杂度，因为iterate了N个digit然后每个digit又O(N)的时间计算String.valueOf(chars)

• Time Complexity: $O(N^2 * \mathcal{A}^N + D)$ where $\mathcal{A}$ is the number of digits in our alphabet, $N$ is the number of digits in the lock, and $D$ is the size of deadends. We might visit every lock combination, plus we need to instantiate our set dead. When we visit every lock combination, we spend $O(N^2)$ time enumerating through and constructing each node.

• Space Complexity: $O(\mathcal{A}^N + D)$, for the queue and the set dead.

Runtime: 118 ms, faster than 83.49% of Java online submissions for Open the Lock.

Memory Usage: 71.1 MB, less than 72.54% of Java online submissions for Open the Lock.

class Solution {

    public int openLock(String[] deadends, String target) {

        String init = "0000";

        if (init.equals(target)) {

            return 0;

        }

        Set<String> deadendSet = new HashSet<>();

        for (String deadend : deadends) {

            deadendSet.add(deadend);

        }

        if (deadendSet.contains(init)) {

            return -1;

        }

        Set<String> visited = new HashSet<>();

        Queue<String> que = new ArrayDeque<>();

        visited.add(init);

        que.offer(init);

        int step = 0;

        while (!que.isEmpty()) {

            int size = que.size();

            step++;

            while (size-- > 0) {

                String curr = que.poll();

                for (String next : getNextCode(curr)) {

                    if (deadendSet.contains(next) || visited.contains(next)) {

                       continue;

                    }

                    if (next.equals(target)) {

                        return step;

                    }

                    visited.add(next);

                    que.offer(next);

                }

            }

        }

        return -1;

    }

    

    private List<String> getNextCode(String curr) {

        char[] chars = curr.toCharArray();

        List<String> codes = new ArrayList<>();

        // only 1 bit can be rotated

        for (int i = 0; i < chars.length; i++) {

            char c = chars[i];

            chars[i] = c == '0' ? '9' : (char)(c - 1);

            codes.add(String.valueOf(chars));

            chars[i] = c == '9' ? '0' : (char)(c + 1);

            codes.add(String.valueOf(chars));

            chars[i] = c;

        }

        return codes;

    }

}

一刷
Classical BFS


76.45 %
// increment i = (i + 1) % 10
// decrement i = (i + 9) % 10

class Solution {
    public int openLock(String[] deadends, String target) {
String init = "0000";
Set<String> visited = new HashSet<>(Arrays.asList(deadends));
        if (visited.contains(init)) {
            return -1;
        }
Queue<String> que = new LinkedList<>();
que.offer(init);
int step = 0;
while (!que.isEmpty()) {
int size = que.size();
while (size-- > 0) {
String curr = que.poll();
if (curr.equals(target)) {
return step;
}
char[] chars = curr.toCharArray();
for (int i = 0; i < 4; i++) {
// increment
char c = chars[i];
chars[i] = (char)('0' + ((c - '0' + 1) % 10));
String next = new String(chars);
if (!visited.contains(next)) {
visited.add(next);
que.offer(next);
}
                    // decrement
chars[i] = (char)('0' + ((c - '0' + 9) % 10));
next = new String(chars);
if (!visited.contains(next)) {
visited.add(next);
que.offer(next);
}
chars[i] = c;
}
}
step++;
}
return -1;
}
}

825. Friends Of Appropriate Ages

Version #1 Bucket Sort and Prefix Sum[Preferred]
99.23 
class Solution {
    public int numFriendRequests(int[] ages) {
        if (ages == null || ages.length == 0) {
            return 0;
        }
        /*
        age[B] <= 0.5 * age[A] + 7
        B > 0.5A + 7
        0.5A + 7 < B <= A
        0.5 A + 7 = A
        A = 14
        */
        int[] bucket = new int[121];
        int[] prefixSum = new int[121];
        for (int age : ages) {
            bucket[age]++;
        }
     
        for (int i = 1; i < 121; i++) {
            prefixSum[i] = prefixSum[i - 1] + bucket[i];
        }
        int result = 0;
        for (int i = 15; i < bucket.length; i++) {
            if (bucket[i] != 0) {
                result += (prefixSum[i] - prefixSum[i / 2 + 7] - 1) * bucket[i];
            }
        } 
        return result;
    }
}



Version #2 Two Pointers
Time O(nlogn)
Space O(1)

19.70 %
class Solution {
    public int numFriendRequests(int[] ages) {
        // age[B] <= 0.5 * age[A] + 7
        // B <= 0.5A + 7 || B > A
        // B > 0.5A + 7 && B <= A
        // (0.5A + 7, A]
        // if A <= 0.5A + 7 -> A <= 14 -> B doesn't exist
        Arrays.sort(ages);
        int result = 0;
        int j = 0, dupStart = 0;
        for (int i = 0; i < ages.length; i++) { // ages[i] -> A, ages[j, i) -> B, A request B
            if (ages[i] <= 14) continue;
            if (i > 0 && ages[i] != ages[i - 1]) dupStart = i;
            while (ages[j] <= 0.5 * ages[i] + 7) {
                j++;
            }
            if (j < i) {
                result += i - j;
            }
            if (dupStart < i) {
                result += i - dupStart;
            }
        }
        return result;
    }
}

826. Most Profit Assigning Work

Version #3 Greedy

56.20 %
class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        Arrays.sort(worker);
        int len = difficulty.length;
        int[][] tuple = new int[len][2];
        // worker[i + 1] can always finish work that worker[i] is assigned
        for (int i = 0; i < len; i++) {
            tuple[i][0] = difficulty[i];
            tuple[i][1] = profit[i];
        }
        Arrays.sort(tuple, Comparator.comparing(a -> a[0]));
        int curr = -1;
        int bestIndex = -1;
        int result = 0;
        for (int i = 0; i < worker.length; i++) {
            // check if this worker can do a more difficult work
            while (curr + 1 < len && tuple[curr + 1][0] <= worker[i]) {
                curr++;
                if (bestIndex == -1 || tuple[curr][1] > tuple[bestIndex][1]) bestIndex = curr;
            }
            result += bestIndex == -1 ? 0 : tuple[bestIndex][1];
        }
        return result;
    }
}




Version #2 Sort both Tuple and Worker + Two Pointers
A worker can always finish the work that one has less difficulty can do

63.82 %
class Solution {
    class Tuple {
int dif;
int prof;
public Tuple(int dif, int prof) {
this.dif = dif;
this.prof = prof;
}
}
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
List<Tuple> list = new ArrayList<>();
for (int i = 0; i < difficulty.length; i++) {
list.add(new Tuple(difficulty[i], profit[i]));
}
// difficulty in ascending order, profit in descending order
Collections.sort(list, (t1, t2) -> {
if (t1.dif == t2.dif) {
return t2.prof - t1.prof;
} else {
return t1.dif - t2.dif;
}
});
int maxProf = 0;
int result = 0;
Arrays.sort(worker);
int i = 0;
int j = 0;
while (i < worker.length) {
while (j < list.size() && list.get(j).dif <= worker[i]) {
maxProf = Math.max(maxProf, list.get(j).prof);
j++;
}
result += maxProf;
i++;
}
return result;
}
}


Version #1 Sort + BinarySearch
Self defined class with sort Tuple
Time O(mnlogn)
32.48 %

class Solution {
    class Tuple {
int dif;
int prof;
public Tuple(int dif, int prof) {
this.dif = dif;
this.prof = prof;
}
}
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
List<Tuple> list = new ArrayList<>();
for (int i = 0; i < difficulty.length; i++) {
list.add(new Tuple(difficulty[i], profit[i]));
}
// difficulty in descending order, profit in descending order
Collections.sort(list, (t1, t2) -> {
if (t1.dif == t2.dif) {
return t2.prof - t1.prof;
} else {
return t2.dif - t1.dif;
}
});
int maxProf = 0;
for (int i = list.size() - 1; i >= 0; i--) {
Tuple curr = list.get(i);
maxProf = Math.max(maxProf, list.get(i).prof);
curr.prof = maxProf;
}
int result = 0;
// Find the profit first tuple whose difficulty is smaller than current
for (int w : worker) {
result += binarySearch(list, w);
}
return result;
}

private int binarySearch(List<Tuple> list, int target) {
int start = 0;
int end = list.size() - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (list.get(mid).dif > target) {
start = mid + 1;
} else {
end = mid;
}
}
return list.get(start).dif <= target ? list.get(start).prof : 0;
}
}

828. Unique Letter String

Ref
907. Sum of Subarray Minimums
901. Online Stock Span
891. Sum of Subsequence Widths


Version #2 Map of queue of indices
Time O(S.length())  Space O(#distinct chars)
30.25 %
class Solution {
    public int uniqueLetterString(String S) {
        // A0....A1....A2 A would contribute to UNIQ (A1-A0)*(A2-A1) times
        if (S == null || S.length() == 0) {
            return 0;
        }
        long mod = (long)(1e9 + 7);
        long result = 0;
        Map<Character, Queue<Integer>> map = new HashMap<>();
        for (int i = 0; i < S.length(); i++) {
            char curr = S.charAt(i);
            Queue<Integer> que = map.getOrDefault(curr, new LinkedList<>(Arrays.asList(-1)));
            que.offer(i);
            if (que.size() > 2) {
                result = (result + (long)(-que.poll() + que.peek()) * (long)(i - que.peek())) % mod;
            }
            map.put(curr, que);
        }
        int len = S.length();
        for (Queue<Integer> que : map.values()) {
            result = (result + (long)(-que.poll() + que.peek()) * (long)(len - que.peek())) % mod;
        }
        return (int) result;
    }
}


Version #1 List of List of lastIndex

56.96 %
class Solution {
    public int uniqueLetterString(String S) {
        // "ABC"
        // left [0, 1] right[1, 2] -> all substring containing unique B -> 2 * 2 = 4
        // left [0, 0] right[0, 2] -> all substring cotaining unique A -> 1 * 3 = 3
        // "ABA"
        // A -> left[0, 0] right[0, 1] -> 1 * 2 = 2
        // B -> left[0, 1] right[1, 2] -> 2 * 2 = 4
        // A -> left[1, 2] right[2, 2] -> 2 * 1 = 2
        List<List<Integer>> lastIndex = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            lastIndex.add(new ArrayList<>());
        }
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            lastIndex.get(c - 'A').add(i);
        }
        int result = 0;
        for (int i = 0; i < 26; i++) {
            List<Integer> indices = lastIndex.get(i);
            int prev = -1;
            int curr = 0;
            int next = 0;
            for (int j = 0; j < indices.size(); j++) {
                curr = j == 0 ? indices.get(0) : next;
                next = j == indices.size() - 1 ? S.length() : indices.get(j + 1);
                result += (curr - prev) * (next - curr);
                prev = curr;
            }
        }
        return result;
    }
}

945. Minimum Increment to Make Array Unique

Version #2 Sort
The current number need to be at least prev + 1

Time O(nlogn) Space O(1)
class Solution {
    public int minIncrementForUnique(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        Arrays.sort(A);
        int prev = A[0];
        int result = 0;
        for (int i = 1; i < A.length; i++) {
            // a have to be at least prev + 1
            result += Math.max(prev + 1 - A[i], 0);
            prev = Math.max(A[i], prev + 1);
        }
        return result;
    }
}


Version # 1 Counter
Time O(n) Space O(n)
class Solution {
    public int minIncrementForUnique(int[] A) {
        int[] counter = new int[50000];
        int max = 0;
        int result = 0;
        for (int a : A) {
            counter[a]++;
            max = Math.max(max, a);
        }
        int j = 0;
        for (int i = 0; i <= max; i++) {
            while (counter[i] > 1) {
                j = Math.max(j, i + 1);
                while (counter[j] > 0) {
                    j++;
                }
                counter[j] = 1;
                counter[i]--;
                result += j - i;
            }
        }
        return result;
    }
}

947. Most Stones Removed with Same Row or Column

Version #1 Union Find

首先完全没思路，看了答案才知道是个number of island的题
然后对于UF中的id，一开始脑子抽了用hash = y * cols + x导致MLE
后来发现原来就直接用stones的index就完全可以表示id了。。。 mdzz

class Solution {
    int[] id;
    int[] size;
    int count;
    public int removeStones(int[][] stones) {
        count = 0;
        int len = stones.length;
        id = new int[len];
        size = new int[len];
        for (int i = 0; i < len; i++) {
            id[i] = i;
            size[i] = 1;
            count++;
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    connect(i, j);
                }
            }
        }
        return stones.length - count;
    }
   
    private int root(int i) {
        while (id[i] != i) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
   
    private void connect(int p, int q) {
        int rootP = root(p);
        int rootQ = root(q);
        if (rootP == rootQ) {
            return;
        }
        count--;
        if (size[rootP] < size[rootQ]) {
            id[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            id[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
    }
}

948. Bag of Tokens

Version #1 Greedy
Buy at the cheapest and sell at the most expensive

Time O(nlogn)

class Solution {
    public int bagOfTokensScore(int[] tokens, int P) {
        Arrays.sort(tokens);
        int left = 0;
        int point = 0;
        int max = 0;
        for (int right = tokens.length - 1; right >= left; right--) {
            while (left <= right && P >= tokens[left]) {
                P -= tokens[left++];
                point++;
            }
            max = Math.max(max, point);
            if (point > 0) {
                P += tokens[right];
                point--;
            }
        }
        return max;
    }
}

889. Construct Binary Tree from Preorder and Postorder Traversal

Version # 2 Iterative
Time O(n)
We keep walking down to the sub tree
Use stack to keep track of the path
When we see that current node's value in post[j], we know this subtree is done
We need to pop it out and construct other unfinished subtree which is on top of the stack

94.57 %
class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre == null || post == null || pre.length != post.length || pre.length == 0) {
            return null;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.addFirst(new TreeNode(pre[0]));
        for (int i = 1, j = 0; i < pre.length; i++) {
           
            while (stack.peekFirst().val == post[j]) {
                stack.removeFirst();
                j++;
            }
            TreeNode curr = new TreeNode(pre[i]);
            if (stack.peekFirst().left == null) {
                stack.peekFirst().left = curr;
            } else {
                stack.peekFirst().right = curr;
            }
            stack.addFirst(curr);
        }
        return stack.removeLast();
    }
}



Version #1 Recursion without mem
Time O(nlogn)
Can be improved by using a hashmap to trace the values in post
94.57 %
class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre == null || post == null || pre.length != post.length) {
            return null;
        }
        return build(pre, 0, pre.length - 1, post, 0, post.length - 1);
    }
 
    private TreeNode build(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(pre[preStart]);
        }
     
        TreeNode root = new TreeNode(pre[preStart]);
        preStart++;
        postEnd--;
        for (int i = postStart; i <= postEnd; i++) {
            if (pre[preStart] == post[i]) {
                root.left = build(pre, preStart, preStart + i - postStart, post, postStart, i);
                root.right = build(pre, preStart + i - postStart + 1, preEnd, post, i + 1, postEnd);
                break;
            }
        }
        return root;
    }
}

888. Fair Candy Swap

59.55 %
class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        if (A == null || B == null) {
            return new int[0];
        }
        Set<Integer> set = new HashSet<>();
        int sumA = 0;
        int sumB = 0;
        for (int a : A) {
            sumA += a;
            set.add(a);
        }
        for (int b : B) {
            sumB += b;
        }
        int diff = (sumA - sumB) / 2;
        for (int b : B) {
            if (set.contains(b + diff)) {
                return new int[]{b + diff, b};
            }
        }
        return new int[0];
    }
}

891. Sum of Subsequence Widths[TODO]

It is extremely tricky!


long count = (long)(
                (1l << i) - (1l << (len - 1 - i))
                )% mod;



19.43 %
class Solution {
    public int sumSubseqWidths(int[] A) {
        if (A == null) {
            return 0;
        }
        Arrays.sort(A);
       
        // 0
        //[1, 2, 3]
       
        // index  i  len - 1 - i
        //   0    0    2
        //   1    1    1
        //   2    2    0
        int len = A.length;
        long mod = (long)(1e9 + 7);
        long result = 0;
        long count = 1;
        for (int i = 0; i < len; i++) {
            // A[i] as upper bound -> 2^i
            // A[i] as lower bound -> 2^(len - 1 - i)
            result = (result + count * ((A[i] - A[len - 1 - i]) % mod)) % mod;
            count = (count << 1) % mod;
        }
        return (int)result;
    }
}

[I read the question wrong... It is sub-sequence instead of sub array!]
Everyone says order doesn't matter, but I don't know why it doesn't matter
Sub-array example
Original
[5, 6, 1, 3]      min/max
[5]                   5 5           
[5,6]                5 6
[5,6,1]             1 6
[5,6,1,3]          1 6
   [6]                6 6
   [6,1]             1 6
   [6,1,3]          1 6
      [1]             1 1
      [1,3]          1 3 
         [3]          3 3
After sorting
[1, 3, 5, 6]      min/max
[1]                   1 1           
[1,3]                1 3
[1,3,5]             1 5
[1,3,5,6]          1 6
   [3]                3 3
   [3,5]             3 5
   [3,5,6]          3 6
      [5]             5 5
      [5,6]          5 6 
         [6]          6 6

906. Super Palindromes

"398904669" "13479046850"
"1" "2"
"96915129" "1492347521772"
"38455498359" "999999999999999999"


Build palindrome
We can build a palindrome by giving a base string and reverse it
e.g.  123 -> 123321 / 12321

We know our input are less than 10^18 -> it's square root are less than 10^9
Since the square root is palindrome concatenated by base str, str is less than 10^5
We iterate over 10^5 and try to build all palindromes R -> check whether R^2 is a palindrome
二刷
58.95 %
class Solution {
    public int superpalindromesInRange(String L, String R) {
        // for any given number x, xr(reversed x)
        // we can build a palindrome by diong xx,x0xr,x1xr,...,x9xr
        int count = 0;
        long min = Long.valueOf(L);
        long max = Long.valueOf(R);
        for (int i = 1; i <= (int)1e5; i++) {
            if (check(i, i, min, max)) count++;
            if (check(i, i / 10, min, max)) count++;
        }
        return count;
    }
    private boolean check(long num, long rev, long min, long max) {
        while (num > 0) {
            rev = rev * 10 + num % 10;
            num /= 10;
        }
        if (rev % 10 >= 4) return false;
        long val = rev * rev;
        if (min <= val && val <= max) {
            return isPalin(val);
        }
        return false;
    }
    private boolean isPalin(long x) {
        long rev = 0;
        if (x != 0 && x % 10 == 0) return false;
        while (rev < x) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev == x || rev / 10 == x;
    }
}

一刷

4.00 %
class Solution {
    public int superpalindromesInRange(String L, String R) {
        int UPPER = (int)(1e5);
        int result = 0;
        long left = Long.valueOf(L);
        long right = Long.valueOf(R);
        // 123 -> 123321 / 12321
        for (int i = 0; i < UPPER; i++) {
            String str = String.valueOf(i);
            String reversedStr = new StringBuffer(str).reverse().toString();
            result += checkPalin(left, right, str + reversedStr) ? 1 : 0;
            result += checkPalin(left, right, str + reversedStr.substring(1)) ? 1 : 0;
        }
        return result;
    }

    private boolean checkPalin(long left, long right, String palin) {
        long value = Long.valueOf(palin);
        value *= value;
        if (left <= value && value <= right && isPalindrome(value)) {
            return true;
        }
        return false;
    }

    private boolean isPalindrome(long x) {
        long temp = x;
        long reverse = 0;
        while (temp > 0) {
            reverse = reverse * 10 + temp % 10;
            temp /= 10;
        }
        return x == reverse;
    }
}

907. Sum of Subarray Minimums

这个题的关键在于
当我们知道 譬如 [1, 5, 6, 9, 2, 4]
2 是[5- 4] 范围内最小的，那么以2 为min的subarray有多少呢？
是以2为结尾的subarray 和以2为开始的subarray的combination(multiplification)
因为它们必须包含2
后面的Stack比较straightforward

95.07 %
class Solution {
    public int sumSubarrayMins(int[] A) {
        // [3,1,2,4]
        //  2 as min -> left [2(2)] right[2(2), 4(3)]
        //  2 * (2 - 2 + 1) * (3 - 2 + 1) = 2 * 2(2 / 2,4) = 4
        //  [3,2,2,4]
        //  2 as min, left[3(0), 2(1)]  right[2(1), 2(2), 4(3)]
        //  2 * 2 * 3 = 6
        // left[>]  right[>=]
        if (A == null) {
            return 0;
        }
        // i = 2
        // curr =
        // 1 2 4
        //
        // index
        int len = A.length;
        Deque<Integer> stack = new ArrayDeque<>();
        long sum = 0;
        long mod = (long)(1e9 + 7);
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && A[stack.peekFirst()] >= A[i]) {
                int curr = stack.removeFirst();
                sum += (long)A[curr] * (curr - (stack.isEmpty() ? -1 : stack.peekFirst())) * (i - curr);
                sum = sum % mod;
            }
            stack.addFirst(i);
        }
       
        while (!stack.isEmpty()) {
            int curr = stack.removeFirst();
            sum += (long)A[curr] * (curr - (stack.isEmpty() ? -1 : stack.peekFirst())) * (len - curr);
            sum = sum % mod;
        }
        return (int)sum;
    }
}

923. 3Sum With Multiplicity

Version #1 Count the occurrence of all elements

Combination
Cnk = n!/(n-k)!*k!

75.68 %
class Solution {
    public int threeSumMulti(int[] A, int target) {
        Map<Integer, Long> map = new HashMap<>();
        for (int a : A) {
            map.put(a, 1l + map.getOrDefault(a, 0l));
        }
        int mod = (int)(1e9 + 7);
        List<Integer> array = new ArrayList<>(map.keySet());
        Collections.sort(array);
        long result = 0;
        for (int i = 0; i < array.size(); i++) {
            for (int j = 0; j <= i; j++) {
                int a = array.get(j);
                int b = array.get(i);
                int c = target - a - b;
                if (c >= b && map.containsKey(c)) {
                    long countA = map.get(a);
                    long temp = 0;
                    if (a == b && b == c) {
                        temp = countA * (countA - 1) * (countA - 2) / 6;
                    } else if (a == b) {
                        long countC = map.get(c);
                        temp = countA * (countA - 1) / 2 * countC;
                    } else if (b == c) {
                        long countC = map.get(c);
                        temp = countA * countC * (countC - 1) / 2;
                    } else if (a < b && b < c) {
                        temp = countA * map.get(c) * map.get(b);
                    }
                    result = (result + temp) % mod;
                }
            }
        }
        return (int)(result % mod);
    }
}



Version #2 HashMap

16.59 %
class Solution {
    public int threeSumMulti(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        // key-sum of two, value-count
        Map<Integer, Integer> map = new HashMap<>();
        int result = 0;
        for (int i = 0; i < A.length; i++) {
            result = (result + map.getOrDefault(target - A[i], 0)) % (int)(1e9 + 7);
            for (int j = i - 1; j >= 0; j--) {
                map.put(A[i] + A[j], 1 + map.getOrDefault(A[i] + A[j], 0));
            }
        }
        return result;
    }
}

942. DI String Match

第一次写了DFS然后TLE
后来看了别人的答案，发现其实是一个变相的dp
原始问题S e.g.

"IDID"
Output: [0,4,1,3,2]

可以分解成子问题
If we see 'I' and use the min number, we can guarantee that all numbers are larger than the current number, so what we choose later doesn't matter
The same idea, if we see 'D' and use the max number, we can guarantee that all numbers are smaller than the current number, so what we choose later doesn't matter
String S           numbers        result   
"IDID"               [0, 4]             0 ->  'I' will always be satisfied
"DID"                [1, 4]             4 ->  'D' will always be satisfied
"ID"                   [1, 3]             1 ->  'I' will always be satisfied


class Solution {
    public int[] diStringMatch(String S) {
        if (S == null) {
            return new int[0];
        }
        int left = 0;
        int right = S.length();
        int[] result = new int[S.length() + 1];
        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == 'I') {
                result[i] = left;
                left++;
            } else {
                result[i] = right;
                right--;
            }
        }
        result[S.length()] = left;
        return result;
    }
}

941. Valid Mountain Array

两个指针相向而行
如果左指针满足increasing就一直走
右指针满足decreasing就一直走
最终需要满足它们相等且左指针不在0点(in case of all increasing)
右指针不在最末点(in case of all decreasing)

class Solution {
    public boolean validMountainArray(int[] A) {
        if (A == null) {
            return false;
        }
        int i = 0;
        int j = A.length - 1;
        while (i + 1 < A.length && A[i + 1] > A[i]) {
            i++;
        }
        while (j > 0 && A[j - 1] > A[j]) {
            j--;
        }
        return i > 0 && j < A.length - 1 && i == j;
    }
}

847. Shortest Path Visiting All Nodes

[1ST TRY]
BFS比较straightforward
从所有点出发，每次向neighbor node探索一次，直到全部探索完
这里的问题是如何记录state
因为每个node可以重复走，所以不能通过node是否visited过来探索
这里的visited的含义是，站在当前的这个node，我已经探索过了哪些node，如果我站在当前的node而已经探索过的node set是重复的，就证明是一个重复的state
如果利用HashSet来记录站在当前node所visited过的node，就会成为Map -> (node, visited States) -> Map of Set<Set<Integer>> 非常复杂
观察到最多只有12个点，所以用一个int 的bit manipulation来记录visit过的点
bit x 位为1则证明这个点还没有visit过
如果 bit x位成为0就证明visit过了
所以一开始把0 - N bit都变成1，当这个mask == 0的时候就是走完了


100.00 %
class Solution {
    public int shortestPathLength(int[][] graph) {
        if (graph == null || graph.length <= 1) {
            return 0;
        }
        // 2 dimensional -> current node + state
        int init = 0;
        int N = graph.length;
        for (int i = 0; i < N; i++) {
            init |= 1 << i;
        }
        // curr[0] -> node, curr[1] -> state
        boolean[][] visited = new boolean[N][init + 1];
        Queue<int[]> que = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            int state = init & ~(1 << i);
            que.offer(new int[]{i, state});
            visited[i][state] = true;
        }   
        int steps = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            steps++;
            while (size-- > 0) {
                int[] curr = que.poll();
                // curr[0] node, curr[1] state
                int[] neighbors = graph[curr[0]];
                for (int neighbor : neighbors) {
                    int nextState = curr[1] & ~(1 << neighbor);
                    if (nextState == 0) {
                        return steps;
                    }
                    if (!visited[neighbor][nextState]) {
                        visited[neighbor][nextState] = true;
                        que.offer(new int[]{neighbor, nextState});
                    }
                }
            }
        }
        return steps;
    }
}

[2ND TRY]
Same idea with 1st try
Instead of using extra space to keep a visited matrix
I used the higher bits to set the node number
It's like hash the [node | visitedNodes] into a single integer
1.13 %
class Solution {
    public int shortestPathLength(int[][] graph) {
// start from any node, bfs until all nodes are visited
// use mask to keep track of visited states
if (graph == null || graph.length == 0 || graph[0] == null || graph[0].length == 0) {
return 0;
}
int N = graph.length;
int init = 0;
for (int i = 0; i < N; i++) {
init |= 1 << i;
}
int min = Integer.MAX_VALUE;
// The (2N, N] bits are used to mark current node
for (int start = 0; start < graph.length; start++) {
// node start as the entry point
Queue<Integer> que = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
// set bit(start) to zero
int initState = init & (~(1 << start));
que.offer(setCurr(initState, start, N));
visited.add(initState);
int step = 0;
while (!que.isEmpty()) {
step++;
int size = que.size();
while (size-- > 0) {
int curr = que.poll();
for (int next : graph[getCurr(curr, N)]) {
int nextState = getState(curr, N) & (~(1 << next));
if (nextState == 0) {
min = Math.min(min, step);
}
int hash = setCurr(nextState, next, N);
if (!visited.contains(hash)) {
visited.add(hash);
que.offer(hash);
}
}
}
}
}
return min;
}

private int setCurr(int state, int curr, int N) {
int mask = 1 << N;
while (curr-- > 0) {
mask <<= 1;
}
return state | mask;
}

private int getCurr(int state, int N) {
state = state >> N;
int result = 0;
while (state > 1) {
result++;
state >>= 1;
}
return result;
}

private int getState(int state, int N) {
int mask = 0;
for (int i = 0; i < N; i++) {
mask |= 1 << i;
}
return state & mask;
}
}