Algorithm Problems Practices


logn
- bisection
- divide and conquer

X. DP
O(1) space - in place, reuse the input
-- multiple dp relations
- find sub-problems and relations
- dp: [i, j]; or dp[len-1] just start/or end
always think whether there is dp solution
dp[i] dp[i-1]
dp[i]  dp[j] 0<j<i
[], [][], or map

X. Kadane's algorithm
- dp, two pointers, scan, track and update local that includes a[i]
LeetCode 53 - Maximum Subarray
2. dp: dp(A, i) = dp(A, i - 1) > 0 ? dp(A, i - 1) : 0 + A[i];
the maxSubArray for A[0:i ] which must has A[i] as the end element
3. Divide and Conquer - nlogn

Maximum circular subarray sum

Max sum subsequence with non-consecutive elements
max_including(i) = max{max_excluding(i-1)+a[i], a[i]}
max_excluding(i) = max{max_including(i-1), max_excluding(i-1)}

Maximum Product Subarray
localMax, localMin, if(a[i] > 0) else


find the maximum number zeros in an array with one flip of a subarray allowed. A flip operation switches all 0s to 1s and 1s to 0s.

find maximum number of set bits after flipping a single contagious segment of bits

X. Knapsack
LeetCode 416 - Partition Equal Subset Sum
1. dp[target+1] or [nums.length+1][target+1]
dp[j] = dp[j] || dp[j - nums[i]]
https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand

X. DP
LintCode - Copy Books

LeetCode 474 - Ones and Zeroes
dp = new int[m + 1][n + 1];
dp[i][j] = Math.max(1 + dp[i-count[0]][j-count[1]], dp[i][j]);

LeetCode 446 - Arithmetic Slices II - Subsequence
- HashMap<Integer, Integer>[] dp
map[i].put(diff, map[i].get(diff)) + map[j].get(diff)) + 1);

LeetCode 375 - Wiggle Subsequence - link
return the length of the longest subsequence that is a wiggle sequence
up[i] - considering i​th element as the last element of the wiggle subsequence and ending with a rising wiggle.
down[i]
if nums[i] > nums[i-1] up[i] = down[i-1]+1 down[i]=down[i-1]
else if nums[i] < nums[i-1]  down[i]=up[i-1]+1 up[i] = up[i-1]
else down[i]= down[i-1] up[i] = up[i-1]
-- space optimization, only use up and down
2. Greedy

Leetcode 44 - Wildcard Matching
with support for '?' and '*'.
dp[s.length() + 1][p.length() + 1]
dp[i[j]: the first i characters in string s matches the first characters of string p.
dp[0][0] = true;
dp[i][0] = false;
dp[0][j] = dp [0][j - 1] if p.charAt(j - 1) == '*'
-- If p.charAt(j - 1) != '*', then dp[i][j] = dp[i - 1][j - 1] if s.charAt(i) == p.charAt(j) || p.charAt(j) == '?' (else false)
-- If p.charAt(j - 1) == '*', then
-- dp[i][j]
     = dp[i][j - 1] || // Match 0 character
     = dp[i - 1][j] // Match any sequence of characters
O(n) space - https://discuss.leetcode.com/topic/10794/my-java-dp-solution

LeetCode 10 - Regular Expression Matching: . and *
'*' Matches zero or more of the preceding element.
- DFS+Cache: dp[i][j] or DP
https://discuss.leetcode.com/topic/40371/easy-dp-java-solution-with-detailed-explanation
https://discuss.leetcode.com/topic/31974/java-4ms-dp-solution-with-o-n-2-time-and-o-n-space-beats-95
1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:
               1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
               2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                              dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
                           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty

Leetcode 139 - Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
1. DP: O(n^2)
Get words minLen, maxLen
boolean [] dp = new boolean[n+1];
dp[0] = true ;
dp[i] = dp[j] && dict.contains(sentences.subString(j,i)) 0<j<i

// Use trie to check whether subString is a word
2. DFS + Cache
3. BFS:

Word Break II
https://leetcode.com/discuss/91894/java-6ms-simple-solution-beating-88%25
http://www.jiuzhang.com/solutions/word-break-ii/
- avoid to use substring
boolean[][] isWord
boolean[] possible

LeetCode 287 - Perfect Squares
dp(i) = min{1+dp(i-j*j)}
https://discuss.leetcode.com/topic/26400/an-easy-understanding-dp-solution-in-java
bfs -  q.offer(0); visited.add(0);
https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics

https://discuss.leetcode.com/topic/2545/a-solution-using-bfs/6
The vertices of the graph are simply the positions of the first characters of the words and each edge actually represents a word

Lintcode: K Sum I
http://www.cnblogs.com/yuzhangcmu/p/4279676.html
int[][][] D = new int[len + 1][k + 1][target + 1];
D[i][j][t] = D[i - 1][j][t];
if (t - A[i - 1] >= 0) {
    D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]];
}

space op: int[][] D = new int[k + 1][target + 1];

Lintcode: k Sum II
- DFS

LeetCode 97 - Interleaving String
dp[i][j]  =
str3.charAt(i + j) == str1.charAt(i) && dp[ i - 1][j] ||
str3.charAt(i + j) == str2.charAt(j) && dp[i][j - 1]

LeetCode 132 - Palindrome Partitioning II
http://happycoding2010.blogspot.com/2015/10/leetcode-132-palindrome-partitioning-ii.html
Return the minimum cuts needed for a palindrome partitioning of s
isPal[i][j] store if s[i..j] is palindrome or not. res[j] is the min cut of s[0..j].

LeetCode 241 - Different Ways to Add Parentheses
DP: https://discuss.leetcode.com/topic/26076/java-recursive-9ms-and-dp-4ms-solution
- split string first
- dp[i][j] stores all possible results from the i-th integer to the j-th integer (inclusive)
- ArrayList<Integer>[][] dp
DFS: divide and conquer + cache
https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms/12

LeetCode 446 - Arithmetic Slices II - Subsequence
T(i, d) = summation of (1 + T(j, d)) as long as 0 <= j < i && d == A[i] - A[j]
Map<Integer, Integer>[] map = new Map[A.length];

LintCode 395 - Coins in a Line II
dp[i] means the largest value you(the first player) can get when you start from values[i]
dp[i] = values[i] + Math.min(dp[i+2], dp[i+3]);
dp[i] = Math.max(dp[i], values[i] + values[i+1] + Math.min(dp[i+3], dp[i+4]));


LeetCode 73 - Unique Paths II
if some obstacles are added to the grids. How many unique paths would there be
dp[i][j] = dp[i−1][j]+dp[i][j−1] if grid[i][j]=0
O(1) space - in place, reuse the input
https://discuss.leetcode.com/topic/4987/java-solution-using-dynamic-programming-o-1-space
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
if(obstacleGrid[i][j] == 1)
    obstacleGrid[i][j] = 0;

LeetCode 72 - Edit Distance
f(i, j) = f(i - 1, j - 1)
f(i, j) = 1 + min { f(i, j - 1), f(i - 1, j), f(i - 1, j - 1) }

LeetCode - 403 Frog Jump
DP https://discuss.leetcode.com/topic/59423/simple-easy-to-understand-java-solution
map = new HashMap≪Integer, HashSet≪Integer>>(stones.length);
List≪HashSet≪Integer>> dp
DFS + cache
https://discuss.leetcode.com/topic/59439/straight-forward-9ms-7-line-c-solution-with-explanation

LeetCode 97 - Interleaving String
1. DP:
dp[0][0] = true;
dp[0][j] = str3.charAt(j) == str2.charAt(j)
dp[i][0] = str3.charAt(i) == str1.charAt(i)
2. BFS
https://discuss.leetcode.com/topic/6562/8ms-c-solution-using-bfs-with-explanation

X. BFS
When to use?
- to find minimum steps
- two-end BFS, multi-end bfs
- BFS + PriorityQueue

LeetCode 417 - Pacific Atlantic Water Flow
bfs or dfs
https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean
if (pacific[i][j] && atlantic[i][j]) res.add(new int[] {i, j});

LeetCode - Word Ladder I
find the length of shortest transformation sequence from start to end
Two-end BFS
https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms
beginSet.add(beginWord);
endSet.add(endWord);
HashSet≪String> visited
if (beginSet.size() > endSet.size()) beginSet, endSet = endSet, beginSet;
if (endSet.contains(target)) return len + 1;

LeetCode Word Ladder II
https://discuss.leetcode.com/topic/17975/super-fast-java-solution-two-end-bfs
http://www.jiuzhang.com/solutions/word-ladder-ii/
http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/
LinkedList≪WordNode> queue
https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj
Map≪String,List≪String>> map: key is a word, the list is the word's pre words.
or:
unvisited = new HashSet≪String>(dict);
visited = new HashSet≪String>();

unvisited.removeAll(visited);
visited.clear();

LeetCode 407 - Trapping Rain Water II
https://discuss.leetcode.com/topic/60418/java-solution-using-priorityqueue
BFS + PriorityQueue

LeetCode [317] Shortest Distance from All Buildings
- do not go into a land, if it is not accessible by at least one of previous buildings.

LeetCode 286 - Walls and Gates
Fill each empty room with the distance to its nearest gate.
- Multi end bfs - O(n^2)
- Naive BFS or dfs - O(n^4)

LeetCode 433 - Minimum Genetic Mutation
https://discuss.leetcode.com/topic/65780/java-solution-using-bfs

Leetcode 200: Find the number of islands
- bfs, dfs, union-find
- number of lakes
- different shapes of number Island
http://www.1point3acres.com/bbs/thread-175393-1-1.html

LeetCode 247 - Strobogrammatic Number II
Find all strobogrammatic numbers that are of length = n.
- Use char[] to avoid string concatenation
iterative, bfs - https://discuss.leetcode.com/topic/28990/simple-java-solution-without-recursion
dfs - https://discuss.leetcode.com/topic/21579/accepted-java-solution-using-recursion
https://discuss.leetcode.com/topic/20733/my-concise-java-solution-using-dfs
public void findStrobogrammaticHelper(List res, char[] a, int l, int r)

LeetCode 248 - Strobogrammatic Number III
Count the total strobogrammatic numbers that exist in the range of low <= num <= high
https://discuss.leetcode.com/topic/44718/java-1ms-solution-with-comments-in-the-code

X. DFS
- Backtrack: don't forget to clear state
- dfs+cache
LeetCode 247 - Strobogrammatic Number II
Find all strobogrammatic numbers that are of length = n.
iterative, bfs - https://discuss.leetcode.com/topic/28990/simple-java-solution-without-recursion
Use char[] to avoid string concatenation
dfs - https://discuss.leetcode.com/topic/21579/accepted-java-solution-using-recursion
https://discuss.leetcode.com/topic/20733/my-concise-java-solution-using-dfs
public void findStrobogrammaticHelper(List<String> res, char[] a, int l, int r)

LeetCode 248 - Strobogrammatic Number III
Count the total strobogrammatic numbers that exist in the range of low <= num <= high
https://discuss.leetcode.com/topic/44718/java-1ms-solution-with-comments-in-the-code
if (i== low_len || i== high_len) strobogrammaticInRangeSameDigits(i, 0, i-1, 0); else strobogrammaticDigit+=counts(i,i);

LeetCode 212 - Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
- dfs + trie
https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00/
- pass TrieNode

LeetCode 395 - Longest Substring with At Least K Repeating Characters
- split by badChars and dfs
https://tech.liuchao.me/2016/09/leetcode-solution-395/
https://discuss.leetcode.com/topic/57265/java-d-c-solution

Leetcode 291 Word Pattern II
Map<Character, String> forwardMap, invertedMap

LeetCode124 - Word Search
find if the word exists in the grid
https://discuss.leetcode.com/topic/7907/accepted-very-short-java-solution-no-additional-space/39

LeetCode 22 – Generate Parentheses
generate all combinations of well-formed parentheses.
helper(List res, StringBuilder sb, int open, int close, int n)
DFS: https://discuss.leetcode.com/topic/5866/my-accepted-java-solution
-- dfs(ArrayList<String> result, String s, int left, int right)
DFS+cache
https://discuss.leetcode.com/topic/33127/java-easy-to-understand-recursive-dp-method-with-explanations/
helper(int n, List<String>[] lists)

BSF, DP
f(n) = (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0)
https://discuss.leetcode.com/topic/3474/an-iterative-method

LeetCode 320 - Generalized Abbreviation
DFS/Backtracking
https://discuss.leetcode.com/topic/32765/java-14ms-beats-100
Divide &Conquer
Bit String/Mark
- 2^n combinations

LeetCode 329. Longest Increasing Path in a Matrix
- DFS+Cache: dfs(int[][] matrix, int i, int j, int[][] memo)

LeetCode 267 - Palindrome Permutation II
void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> res)
private void helper(char[] array, List<String> result, Map<Character, Integer> map, int left, int right)

LeetCode - Subsets
res = new ArrayList<List>();
3. bit string
Math.pow(2, n)
if (((1 << j) & i) != 0) subset.add(nums[j]);

LeetCode 46 - Permutations
LeetCode 47 - Permutations II
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;

Google interview - max vacation days
Google – Get Some Beer
https://reeestart.wordpress.com/2016/06/28/google-get-some-beer/

X. Divide and Conquer
- subproblems
LeetCode 50 - Pow(x, n)
Google – Power Sum
return sum of n^0 + n^1 + … + n^n.
https://reeestart.wordpress.com/2016/06/10/google-power-sum/

X. merge sort
need one extra array - no need to create tmp array every time
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/code/MergeSort.java
void merge(Comparable[ ] a, Comparable[ ] tmp, int left, int right, int rightEnd )

LeetCode 218 - The Skyline Problem
LeetCode 315 - Count of Smaller Numbers After Self
LeetCode 327 - Count of Range Sum

Count Inversions in an array

Maximum Sum Path in Two Arrays
result += max(sum1, sum2); sum1=sum2=0;

Merge k sorted array
Find a permutation that causes worst case of Merge Sort

X. Quick sort/select
LeetCode 215 - Kth Largest Element in an Array
LeetCode 148 - Sort List
quick sort - partition, sort, concat
merge sort - findMiddle sort left/right, merge
http://www.chenguanghe.com/quicksort-for-linklist/

X. Slide Window
LeetCode 424 - Longest Repeating Character Replacement
you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters
https://discuss.leetcode.com/topic/63494/java-12-lines-o-n-sliding-window-solution-with-explanation
https://discuss.leetcode.com/topic/63471/java-sliding-window-easy-to-understand
(length of substring - number of times of the maximum occurring character in the substring) <= k
if(count(ch) > k){  ch[str[j] - 'A']--; break; }

LeetCode 30 - Substring with Concatenation of All Words
https://discuss.leetcode.com/topic/6617/an-o-n-solution-with-detailed-explanation/11
countMap, curMap, foundCount,
toFindMap, foundMap
O(KN)
2. trie

LeetCode 3 - Longest Substring Without Repeating Characters
https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation/
HashMap<Character, Integer> map - chracter -> last position
if (map.containsKey(s.charAt(i))) start = Math.max(start,map.get(s.charAt(i))+1);

LeetCode 340 - Longest Substring with At Most K Distinct Characters
https://discuss.leetcode.com/topic/41671/15-lines-java-solution-using-slide-window
follow up - stream
https://discuss.leetcode.com/topic/48827/java-o-nlogk-using-treemap-to-keep-last-occurrence-interview-follow-up-question

LeetCode 438 - Find All Anagrams in a String
- map = new int[256]; int count


LeetCode 67 - Minimum Window Substring
Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n).
https://leetcode.com/discuss/90376/o-n-5ms-java-solution-beats-93-18%25
Map<Character, Integer> needToFill, hasFound

http://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized


X. Two pointers
3Sum
- presort, O(N^2)
- how to avoid duplicate results
https://discuss.leetcode.com/topic/28857/easiest-java-solution

3Sum Smaller
https://discuss.leetcode.com/topic/23421/simple-and-easy-understanding-o-n-2-java-solution
nums[i] + nums[j] + nums[k] < target
count += right-left;

3Sum Closest
if (sum <= target) j++; else k--;

X. Trie
- use trie so no need to scan every candidate(O(n))
LeetCode 421 - Maximum XOR of Two Numbers in an Array
- use bit trie for int
- children = new Trie[2];
https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
2. 32n
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
if(set.contains(tmp ^ prefix)) max = tmp;

LeetCode 212 - Word Search II

logN related
X. Binary search/BiSection
- use bisection when it's difficult to find correct value, but easy to verify whether a value is correct
- split to half
LeetCode 222 -  Count Complete Tree Nodes
O(log(n)^2) https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2

LeetCode 287 - Find the Duplicate Number
1. nlogn - binary search/bisection
https://discuss.leetcode.com/topic/25580/two-solutions-with-explanation-o-nlog-n-and-o-n-time-o-1-space-without-changing-the-input-array/2
2. O(n)
- graph: index -> as graph
- find cycle in linkedlist
http://keithschwarz.com/interesting/code/?dir=find-duplicate
https://discuss.leetcode.com/topic/18864/simple-java-solution-in-o-n-without-extra-space
3. 32n
https://discuss.leetcode.com/topic/38493/o-32-n-solution-using-bit-manipulation-in-10-lines

LeetCode 410 - Split Array Largest Sum
minimize the largest sum among these m subarrays.
bisection - https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java

LeetCode 287 - Find the Duplicate Number
1. bisection - long*n
https://discuss.leetcode.com/topic/25580/two-solutions-with-explanation-o-nlog-n-and-o-n-time-o-1-space-without-changing-the-input-array
2. O(n)
- index->value graph subproblem
- find cycle in linkedlist
http://keithschwarz.com/interesting/code/?dir=find-duplicate
https://discuss.leetcode.com/topic/25685/java-o-n-time-and-o-1-space-solution-similar-to-find-loop-in-linkedlist

LintCode - Copy Books
Divide A into k or fewer partitions, such that the maximum sum over all the partitions is minimized.
http://sidbai.github.io/2015/07/25/Copy-Books/
http://www.geeksforgeeks.org/find-minimum-time-to-finish-all-jobs-with-given-constraints/
K people to copy books with different pages, return the number of smallest minutes need to copy all the books.
1. dp - minutes[i][j] = min( max( minutes[i-1][t], sum(t+1, j) )
- O(n^2 * k)
2. dp - O(n * k)
3. bisection - nlg(sum/k)
https://github.com/iFighting/Lintcode/blob/master/Java/Copy-Books.java

Codility: Lesson 12 Min Max Division
https://codility.com/programmers/lessons/14-binary_search_algorithm/
int left = max, right = sum;

Jobdu-1534
kth sum pairs from array a and b
http://www.acmerblog.com/offer-google-2-1173.html

X. Using Binary search tree
LeetCode 327 - Count of Range Sum
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
1. Merge Sort
2. Binary search tree
private class TreeNode {
    long val = 0;
    int count = 1;
    int leftSize = 0;
    int rightSize = 0;
    TreeNode left = null;
    TreeNode right = null;
    countSmaller(TreeNode root, long val)
    countLarger(TreeNode root, long val)
    private int rangeSize(TreeNode root, long lower, long upper) {
        int total = root.count + root.leftSize + root.rightSize;
        int smaller = countSmaller(root, lower);    // Exclude everything smaller than lower
        int larger = countLarger(root, upper);      // Exclude everything larger than upper
        return total - smaller - larger;
    }
}
for(int i = 1; i < sums.length; i++) {
    output += rangeSize(root, sums[i] - upper, sums[i] - lower);
    insert(root, sums[i]);
}

LeetCode 315 - Count of Smaller Numbers After Self
1. Binary search tree
https://leetcode.com/discuss/73762/9ms-short-java-bst-solution-get-answer-when-building-bst
class TreeNode{
    int smallerCount;
    int val;
    TreeNode left;
    TreeNode right;
}
2. Merge sort
http://algobox.org/count-of-smaller-numbers-after-self/
class Tuple {
    public int val;
    public int idx;
}
3. Use TreeSet
https://discuss.leetcode.com/topic/31422/easiest-java-solution/12

Binary search
LeetCode 153 - Find the minimum element in a sorted and rotated array
mid = low + (high - low) / 2;
Compare num[mid] with num[high]

LeetCode 33 - Searching an Element in a Rotated Sorted Array

LeetCode 162 - Find Peak Element: num[i] ≠ num[i+1]
- Compare mid with mid+1
nums[left - 1] < nums[left] && nums[right] > nums[right + 1]
while (right - left > 1) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < nums[mid + 1]) {
        left = mid + 1;
    } else {
        right = mid;
    }
}
return (left == N - 1 || nums[left] > nums[left + 1]) ? left : right;

Bisection
Given a result, it is easy to test whether it is valid or not.
LeetCode 410 - Split Array Largest Sum
- binary(nums, m, sum, max);
LeetCode 367 - Valid Perfect Square

X. Interval
- First sort these intervals somehow
- Think as different events - start, end
- sort interval + greedy
- merge interval

LeetCode 218 - The Skyline Problem
- (start/end, height) tuple, set the start segment as negative height or Edge:(x, height, isStart)
- sort interval
- TreeMap<Integer, Integer> heightMap: key is the height, value is the count
- prevHeight, currHeight = heightMap.firstKey();
heightMap = new TreeMap<>(Collections.reverseOrder());
heightMap.put(0,1);
pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
https://discuss.leetcode.com/topic/38065/java-solution-using-priority-queue-and-sweepline/
http://www.programcreek.com/2014/06/leetcode-the-skyline-problem-java/
https://discuss.leetcode.com/topic/22482/short-java-solution

LeetCode 56 - Merge Intervals
- Sort the intervals based on increasing order of starting time
- if prev.end >= curr.start  prev = merged else result.add(prev); prev = curr;

LeetCode 253 - Meeting Rooms II
https://discuss.leetcode.com/topic/35253/explanation-of-super-easy-java-solution-beats-98-8-from-pinkfloyda
- int[] starts, ends

Use TreeMap to store intervals
LeetCode 352 - Data Stream as Disjoint Intervals
- TreeMap<Integer, Interval> treeMap: key is the start point
- lowerKey(), higherKey()

LettCode 452 - Minimum Number of Arrows to Burst Balloons
- sort interval and greedy
https://discuss.leetcode.com/topic/66709/c-easy-understood-solution-sort/

LeetCode 435 - Non-overlapping Intervals
- sort interval by end
https://discuss.leetcode.com/topic/65828/java-solution-with-clear-explain

LeetCode 436 - Find Right Interval
TreeMap<Integer, Integer> intervalMap: key is the start, value is the index
- first put all intervals to the map: sorted by start
- intervalMap.ceilingEntry(intervals[i].end);

Google – Maximum Time Range Overlaps
https://reeestart.wordpress.com/2016/07/02/google-maximum-time-range-overlaps/

Google - remove alarm
https://reeestart.wordpress.com/2016/06/30/google-remove-alarm/
hash map - map priority to set of alarm id
max priority heap - PriorityQueue<Integer>

Google – Find a Path Among Circles
O(n^2) - https://reeestart.wordpress.com/2016/07/02/google-find-a-path-among-circles/


Bucket
LeetCode - 220 Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
slide window + bucket
https://leetcode.com/discuss/38206/ac-o-n-solution-in-java-using-buckets-with-explanation
https://discuss.leetcode.com/topic/27608/java-python-one-pass-solution-o-n-time-o-n-space-using-buckets/
https://leetcode.com/discuss/68090/easy-ac-solution-using-treeset-long-in-java

X. Ordered Stack
LeetCode 42 - Trapping Rain Water
1. Two Pointers
comapre height[left] and height[right]
2. Left and right array
int[] leftMax, rightMax
3. Ordered Stack - decreasing
s.push(i++); - store index
result += stack.isEmpty()? 0:(Math.min(A[stack.peek()],A[i])-A[bot])*(i-stack.peek()-1);

Next Greater Element
http://www.ideserve.co.in/learn/next-great-element-in-an-array

X. Stack
LeetCode 456 - 132 Pattern
Stack to maintain min-max: max after min till current element
https://discuss.leetcode.com/topic/68193/java-o-n-solution-using-stack-in-detail-explanation

TreeMap
Use TreeMap/TreeSet instead of PriorityQueue if it works and you need remove item from them

X. Union Find
http://algs4.cs.princeton.edu/15uf/UF.java.html
need know size of the nodes to init union-find
- Weighted Quick-Union and path compression
- O(1) ops: union, find, count, maxUnionCount, getHighestRank
- flattened parent tree
- no need to build/store graph (from edges array)

LeetCode 261 - Graph Valid Tree
1. uf
2. dfs
  boolean hasCycle(List<List<Integer>> adjList, int currentId, boolean[] visited, int parentId)
  if ((visited[v] && parentId != v) || (!visited[v] && hasCycle(adjList, neighborId, visited, currentId))) return hasCycle=true
3. bfs

LeetCode 130 - Surrounded Regions
1. dfs, bfs
find all 'O' not surrounded by 'X' (at or connected to the edge of the board ) and changed to '#'
flip the remain 'O' into X
flip the '#' back to 'O'
2. uf - union all the 'O' nodes on the boundry to a dummy node

LeetCode 128 - Longest Consecutive Sequence
1. use hashset, then check left and right
- but doesn't work for stream
https://discuss.leetcode.com/topic/17980/another-accepted-java-o-n-solution
2. https://discuss.leetcode.com/topic/9088/o-n-hashmap-java-solution
Map<Integer, Integer> map:  keep track of the sequence length and store that in the boundary points of the sequence.
3. uf: maxUnion or getHighestRank
https://discuss.leetcode.com/topic/29286/my-java-solution-using-unionfound
Map<Integer,Integer> map: value -> index
if(map.containsKey(nums[i]+1)) uf.union(i,map.get(nums[i]+1));

Detect Cycle in a an Undirected Graph
Number of Islands
LeetCode 323 - Number of Connected Components in an Undirected Graph
LeetCode 261 - Graph Valid Tree
LeetCode 305 - Number of Islands II
Group Contacts

X. Graph algorithm - O(V+E)
- Map<Integer, List<Integer>> map
- List<List<Integer>> adjList

 topological sort
-- Put indegree=0 nodes to queue, iterate queue,  and decrease indegree of the node's neighbors by 1, if indegree is now 0, put into queue
- time complexity O(V+E), space O(V)
Leetcode 310 - Minimum Height Trees
List<Set<Integer>> adj
LeetCode 210 - Course Schedule II
LeetCode 269 -  Alien Dictionary
https://discuss.leetcode.com/topic/32900/java-bfs-solution
- build graph
dfs
https://discuss.leetcode.com/topic/33565/3ms-clean-java-solution-dfs
visited[i] = -1. Not even exist.
visited[i] = 0. Exist. Non-visited.
visited[i] = 1. Visiting.
visited[i] = 2. Visited.

LeetCode 444 - Sequence Reconstruction
https://discuss.leetcode.com/topic/65948/java-solution-using-bfs-topological-sort/5
- build the edge for adjacent ints in the array
Map<Integer, List<Integer>> graph
Map<Integer, Integer> indegree

Eulerian path/circuit
LeetCode 332 - Reconstruct Itinerary
https://discuss.leetcode.com/topic/36370/short-ruby-python-java-c
public List<String> findItinerary(String[][] tickets) {
    for (String[] ticket : tickets)
        targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
    visit("JFK");
    return route;
}
Map<String, PriorityQueue<String>> targets = new HashMap<>();
List<String> route = new LinkedList();
void visit(String airport) {
    while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
        visit(targets.get(airport).poll());
    route.add(0, airport);
}

X. Binary tree
- usually expected runtime for tree is O(n)
- PreOrder/InOrder/PostOrder/LevelOrder traverse
- Use PostOrder Traverse
Leetcode 124 - 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.
private int maxPathDown(TreeNode node) {
    if (node == null) return 0;
    int left = Math.max(0, maxPathDown(node.left));
    int right = Math.max(0, maxPathDown(node.right));
    maxValue = Math.max(maxValue, left + right + node.val);
    return Math.max(left, right) + node.val;
}
LeetCode 437 - Path Sum III
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards
https://discuss.leetcode.com/topic/64526/17-ms-o-n-java-prefix-sum-method
- preorder tree traverse
- use hashmap to track: the prefix sum -> how many ways get to this prefix sum
- map.put(sum, map.get(sum)-1); // Remove the current node so it wont affect other path

LeetCode 250: Count Univalue Subtrees
- post order
Remove the paths from root to leaf whose sum is not equal to given K.
http://algorithmsandme.in/2014/03/remove-all-nodes-in-binary-tree-which-dont-lie-in-path/

LeetCode 230 - Find k-th smallest element in BST
- inorder search, return when count decrease to 0 from k
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently?

LeetCode 298 - Binary Tree Longest Consecutive Sequence
- preorder: count = (root.val - val == 1)?count+1:1;

LeetCode 107 - Binary Tree Level Order Traversal II
- bottom-up level order

LeetCode 103 - Printing a Binary Tree in Zig Zag Level-Order
If we only need print, it's easier to first get all level nodes in correct order then print
X. bfs https://discuss.leetcode.com/topic/42184/java-easy-understand-recursive-methods-beats-96-attach-easy-bfs-methods
Queue<TreeNode>, boolean leftToRight = !leftToRight;
if(leftToRight) levelNodes.add(n.val); else levelNodes.addFirst(n.val);
x. dfs - https://discuss.leetcode.com/topic/3413/my-accepted-java-solution
ArrayList<LinkedList<Integer>> result
x. 2 stacks
https://discuss.leetcode.com/topic/3318/my-ac-java-code
https://discuss.leetcode.com/topic/32427/java-double-stack-solution
Stack<TreeNode> oddSt, evenSt

X. Binary search tree
LeetCode 333 - Largest BST Subtree
class Wrapper{
    int size;
    int lower, upper;
    boolean isBST;
}

LeetCode 95 - Unique Binary Search Trees II
DFS - divide and conquer

X. Tree with only parent node
Google – Sum of Subtree with Only Parent Pointer
https://reeestart.wordpress.com/2016/06/23/google-sum-of-subtree-with-only-parent-pointer/
- reconstruct parent -> child
Map<TNode, List<TNode>> tree

X. Bit trick
- 23n, loop and check very bit
LeetCode 287 - Find the Duplicate Number
LeetCode 421 - Maximum XOR of Two Numbers in an Array

X. Game theory
If a player is able to move to a losing position then he is in a winning position.
If a player is able to move only to the winning positions then he is in a losing position.
LeetCode flip game II
DFS + Cache (top-down)
- use it's dp(bottom-up) to time complexity
- Map<String, Boolean> winMap
- if(!canWin(opponent, map))

Google – Initialize Board
radom + backtrack - https://reeestart.wordpress.com/2016/07/01/google-initialize-board/

Math
LeetCode 60 - Permutation Sequence
Given n and k, return the kth permutation sequence.
k--;
mod = mod / (n - i);
int curIndex = k / mod;
k = k % mod;
builder.append(list.remove(groupIndex));

X. Random
LeetCode 398 - Random Pick Index
https://discuss.leetcode.com/topic/58301/simple-reservoir-sampling-solution
if (rnd.nextInt(++count) == 0) result = i;

X. Misc
LeetCode 158 - Read N Characters Given Read4 II
https://discuss.leetcode.com/topic/6402/clean-accepted-java-solution

char[] buffer, int offset, remaining, boolean isEndOfFile

LeetCode 289 - Game of Life
use 2 bits: [2nd bit, 1st bit] = [next state, current state]

LeetCode 361 - Bomb Enemy
1. v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]
2.
rowhits, colhits[n]
for (int k=j; k<n && grid[i][k] != 'W'; k++)
    rowhits += grid[i][k] == 'E';
for (int k=i; k<m && grid[k][j] != 'W'; k++)
    colhits[j] += grid[k][j] == 'E';
result = max(result, rowhits + colhits[j]);

LeetCode 300 - Longest Increasing Subsequence
1.
int i = Collections.binarySearch(dp, num);
dp.set((i<0) ? -i-1 : i, num);
-- O(nlogn)
2. DP O(N^2)

4Sum
https://discuss.leetcode.com/topic/12368/clean-accepted-java-o-n-3-solution-based-on-3sum
http://www.lifeincode.net/programming/leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java/
O(N^3)
HashMap<Integer, ArrayList<Pair>> hashMap

LeetCode 454 - 4Sum II
https://discuss.leetcode.com/topic/67593/clean-java-solution-o-n-2

Leetcode 370 - Range Addition
https://discuss.leetcode.com/topic/49691/java-o-k-n-time-complexity-solution
res[start] += value;
res[end+1] -= value;

LeetCode 406 - Queue Reconstruction by Height
1. sort + insert: by height then index
https://discuss.leetcode.com/topic/60394/easy-concept-with-python-c-java-solution

Rearrange Positive and Negative Numbers of Array On Each Side with­out chang­ing their respec­tive order
- use reverse to avoid extra tmp array

Google – Shortest Words Contain Input String
- Inverted Index
Map<Character, List<String>> invertedIndex
set.retainAll(invertedIndex.get(c));

Hash - feature key
Google – Plate and Dictionary
- prime product as string key

LCA
-- Node to Node Binary Tree Path

Posted by at
Labels:

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)