Tips on Using Eclipse Effectively

Tips on Using Eclipse Effectively
Useful Eclipse Shortcut Keys

ALT + Left/Right ArrowMove backward/forward in the editor navigation history
CTRL+OShow the quick outline for the editor input
CTRL+KFind next item, no need to ctrl+f, type some words, then search
CTRL+1Activates the quick fix
CTRL+SPACEContent Assist
ALT+/Word completion
ALR+SHIFT+RRename the selected element
ALT+SHIFT+MExtract statements into a new method and use the new method
Ctrl + LGo To Line
CTRL+TShow quick hierarchy of the selected element
CTRL + SHIFT + FFormat code
CTRL+SHIFT+OOrganize imports
Ctrl+Shift+XChange the selection to upper case, useful in declare final variable
Ctrl+Shift+YChange the selection to lower case
Ctrl+Shift+HOpen a type in the type hierarchy view
Ctrl+Shift+SSave all current contents
Ctrl+Shift+WClose all editors
Ctrl+Shift+GSearch for references to the selected element in the workspace
CTRL+EShow a list of all open editors
CTRL + DDelete row
CTRL+MToggle maximize/restore state of active view or editor
CTRL+SHIFT+U    Shows the Occurrences in File quick menu
Ctrl+Shift+R        Open Resources
CTRL + I               Corrects indentation
Ctrl+M                  Maximize Active View or Editor
Context Information, If typing a method call with several parameters use this to show the applicable parameter types.
Alt+Left/Right Backward/Forward History
CTRL + I         Corrects indentation
CTL + N            Open new type wizard
CTRL + J           Incremental search
CTRL + SHIFT + L Shows you a list of your currently defined shortcut keys
CTRL+F6          Use to move between open editors
CTRL+F7          Move between views
CTRL+F8          Move between perspectives
To configure the shortcut key, click Window --> Preferences --> General --> Keys

Associate editors with file types:
Window -> Preferences -> General -> Editors -> File Associations

Find: ^\s*\n
Replace with: (empty)

Eclipse plugins:
Code quality:
It is used to enforce Coding Standards in Java Project, such as Naming conventions, Coding problems, Best Practices.

PMD focuses more on preemptive defect detection.

FindBugs concentrates on detecting potential bugs and performance issues.
Klocwork is aimed at improving software security, quality, and reliability. It is not free, but we can get 30 days free trail. And it is really very cool.

Mylyn can integrate with issue management systems such as Bugzilla, and it also provides context management, which can hide much of the detail of projects that is irrelevant to the task at hand.
Mylyn is very helpful, especially your main job is to fix defects, or focus on one component of a big project.

EPIC - Perl Editor and IDE for Eclipse
The PyDev Update Site
Groovy Eclipse plugin
Aptana Studio

Recently, I re-downloaded and reinstalled jdk, and Eclipse always shows this error:
'UnsupportedEncodingException: GBK'. After google search, on,
I found out this is because I installed a JRE only for US English, and I should choose to download and install Multi-language JRE.

When we save file, it may print out the error "Some characters can not be mapped using GBK character encoding".
The solution is to change file encoding to 'utf-8':
Select Window -> Preferences ->General
Select  Workspace , set Text file encoding to 'utf-8'.
Select Content Types, set Default encoding to 'utf-8'

Ignore white space when compare two files in Eclipse IDE
When compare two files in Eclipse, many times lines differ only in white spaces, and we don't want to notice this minor difference.
Select Window -> Preference -> Compare/Path, and in 'General' tab, select the checkbox --'Ignore white space'.

Java Power tools safari online book

Advanced Data Structures

- Related with greedy algorithm
- Use minQueue to get kth max, maxQueue to get kth min
- merge sort with PQ

- Remove is O(n)

LeetCode 414 - Third Maximum Number
Use PriorityQueue with HashSet to check duplicate
- TreeSet (not PQ as need call contains)
if(set.size() > 3) {set.remove(set.first());}
- Maitain state: first, second, third

LeetCode 502 - IPO
find a project with max profit and within current capital capability
- 2 PriorityQueue
        PriorityQueue<int[]> pqCap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        PriorityQueue<int[]> pqPro  = new PriorityQueue<>((a, b) -> (b[1] - a[1]));        
        for (int i = 0; i < k; i++) {
            while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
            W += pqPro.poll()[1];

LeetCode 632 - Smallest Range

LeetCode 630 - Course Schedule III
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dthday. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses,(a,b)->a[1]-b[1]); //Sort the courses by their deadlines (Greedy! We have to deal with courses with early deadlines first)
        PriorityQueue pq=new PriorityQueue<>((a,b)->b-a);
        int time=0;
        for (int[] c:courses) 
            time+=c[0]; // add current course to a priority queue
            if (time>c[1]) time-=pq.poll(); //If time exceeds, drop the previous course which costs the most time. (That must be the best choice!)
        return pq.size();

LeetCode 378 - Kth Smallest Element in a Sorted Matrix
- Bisection O(nlogm) while m = max - min
    public int kthSmallest(final int[][] matrix, int k) {
        int c = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>(
            k, (o1, o2) -> matrix[o1[0]][o1[1]] - matrix[o2[0]][o2[1]]);
        queue.offer(new int[] {0, 0});
        while (true) {
            int[] pair = queue.poll();
            if (++c == k) {
                return matrix[pair[0]][pair[1]];
            if (pair[0] == 0 && pair[1] + 1 < matrix[0].length) {
                queue.offer(new int[] {0, pair[1] + 1});
            if (pair[0] + 1 < matrix.length) {
                queue.offer(new int[] {pair[0] + 1, pair[1]});
LeetCode 373 - Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Find elements more than K times
Given m sorted lists, find out the elements more than k times. If an element appear more than once in a list, count it only once.
- Use PriorityQueue instead of HashMap to save space

POJ 4302 Holedox Eating
- 2 PriorityQueue

LeetCode 621 - Task Scheduler
- Use Priority Queue
- Calculating Idle slots
LeetCode 358 - Rearrange String k Distance Apart
Rearrange Characters in String With No Adjacent Duplicate Characters

LeetCode 632 - Smallest Range
You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the klists.
- Merge k sorted list

LeetCode 407 - Trapping Rain Water II

Double Monotonic Queue

Deque q = new ArrayDeque<>();
Deque doubleQueue = new LinkedList<>();

LeetCode 239 - Sliding Window Maximum
- Store index instead of the value
- Only keep promising elements in the deque

LeetCode 102 - Binary Tree Level Order Traversal
  for(int i=0; i}

LeetCode 127 - Word Ladder I
- BFS, Two-end BFS
Deque queue = new ArrayDeque();
Set visited

LeetCode 111 - Minimum Depth of Binary Tree

Interval tree
- augmented self-balancing bst: low, high, max
- logn: add/Remove(interval), overlapping(x)

Google – Toggle Problem

Using Multiple Data Structures 
Google – Manager Peer Problem
- Tree + Hash Table
Map nodeMap
private class TNode {
  int val;
  TNode parent;
  List neighbors;

Design a data structure that supports insert, delete, search and getRandom in constant time
//A hash where keys are array elements and vlaues are ndexes in arr[]
HashMap  hash;
ArrayList arr;

LeetCode 432 - All O`one Data Structure
Inc(Key), Dec(Key), GetMaxKey(), GetMinKey()

    private Bucket head;
    private Bucket tail;
    // for accessing a specific Bucket among the Bucket list in O(1) time
    private Map countBucketMap;
    // keep track of count of keys
    private Map keyCountMap; or the value can be Bucket
    // each Bucket contains all the keys with the same count
    private class Bucket {
        int count;
        Set keySet;
        Bucket next, prev;
LeetCode - LRU Cache
    private int capacity;
    private HashMap hs = new HashMap();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head; = tail;

    public int get(int key) {
        if( !hs.containsKey(key)) {
            return -1;

        // remove current
        Node current = hs.get(key); =; = current.prev;

        // move current to tail

        return hs.get(key).value;

    public void set(int key, int value) {
        // this internal `get` method will update the key's position in the linked list.
        if (get(key) != -1) {
            hs.get(key).value = value;

        if (hs.size() == capacity) {
   = head;

        Node insert = new Node(key, value);
        hs.put(key, insert);

    private void move_to_tail(Node current) {
        current.prev = tail.prev;
        tail.prev = current; = current; = tail;
LeetCode 460 - LFU Cache
when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
- Doubly Linked List + HashMap
    private Node head = null;
    private int cap = 0;
    private HashMap valueHash = null;
    private HashMap nodeHash = null;
Design Phone Directory
isTaken(String phone) takeNumber(String phone) giveMeANumber()
- Trie

Stock Ticker
  1. void addOrUpdate(String stock, double price) add or update the price of a stock to the data structure.
  2. List> top() return the top k price stocks and their current prices.
- HashMap contains all elements, MinHeap or TreeSet contains top(k)

Sparse Matrix
Implementing Stack using priority queue.
- assign priority to the elements that are being pushed

* insert(key, value, timestamp)
* get(key, timestamp)
//> = =
HashMap> map = new HashMap<>();

Design a stack with operations on middle element
- push, pop
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element.
- Doubly Linked List

Min Stack

Algorithm Problems Practices

- bisection
- divide and conquer

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]]

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

LeetCode 10 - Regular Expression Matching: . and *
'*' Matches zero or more of the preceding element.
- DFS+Cache: dp[i][j] or DP
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
- avoid to use substring
boolean[][] isWord
boolean[] possible

LeetCode 287 - Perfect Squares
dp(i) = min{1+dp(i-j*j)}
bfs -  q.offer(0); visited.add(0);
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
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

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

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
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
map = new HashMap≪Integer, HashSet≪Integer>>(stones.length);
List≪HashSet≪Integer>> dp
DFS + cache

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

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

LeetCode 417 - Pacific Atlantic Water Flow
bfs or dfs
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
HashSet≪String> visited
if (beginSet.size() > endSet.size()) beginSet, endSet = endSet, beginSet;
if (endSet.contains(target)) return len + 1;

LeetCode Word Ladder II
LinkedList≪WordNode> queue
Map≪String,List≪String>> map: key is a word, the list is the word's pre words.
unvisited = new HashSet≪String>(dict);
visited = new HashSet≪String>();


LeetCode 407 - Trapping Rain Water II
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

Leetcode 200: Find the number of islands
- bfs, dfs, union-find
- number of lakes
- different shapes of number Island

LeetCode 247 - Strobogrammatic Number II
Find all strobogrammatic numbers that are of length = n.
- Use char[] to avoid string concatenation
iterative, bfs -
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

- 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 -
Use char[] to avoid string concatenation
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
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
- pass TrieNode

LeetCode 395 - Longest Substring with At Least K Repeating Characters
- split by badChars and dfs

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

LeetCode124 - Word Search
find if the word exists in the grid

LeetCode 22 – Generate Parentheses
generate all combinations of well-formed parentheses.
helper(List res, StringBuilder sb, int open, int close, int n)
-- dfs(ArrayList<String> result, String s, int left, int right)
helper(int n, List<String>[] lists)

f(n) = (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0)

LeetCode 320 - Generalized Abbreviation
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

X. Divide and Conquer
- subproblems
LeetCode 50 - Pow(x, n)
Google – Power Sum
return sum of n^0 + n^1 + … + n^n.

X. merge sort
need one extra array - no need to create tmp array every time
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

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
(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
countMap, curMap, foundCount,
toFindMap, foundMap
2. trie

LeetCode 3 - Longest Substring Without Repeating Characters
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
follow up - stream

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).
Map<Character, Integer> needToFill, hasFound

X. Two pointers
- presort, O(N^2)
- how to avoid duplicate results

3Sum Smaller
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];
2. 32n
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

LeetCode 287 - Find the Duplicate Number
1. nlogn - binary search/bisection
2. O(n)
- graph: index -> as graph
- find cycle in linkedlist
3. 32n

LeetCode 410 - Split Array Largest Sum
minimize the largest sum among these m subarrays.
bisection -

LeetCode 287 - Find the Duplicate Number
1. bisection - long*n
2. O(n)
- index->value graph subproblem
- find cycle in linkedlist

LintCode - Copy Books
Divide A into k or fewer partitions, such that the maximum sum over all the partitions is minimized.
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)

Codility: Lesson 12 Min Max Division
int left = max, right = sum;

kth sum pairs from array a and b

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
class TreeNode{
    int smallerCount;
    int val;
    TreeNode left;
    TreeNode right;
2. Merge sort
class Tuple {
    public int val;
    public int idx;
3. Use TreeSet

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;

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());
pq = new PriorityQueue<>((a, b) -> (b - a));

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

LeetCode 435 - Non-overlapping Intervals
- sort interval by end

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

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

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

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

X. Stack
LeetCode 456 - 132 Pattern
Stack to maintain min-max: max after min till current element

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

X. Union Find
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
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
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
- build graph
visited[i] = -1. Not even exist.
visited[i] = 0. Exist. Non-visited.
visited[i] = 1. Visiting.
visited[i] = 2. Visited.

LeetCode 444 - Sequence Reconstruction
- 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
public List<String> findItinerary(String[][] tickets) {
    for (String[] ticket : tickets)
        targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
    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())
    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
- 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.

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
Queue<TreeNode>, boolean leftToRight = !leftToRight;
if(leftToRight) levelNodes.add(n.val); else levelNodes.addFirst(n.val);
x. dfs -
ArrayList<LinkedList<Integer>> result
x. 2 stacks
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
- 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 -

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

X. Random
LeetCode 398 - Random Pick Index
if (rnd.nextInt(++count) == 0) result = i;

X. Misc
LeetCode 158 - Read N Characters Given Read4 II

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]
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
int i = Collections.binarySearch(dp, num);
dp.set((i<0) ? -i-1 : i, num);
-- O(nlogn)
2. DP O(N^2)

HashMap<Integer, ArrayList<Pair>> hashMap

LeetCode 454 - 4Sum II

Leetcode 370 - Range Addition
res[start] += value;
res[end+1] -= value;

LeetCode 406 - Queue Reconstruction by Height
1. sort + insert: by height then index

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

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

-- Node to Node Binary Tree Path


adsense (5) Algorithm (69) Algorithm Series (35) Android (6) ANT (6) bat (8) Big Data (7) Blogger (14) Cache (5) Chrome (18) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (62) Eclipse (32) Git (5) Google (28) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (182) 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 (16) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)