Leetcode/Lintcode Online Judge Solutions

Featured

Cheat Sheet

Question D F Data Structure Algorithms Comments
3Sum 3 5 array two pointers
3Sum Closest 3 1 array two pointers
4Sum 3 2 array
Add Binary 2 4 string two pointers
math
Add Two Numbers 3 4 linked list two pointers
math
Anagrams 3 4 string
hashtable
BackPack I 4 4 backpack dp
BackPack II 4 4 backpack dp
Balanced Binary Tree 1 2 tree dfs
Best Time to Buy and Sell Stock 2 1 array dp
Best Time to Buy and Sell Stock II 3 1 array greedy
Best Time to Buy and Sell Stock III 4 1 array dp
Binary Search Tree Iterator 5 2 BST Iterator
Binary Tree Inorder Traversal 4 3 tree
hashtable
recursion
morris
stack
Binary Tree Level Order Traversal 3 4 tree bfs
Binary Tree Level Order Traversal II 3 1 tree bfs
Binary Tree Maximum Path Sum 4 2 tree dfs
Binary Tree Zigzag Level Order Traversal 4 3 queue
tree
bfs
stack
Climbing Stairs 2 5 dp
Clone Graph 4 3 Graph BFS
HashMap
4*
Combination Sum 3 3 array combination DFS
Combination Sum II 4 2 array combination
Combinations 3 4 combination
Construct Binary Tree from Inorder and Postorder Traversal 3 3 array
tree
dfs
Construct Binary Tree from Preorder and Inorder Traversal 3 3 array
tree
dfs
Container With Most Water 3 2 array two pointers
Convert Sorted Array to Binary Search Tree 2 3 tree dfs
Convert Sorted List to Binary Search Tree 4 3 linked list recursion
two pointers
Copy List with Random Pointer 4 2 LinkedList O(1)方法还没做
Count and Say 2 2 string two pointers
Count of Smaller Number I 4 3 array sort+binary search
segment tree
Count of Smaller Number II 5 3 array segment tree 值型线段树
Data Stream Median 5 2 heap min/max heap 10*
new comparator用法
Decode Ways 3 4 string recursion
dp
Distinct Subsequences 4 2 string dp
Divide Two Integers 4 3 binary search
math
Edit Distance 4 3 string dp
First Missing Positive 5 2 array sort
Flatten Binary Tree to Linked List 3 3 tree recursion
stack
Generate Parentheses 3 4 string dfs
Gray Code 4 2 combination
Hash Function 3 1 hash
math
要知道如何避免乘法overflow
Heapify 3 3 Heap 掌握siftup/siftdown两种方法 知道时间复杂度怎么算的
House Robber 3 2 dp
Implement strStr() 4 5 string two pointers
KMP
rolling hash
Insert Interval 4 5 array
linked list
red black tree
sort
merge
Integer to Roman 3 4 math
Interleaving String 5 2 string recursion
dp
Jump Game 3 2 array
Jump Game II 4 2 array
K Sum 5 2 backpack dp
K Sum II 3 2 DFS 时间复杂度多少?
Largest Rectangle in Histogram 5 2 array stack
Length of Last Word 1 1 string
Letter Combinations of a Phone Number 3 3 string dfs
Linked List Cycle I 3 3 LinkedList fast slow pointers
Linked List Cycle II 4 3 LinkedList fast slow pointers
Longest Common Prefix 2 1 string
Longest Common Subsequence 4 2 2 Strings dp
Longest Common Substring 4 2 2 Strings dp
Longest Consecutive Sequence 4 3 array
Longest Increasing Subsequence 3 3 array dp
Longest Increasing Continuous subsequence I 3 3 array dp
Longest Increasing Continuous subsequence II 4 3 array dp
Longest Palindromic Substring 4 2 string
Longest Substring Without Repeating Characters 3 2 string
hashtable
two pointers
Longest Valid Parentheses 4 1 string dp
Lowest Common Ancestor 4 2 Binary Tree Divide&Conquer
LRU Cache 5 2 Doubly linked list Cache概念
基本功
Majority Number I 3 2 抵消的概念
Majority Number II 4 2 抵消的概念
Majority Number III 5 2 抵消的概念
Max Square 3 3 dp
Max Tree 5 1 stack 有空重新做一遍
Maximal Rectangle 5 1 array dp
stack
Maximum Depth of Binary Tree 1 1 tree dfs
Maximum Product Subarray 4 3 Array SubArray
prefix sum
SubArray系列问题
用类似前缀和解决
Maximum Subarray I 3 3 array prefix sum
Maximum Subarray II 4 2 array
Maximum Subarray III 5 1 array
Median of Two Sorted Arrays 5 3 array binary search
Merge Intervals 4 5 array
linked list
red black tree
sort
merge
Merge k Sorted Lists 3 4 linked list
heap
sort
two pointers
merge
用heap再做一遍
Merge Sorted Array 2 5 array two pointers
merge
Merge Two Sorted Lists 2 5 linked list sort
two pointers
merge
Min Stack 3 3 Stack
Minimum Adjustment Cost 5 1 array dp
Minimum Depth of Binary Tree 1 1 tree dfs
Minimum Path Sum 3 3 array dp
Minimum Subarray 3 3 subarray prefix sum 掌握前缀和概念
Minimum Window Substring 4 2 string two pointers
Multiply Strings 4 3 string two pointers
math
N Queens 4 3 array dfs
N Queens II 4 3 array dfs
Next Permutation 5 2 array permutation
Palindrome Number 2 2 math
Palindrome Partitioning 3 4 string dfs
Palindrome Partitioning II 4 3 string dp
Partition List 3 3 linked list two pointers
dummy node
Pascal's Triangle 2 1 array
Pascal's Triangle II 2 1 array
Path Sum 1 3 tree dfs
Path Sum II 2 2 tree dfs
Permutation Sequence 5 1 permutation math
Permutations 3 4 array permutation
Permutations II 4 2 array permutation
Plus One 1 2 array math
Populating Next Right Pointers in Each Node 3 3 tree dfs
Populating Next Right Pointers in Each Node II 4 2 tree dfs
Pow(x,n) 3 5 binary search math
Recover Binary Search Tree 4 2 tree dfs
Regular Expression Matching 5 3 string recursion
dp
Rehashing 3 1 Hashing 怎么对负数取模
Remove Duplicates from Sorted Array 1 3 array two pointers
Remove Duplicates from Sorted Array II 2 2 array two pointers
Remove Duplicates from Sorted List 1 3 linked list
Remove Duplicates from Sorted List II 3 3 linked list dummy node
Remove Element 1 4 array two pointers
Remove Nth Node From End of List 2 3 linked list fast slow pointers
Reorder List 4 2 LinkedList findMid/reverse/dummyHead
Restore IP Addresses 3 3 string dfs
Reverse Integer 2 3 math
Reverse Linked List I 2 3 Linked List dummy node 1
Reverse Linked List II 3 2 linked list two pointers
Reverse Nodes in k Group 4 2 linked list recursion
two pointers
Roman to Integer 2 4 math
Rotate Image 4 2 array
Rotate List 3 2 linked list two pointers
Same Tree 1 1 tree dfs
Scramble String 5 2 string recursion
dp
Search a 2D Matrix 3 3 array binary search
Search for a Range 4 3 array binary search
Search in Rotated Sorted Array 4 3 array binary search
Search in Rotated Sorted Array II 5 3 array binary search
Search Insert Position 2 2 array
Search Range in Binary Search Tree 3 3 BST
Set Matrix Zeroes 3 5 array
Simplify Path 3 1 string stack
Sliding Window Maximum 5 2 array deque Deque d = new ArrayDeque<>(),以及pollFirst(), pollLast(), offerFirst, offerLast(), peekFirst(), peekLast()用法以及时间复杂度分析,以及为什么要用deque
Sliding Window Median 5 2 array heap 两个heap维护一个median结构,注意hashHeap在此的运用和时间复杂度关系
Sort List 4 2 List fast slow pointers 涉及到findLinkedListMiddle, mergeLinkedList等基本功
Sort Colors 4 2 array sort
two pointers
Spiral Matrix 4 2 array
Spiral Matrix II 3 2 array
Sqrt(x) 4 4 binary search
String to Integer (atoi) 2 5 string math
Subsets 3 4 array recursion
combination
Subsets II 4 2 array recursion
combination
Substring with Concatenation of All Words 3 1 string two pointers
Sudoku Solver 4 2 array dfs
Sum Root to Leaf Numbers 2 4 tree dfs
Surrounded Regions 4 3 array bfs
dfs
Swap Nodes in Pairs 2 4 linked list
Symmetric Tree 1 2 tree dfs
Text Justification 4 2 string
Topological Sorting 4 3 Graph BFS
indegrees
4*
Trailing Zeros 3 1 math
Trapping Rain Water 4 2 array two pointers
stack
Triangle 3 1 array dp
Two Sum 2 5 array
set
sort
two pointers
Unique Binary Search Trees 3 1 tree dp
Unique Binary Search Trees II 4 1 tree dp
dfs
Unique Paths 2 3 array dp
Unique Paths II 3 3 array dp
Valid Number 2 5 string math
Valid Palindrome 2 5 string two pointers
Valid Parentheses 2 5 string stack
Valid Sudoku 2 2 array
Validate Binary Search Tree 3 5 tree dfs
Wildcard Matching 5 3 string recursion
dp
greedy
FB喜欢
Word Break 4 3 String dp
Word Ladder 3 5 graph bfs
shortest path
Word Ladder II 5 1 graph bfs+dfs 10*
Word Search 3 4 array dfs
ZigZag Conversion 3 1 string

Credits to:
1. All the questions are from Leetcode Online Judge/Lintcode
2. Some of the stats in (Difficulty|Frequency|Data Structure|Algorithms)columns are defined by peking2 in http://leetcode.cloudfoundry.com/
3. Some of the solutions are from 九章算法

FacebookTwitterGoogle+Share

Leetcode: 349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2].

Note:

  • Each element in the result must be unique.
  • The result can be in any order.

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    int count = 0;
    HashMap<Integer, Integer> twoSum1 = new HashMap<>();
    HashMap<Integer, Integer> twoSum2 = new HashMap<>();

    constructTwoPairMap(twoSum1, A, B);
    constructTwoPairMap(twoSum2, C, D);
    for (Integer pairSum : twoSum1.keySet()) {
        count += twoSum1.get(pairSum) * twoSum2.getOrDefault(pairSum * (-1), 0);
    }
    return count;
}

public void constructTwoPairMap(HashMap<Integer, Integer> map, int[] A, int[] B) {
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < B.length; j++) {
            int sum = A[i] + B[j];
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
    }
}

TCP VS UDP

UDP (User Datagram Protocol) – Light wight but not that reliable

Pros:

1. Packets size is smaller than TCP (udp header: 8 bytes vs tcp header 20bytes)

2. No connections to create and maintain

3. More control on when the data is sent

Cons:

1. No error recovery. lost packets are just discarded.

2. Packets can arrive out of order

3. No traffic control.

4. Optional checksum in IPv4, only mandatory in IPv6

TCP (Transmission Control Protocol) – Reliable but bigger communication overhead

3 way handshake

Pros:

1. Delivery acknowledgement. Receiver would send a respond confirming the packets has been received.

2. Retransmission. When the sender doesn’t get the confirmation from the receiver after a certain amount of time, it will resent the packets.

3. Traffic control. TCP delays transmission if the network is congested.

4. Checksum is now mandatory for both IPv6 and IPv4

Cons:

1. Bigger header

2. Data doesn’t always get sent out immediately (think of video conferencing)

3. Bigger traffic overhead (because of the retransmission and delivery acknowledgement)

Dungeon Game

Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K) -3 3
-5 -10 1
10 30 -5 (P)

Notes:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
            return 0;
        }
        int row = dungeon.length;
        int col = dungeon[0].length;
        //dp[i][j]: the minimum hp knight need to have at dungeon[i][j]
        int[][] dp = new int[row][col];
    
        //init bottom-right cell
        dp[row - 1][col - 1] = Math.max(1 - dungeon[row - 1][col - 1], 1);
    
        //init rightmost rooms
        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] =  Math.max(dp[i + 1][col - 1] - dungeon[i][col - 1], 1);
        }
        //init bottom rooms
        for (int j = col - 2; j >= 0; j--) {
            dp[row - 1][j] = Math.max(dp[row - 1][j + 1] - dungeon[row - 1][j], 1);
        }
        //dp
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                dp[i][j] = Math.max(Math.min(dp[i][j + 1] - dungeon[i][j], dp[i + 1][j] - dungeon[i][j]), 1);
            }
        }
    
        return dp[0][0];
    }

Phone Screen @Uber Oct. 26th, 2015

Given a pattern and an input string, check if the input string matches the pattern.

Eg.
pattern: abab
input: howwhathowwhat
mapping: a => how, b => what
so match(abab, howwhathowwhat) -> true
match(abab, whathowhowwhat) -> false
match(“”, “”) -> true
match(“a”, “a”) -> true
match(“ab”, “abab”) -> true
match(“aaaa”, “howwhatwhathow”) -> false
match(“aaaa”, “whatwhatwhatwhat”) -> true

Each char in pattern string can match 1-n chars in input string. Same char can only match same string. Different chars can match same strings.

class Solution {
    public boolean match(String pattern, String input) {
        if (pattern == null || input == null || input.length() < pattern.length()) {
            return false;
        }
        Map<Character, String> map = new HashMap<>();
        return matchHelper(pattern, 0, input, 0, map);
    }

    public boolean matchHelper(String pattern, int index, String input, int inputIndex, Map<Character, String> map) {
        if (index == pattern.length()) {
            if (inputIndex == input.length()) {
                return true;
            }
            return false;
        }
        char c = pattern.charAt(index);

        if (map.containsKey(c)) {
            String val = map.get(c);
            if (inputIndex + val.length() <= input.length() && val.equals(input.substring(inputIndex, inputIndex + val.length()))) {
                return matchHelper(pattern, index + 1, input, inputIndex + val.length(), map);
            }
        } else {
            for (int i = inputIndex; i < input.length(); i++) {
                String val = input.substring(inputIndex, i + 1);
                map.put(c, val);
                if (matchHelper(pattern, index + 1, input, i + 1, map)) {
                    return true;
                }
                map.remove(c);
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.match("", "")); //true
        System.out.println(s.match("a", "a")); //true
        System.out.println(s.match("ab", "abab")); //true
        System.out.println(s.match("abab", "howwhathowwhat")); //true
        System.out.println(s.match("abab", "howwhatwhathow")); //false
        System.out.println(s.match("aaaa", "howwhatwhathow")); //false
        System.out.println(s.match("aaaa", "whatwhatwhatwhat")); //true
    }
}

Sqrt(x)

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Challenge

O(log(x))

Solution: Binary search O(log(x)). Remember to use Long during computation

public int sqrt(int x) {
    // find the last number which square of it <= x
    long start = 1, end = x;
    while (start + 1 < end) {
        long mid = start + (end - start) / 2;
        if (mid * mid <= x) {
            start = mid;
        } else {
            end = mid;
        }
    }

    if (end * end <= x) {
        return (int) end;
    }
    return (int) start;
}

Shortest Word Distance I, II & III

Word Distance I – Only called once

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: One pass. O(n), Every time find an occurrence of word1 or word2, compare the distance of p1 and p2.

public int shortestDistance(String[] words, String word1, String word2) {
        int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;
    
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) 
                p1 = i;
    
            if (words[i].equals(word2)) 
                p2 = i;
    
            if (p1 != -1 && p2 != -1)
                min = Math.min(min, Math.abs(p1 - p2));
        }
    
        return min;
    }

Shortest Word Distance II – API, will be called multiple times

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: First preprocess the word to dict, which is a <word, list of index>map.

Then every time just get the word only check two list of indexes.

public class WordDistance {
    Map<String, List<Integer>> dict;
    public WordDistance(String[] words) {
        dict = new HashMap<>();
        for(int i=0;i<words.length;i++){
            if(dict.containsKey(words[i])){
                dict.get(words[i]).add(i);
            }else{
                List<Integer> indexes = new ArrayList<>();
                indexes.add(i);
                dict.put(words[i], indexes);
            }
        }
    }

    public int shortest(String word1, String word2) {
        if(dict==null||!dict.containsKey(word1)||!dict.containsKey(word2)){
            return 0;
        }
        int res = Integer.MAX_VALUE;
        List<Integer> indexes1 = dict.get(word1);
        List<Integer> indexes2 = dict.get(word2);
        int index1 = 0;
        int index2 = 0;
        while(index1<indexes1.size()&&index2<indexes2.size()){
            res = Math.min(res, Math.abs(indexes1.get(index1)-indexes2.get(index2)));
            if(indexes1.get(index1)<indexes2.get(index2)){
                index1++;
            }else{
                index2++;
            }
        }
        return res;
        
    }
}

Shortest Word Distance III – word1 could be the same as word2

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.

Note:
You may assume word1 and word2 are both in the list.

Solution: if word1==word2==words[], then p1=p2=i, and every time we update p1, we check the distance between p1 and p2.

public int shortestWordDistance(String[] words, String word1, String word2) {
    int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;

    for (int i = 0; i < words.length; i++) {
        if (words[i].equals(word1)) {
            p1 = i;
            if (word1.equals(word2) && p1 != -1 && p2 != -1) {
                min = Math.min(min, Math.abs(p1 - p2));
            }
        }

        if (words[i].equals(word2)) {
            p2 = i;
        }

        if (!word1.equals(word2) && p1 != -1 && p2 != -1) {
            min = Math.min(min, Math.abs(p1 - p2));
        }
    }

    return min;
}

Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

  1
 / \
2   3

return 6.

Solution: Divide and Conquer. for each node, calculate two maxPath:

1. maxSinglePath: start from root to any nodes, could be empty. 从root往下走到任意点的最大路径,这条路径可以不包含任何点.

2. maxPath: 从树中任意到任意点的最大路径,这条路径至少包含一个点. Max path in the tree, can not be empty, doesn’t have to include root.

So the result is root.maxPath

O(n) time complexity. Each node is visited once.

Version 1. cleaner version, with global variable

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
     
    int maxPath = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxSinglePath(root);
        return maxPath;
    }
    
    public int maxSinglePath(TreeNode root){
        if(root==null){
            return 0;
        }
        //devide
        int left = Math.max(0, maxSinglePath(root.left));
        int right = Math.max(0, maxSinglePath(root.right));
        
        //conquer
        maxPath = Math.max(maxPath, left+right+root.val);
        
        return Math.max(left, right)+root.val;
    }
}

Version 2. jiuzhang, with result class

private class maxPathResult {
    int maxSinglePath;
    int maxPath;
    public maxPathResult(int maxSinglePath, int maxPath) {
        this.maxSinglePath = maxSinglePath;//start from root to any nodes, could be empty
        this.maxPath = maxPath;//max path in the tree, can not be empty, doesn't have to include root
    }
}
public int maxPathSum(TreeNode root) {
    // write your code here
    return helper(root).maxPath;
}

public maxPathResult helper(TreeNode root) {
    if (root == null) {
        return new maxPathResult(0, Integer.MIN_VALUE);
    }
    //devide
    maxPathResult left = helper(root.left);
    maxPathResult right = helper(root.right);

    //conquer
    int maxSinglePath = Math.max(left.maxSinglePath, right.maxSinglePath) + root.val;
    maxSinglePath = Math.max(maxSinglePath, 0);

    int maxDoublePath = left.maxSinglePath + right.maxSinglePath + root.val;

    int maxPath = Math.max(Math.max(left.maxPath, right.maxPath), maxDoublePath);
    return new maxPathResult(maxSinglePath, maxPath);
}