Thursday, July 7, 2016

LeetCode 373 - Find K Pairs with Smallest Sums


http://bookshadow.com/weblog/2016/07/07/leetcode-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.
Example 1:
Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:
Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2

Return: [1,1],[1,1]

The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:
Given nums1 = [1,2], nums2 = [3],  k = 3 

Return: [1,3],[2,3]

All possible pairs are returned from the sequence:
[1,3],[2,3]
给定两个递增有序的整数数组nums1和nums2,以及一个整数k。
定义一个数对(u, v),包含第一个数组中的一个元素以及第二个数组中的一个元素。
寻找和最小的k个这样的数对(u1,v1),(u2,v2) ...(uk,vk)。
https://discuss.leetcode.com/topic/50450/slow-1-liner-to-fast-solutions
X. Use Priority Queue  O(KlogK)
http://www.cnblogs.com/grandyang/p/5653127.html
这种方法我们从0循环到数组的个数和k之间的较小值,这样做的好处是如果k远小于数组个数时,我们不需要计算所有的数字对,而是最多计算k*k个数字对,然后将其都保存在res里,这时候我们给res排序,用我们自定义的比较器,就是和的比较,然后把比k多出的数字对删掉即可

https://discuss.leetcode.com/topic/50885/simple-java-o-klogk-solution-with-explanation
https://discuss.leetcode.com/topic/50529/java-9ms-heap-queue-solution-k-log-k
Basic idea: Use min_heap to keep track on next minimum pair sum, and we only need to maintain K possible candidates in the data structure.
Some observations: For every numbers in nums1, its best partner(yields min sum) always strats from nums2[0] since arrays are all sorted; And for a specific number in nums1, its next candidate sould be [this specific number] + nums2[current_associated_index + 1], unless out of boundary;)
Here is a simple example demonstrate how this algorithm works.
image
The run time complexity is O(kLogk) since que.size <= k and we do at most k loop.
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> que = new PriorityQueue<>((a,b)->a[0]+a[1]-b[0]-b[1]);
        List<int[]> res = new ArrayList<>();
        if(nums1.length==0 || nums2.length==0 || k==0) return res;
        for(int i=0; i<nums1.length && i<k; i++) que.offer(new int[]{nums1[i], nums2[0], 0});
        while(k-- > 0 && !que.isEmpty()){
            int[] cur = que.poll();
            res.add(new int[]{cur[0], cur[1]});
            if(cur[2] == nums2.length-1) continue;
            que.offer(new int[]{cur[0],nums2[cur[2]+1], cur[2]+1});
        }
        return res;
    }
https://segmentfault.com/a/1190000008309330
greedy: 先把一组x里面和另外一组y最小元素的组合放进heap,然后每次poll出和最小的,同时放进去有可能成为第二小的组合,即当前y元素的下一个和x元素的组合。
https://discuss.leetcode.com/topic/51163/java-priorityqueue-9ms-without-helper-class
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> res = new LinkedList<>();
        if(nums1==null || nums1.length==0 || nums2==null || nums2.length==0) {
            return res;
        }
        
        // index pair
        PriorityQueue<int[]> minQ = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] pair1, int[] pair2) {
                return (nums1[pair1[0]]+nums2[pair1[1]])-(nums1[pair2[0]]+nums2[pair2[1]]);
            }
            
        });
        
        
        minQ.offer(new int[]{0, 0});
        
        while (k>0 && !minQ.isEmpty()) {
            int[] pair=minQ.poll();
            int i = pair[0];
            int j = pair[1];
            res.add(new int[]{nums1[i], nums2[j]});
            k--;
            
            if(j+1<nums2.length) {
                minQ.offer(new int[]{i, j+1});
            }
            
            if(j==0 && i+1<nums1.length){ 
                minQ.offer(new int[] {i+1, 0}); //\\
            }

        }
        
        
        return res;
    }
X. O(k) solution
https://discuss.leetcode.com/topic/50647/9ms-java-solution-with-explanation/2
https://discuss.leetcode.com/topic/52953/share-my-solution-which-beat-96-42
the basic idea is using a priority queue to store the candidates and pop them out in ascending order.
But, actually you don't need to store all of the pairs at the beginning, do you?
Imagine a matrix:
a1 a2 a3
a4 a5 a6
a7 a8 a9
The number in m[i][j] refers to the sum of nums1[i] + nums[j].
When you pop the value in m[0][1] (which is "a2"), actually you only need to put candidates m[1][1] ("a3") and m[0][2] ("a5") to the queue. And at this moment you don't need to care any other candidate.
In this way, the priority queue can be quite short comparing to putting all the pairs in the beginning.
Ok, now is there any thing you need to pay attention to? Yes, please notice there might be duplicates.
"a2" will lead to "a3" and "a5", while "a4" will lead to "a5" and "a7", thus "a5" will be a dup.
How to handle this?
I don't have a very good solution. my current one is to add the first column at the beginning, then each time you pop one item, you just add the one on the right and ignore the one below (since it will be someone else's right unless it's in the first column).
use a matrix to represent all combination of pairs from nums1 and nums2. Do a bfs from [0][0]. However, use a PriorityQueue instead of regular queue.

assuming nums1.length == nums2.length == n. time complexity should be klogn. The PQ's maximum size should be a linear function of n, not n^2. Image it is a regular bfs using a queue. The maximum size of PQ happens when all elements are along the diagonal line of matrix, which is sqrt2*n.

-- Uses too much space: visited[][] - use HashSet

    final int[][] neighbors = {{0, 1}, {1, 0}};
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> list = new ArrayList<>();
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0 || k == 0) {
            return list;
        }
        int m = nums1.length, n = nums2.length;
        boolean[][] visited = new boolean[m][n];
        Queue<Pair> minHeap = new PriorityQueue<>();
        minHeap.offer(new Pair(0, 0, nums1[0] + nums2[0]));
        visited[0][0] = true;
        while (k > 0 && !minHeap.isEmpty()) {
            Pair min = minHeap.poll();
            list.add(new int[] {nums1[min.row], nums2[min.col]});
            k--;
            for (int[] neighbor : neighbors) {
                int row1 = min.row + neighbor[0];
                int col1 = min.col + neighbor[1];
                if (row1 < 0 || row1 == m || col1 < 0 || col1 == n || visited[row1][col1]) {
                    continue;
                }
                visited[row1][col1] = true;
                minHeap.offer(new Pair(row1, col1, nums1[row1] + nums2[col1]));
            }
        }
        return list;
    }
}

class Pair implements Comparable<Pair> {
    int row;
    int col;
    int value;
    
    Pair(int row, int col, int value) {
        this.row = row;
        this.col = col;
        this.value = value;
    }
    
    public int compareTo(Pair other) {
        return value - other.value;
    } 
}

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) 
{
        List<int[]> result = new LinkedList<int[]>();
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0 || k == 0) return result;
        
        PriorityQueue<Triple> queue = new PriorityQueue<Triple>(nums1.length, new Comparator<Triple>() {
            public int compare(Triple a, Triple b)
            {
                return Integer.compare(a.val, b.val);
            }
        });

// add the first column
        for (int i=0; i<nums1.length; i++)
        {
            queue.add(new Triple(nums1[i]+nums2[0], i, 0));
        }
        
        while (k-- > 0 && !queue.isEmpty())
        {
            Triple current = queue.poll();
            result.add(new int[]{nums1[current.one], nums2[current.two]});
// if the current one has a right candidate, add it to the queue. 
            if (current.two+1 < nums2.length)
                queue.add(new Triple(nums1[current.one]+nums2[current.two+1], current.one, current.two+1));
        }
        
        return result;
}
    
// Triple is used to store the sum, the index in nums1 and the index in nums2.
    class Triple
    {
        int val;
        int one;
        int two;
        Triple (int val, int one, int two)
        {
            this.val = val;
            this.one = one;
            this.two = two;
        }
    }
To get the idea clear, you can think that this is the problem to merge k sorted arrays.
array1 = (0,0),(0,1),(0,2),....
array2 = (1,0),(1,1),(1,2),....
....
arrayk = (k-1,0),(k-1,1),(k-1,2),....
So, each time when an array is chosen having the smallest sum, you only move its index to next one of this array.
https://discuss.leetcode.com/topic/53380/o-k-solution
Now that I can find the kth smallest element in a sorted n×n matrix in time O(min(n, k)), I can finally solve this problem in O(k).
The idea:
  1. If nums1 or nums2 are larger than k, shrink them to size k.
  2. Build a virtual matrix of the pair sums, i.e., matrix[i][j] = nums1[i] + nums2[j]. Make it a square matrix by padding with "infinity" if necessary. With "virtual" I mean its entries will be computed on the fly, and only those that are needed. This is necessary to stay within O(k) time.
  3. Find the kth smallest sum kthSum by using that other algorithm.
  4. Use a saddleback search variation to discount the pairs with sum smaller than kthSum. After this, k tells how many pairs we need whose sum equals kthSum.
  5. Collect all pairs with sum smaller than kthSum as well as k pairs whose sum equals kthSum.
Each of those steps only takes O(k) time.

The code (minus the code for kthSmallest, which you can copy verbatim from my solution to the other problem):
Thanks to @zhiqing_xiao for pointing out that my previous way of capping the input lists might not be O(k). It was this:
def kSmallestPairs(self, nums1, nums2, k):
    del nums1[k:]
    del nums2[k:]
    def kSmallestPairs(self, nums1_, nums2_, k):

        # Use at most the first k of each, then get the sizes.
        nums1 = nums1_[:k]
        nums2 = nums2_[:k]
        m, n = len(nums1), len(nums2)

        # Gotta Catch 'Em All?
        if k >= m * n:
            return [[a, b] for a in nums1 for b in nums2]
        
        # Build a virtual matrix.
        N, inf = max(m, n), float('inf')
        class Row:
            def __init__(self, i):
                self.i = i
            def __getitem__(self, j):
                return nums1[self.i] + nums2[j] if self.i < m and j < n else inf
        matrix = map(Row, range(N))

        # Get the k-th sum.
        kthSum = self.kthSmallest(matrix, k)

        # Discount the pairs with sum smaller than the k-th.
        j = min(k, n)
        for a in nums1:
            while j and a + nums2[j-1] >= kthSum:
                j -= 1
            k -= j

        # Collect and return the pairs.
        pairs = []
        for a in nums1:
            for b in nums2:
                if a + b >= kthSum + (k > 0):
                    break
                pairs.append([a, b])
                k -= a + b == kthSum
        return pairs

    def kthSmallest(self, matrix, k):
        
        # copy & paste from https://discuss.leetcode.com/topic/53126/o-n-from-paper-yes-o-rows

X. O(KlogK)
Don't use PQ
https://discuss.leetcode.com/topic/50527/java-10ms-solution-no-priority-queue
https://discuss.leetcode.com/topic/50632/java-priority-queue-or-without-priority-queue
  1. With Priority Queue. Scan [k+1, 2K] pair. Heap size is [2, k]. O(klogk) time, O(k) space
  2. Without Priority Queue. O(N^2) time, O(1) space
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
      List<int[]> sPairs = new ArrayList<>();
      if (nums1 == null || nums1.length == 0 || nums2 == null
              || nums2.length == 0 || k == 0) return sPairs;

      int len1 = nums1.length, len2 = nums2.length;
      int[] nums2idx = new int[len1]; // map to last used element in nums2
      while (sPairs.size() < k) {
        int minSoFar = Integer.MAX_VALUE;
        int nums1pos = -1;
        // find smallest pair
        for (int i = 0; i < len1; i++) {
          if (nums2idx[i] >= len2) {
            continue;
          }
          if (nums1[i] + nums2[nums2idx[i]] <= minSoFar) {
            minSoFar = nums1[i] + nums2[nums2idx[i]];
            nums1pos = i;
          }
        }

        if (nums1pos == -1) {
          break;
        }

        sPairs.add(new int[]{nums1[nums1pos], nums2[nums2idx[nums1pos]]});
        nums2idx[nums1pos]++;
      }

      return sPairs;
    }

http://blog.csdn.net/yeqiuzs/article/details/51851359
用最小堆保存遍历过程中的pairs。
当遍历到(i,j)时,继续往下遍历,相邻的结点是(i+1,j),(i,j+1) 
因为是有序数组,这两个pair是较小的,加入堆中。
 public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
  List<int[]> res = new ArrayList<int[]>();
  boolean visit[][] = new boolean[nums1.length][nums2.length];
  Queue<int[]> heap = new PriorityQueue<int[]>(new Comparator<int[]>(){
   public int compare(int[] i, int[] j) {
    return (nums1[i[0]] + nums2[i[1]] -( nums1[j[0]] + nums2[j[1]]));
   }
  });

  heap.add(new int[] { 0, 0 });
  visit[0][0] = true;

  while (!heap.isEmpty() && res.size() < k) {
   int d[] = heap.poll();
   res.add(new int[] { nums1[d[0]], nums2[d[1]] });

   if (d[1] + 1 < nums2.length && visit[d[0]][d[1] + 1] == false) {
    heap.add(new int[] { d[0], d[1] + 1 });
    visit[d[0]][d[1] + 1] = true;
   }
   if (d[0] + 1 < nums1.length && visit[d[0]+1][d[1]] == false) {
    heap.add(new int[] { d[0]+1, d[1]});
    visit[d[0]+1][d[1]] = true;
   }
  }
  return res;
 }
https://www.hrwhisper.me/leetcode-find-k-pairs-smallest-sums/
最直接的思路是把全部的数都组合一下,然后维护一个大小为k的最大堆 这样复杂度O(m*n*logk)
其实还可以维护一个最小堆,每次取出堆顶的元素,然后把该元素相邻结点加入进去。这样能保证最小。
struct Order {
int sum;
int index1, index2;
Order(int a, int b, int sum) : index1(a), index2(b), sum(sum) {}
bool operator < (const Order& b) const {
return sum > b.sum;
}
};
int dx[] = { 1,0 };
int dy[] = { 0,1 };
class Solution {
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int, int>> ans;
if (nums1.empty() || nums2.empty()) return ans;
int n = nums1.size(), m = nums2.size();
vector<vector<bool>> vis(n, vector<bool>(m, false));
priority_queue<Order> q;
q.push(Order(0, 0, nums1[0] + nums1[1]));
vis[0][0] = true;
while (k > 0 && !q.empty()) {
Order cur = q.top();
q.pop();
k--;
int x = cur.index1, y = cur.index2;
ans.push_back(make_pair(nums1[x], nums2[y]));
for (int i = 0; i < 2; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < n && ny < m && !vis[nx][ny]) {
q.push(Order(nx, ny, nums1[nx] + nums2[ny]));
vis[nx][ny] = true;
}
}
}
return ans;
}
};
http://www.2cto.com/px/201607/524030.html
 public List kSmallestPairs(int[] nums1, int[] nums2, int k) {
  List res = new ArrayList();
  boolean visit[][] = new boolean[nums1.length][nums2.length];
  Queue heap = new PriorityQueue(new Comparator(){
   public int compare(int[] i, int[] j) {
    return (nums1[i[0]] + nums2[i[1]] -( nums1[j[0]] + nums2[j[1]]));
   }
  });

  heap.add(new int[] { 0, 0 });
  visit[0][0] = true;

  while (!heap.isEmpty() && res.size() < k) {
   int d[] = heap.poll();
   res.add(new int[] { nums1[d[0]], nums2[d[1]] });

   if (d[1] + 1 < nums2.length && visit[d[0]][d[1] + 1] == false) {
    heap.add(new int[] { d[0], d[1] + 1 });
    visit[d[0]][d[1] + 1] = true;
   }
   if (d[0] + 1 < nums1.length && visit[d[0]+1][d[1]] == false) {
    heap.add(new int[] { d[0]+1, d[1]});
    visit[d[0]+1][d[1]] = true;
   }
  }
  return res;
 }


def kSmallestPairs(self, nums1, nums2, k): queue = [] def push(i, j): if i < len(nums1) and j < len(nums2): heapq.heappush(queue, [nums1[i] + nums2[j], i, j]) push(0, 0) pairs = [] while queue and len(pairs) < k: _, i, j = heapq.heappop(queue) pairs.append([nums1[i], nums2[j]]) push(i, j + 1) if j == 0: push(i + 1, 0) return pairs

http://www.programcreek.com/2015/07/leetcode-find-k-pairs-with-smallest-sums-java/
This problem is similar to Super Ugly Number. The basic idea is using an array to track the index of the next element in the other array.
The best way to understand this solution is using an example such as nums1={1,3,11} and nums2={2,4,8}.
http://blog.csdn.net/qq508618087/article/details/51864835
这种思想有点像寻找第k个丑数, 记录一下nums1中每个数对应nums2中组合的位置. 然后每次找到能够产生最小的组合即可.
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<int[]> result = new ArrayList<int[]>();
 
    k = Math.min(k, nums1.length*nums2.length);
 
    if(k==0)
        return result;
 
    int[] idx = new int[nums1.length];
 
    while(k>0){
        int min = Integer.MAX_VALUE;
        int t=0;
        for(int i=0; i<nums1.length; i++){
            if(idx[i]<nums2.length && nums1[i]+nums2[idx[i]]<min){
                t=i;
                min = nums1[i]+nums2[idx[i]];
            }
        }
 
        int[] arr = {nums1[t], nums2[idx[t]]};    
        result.add(arr);
 
        idx[t]++;
 
        k--;
    }
 
    return result;
}
X. https://discuss.leetcode.com/topic/50527/java-10ms-solution-no-priority-queue/2 TODO
Because both array are sorted, so we can keep track of the paired index. Therefore, we do not need to go through all combinations when k < nums1.length + num2.length. Time complexity is O(k*m) where m is the length of the shorter array.
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> ret = new ArrayList<int[]>();
        if (nums1.length == 0 || nums2.length == 0 || k == 0) {
            return ret;
        }
        
        int[] index = new int[nums1.length];
        while (k-- > 0) {
            int min_val = Integer.MAX_VALUE;
            int in = -1;
            for (int i = 0; i < nums1.length; i++) {
                if (index[i] >= nums2.length) {
                    continue;
                }
                if (nums1[i] + nums2[index[i]] < min_val) {
                    min_val = nums1[i] + nums2[index[i]];
                    in = i;
                }
            }
            if (in == -1) {
                break;
            }
            int[] temp = {nums1[in], nums2[index[in]]};
            ret.add(temp);
            index[in]++;
        }
        return ret;
    }
public class Solution
 {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int len1=nums1.length, len2=nums2.length;
        int[] step= new int[len1];
        List<int[]> res= new ArrayList<int[]>();
        
        //记录一下从nums1到nums2的步数
        for(int i=0; i<Math.min(k,len1*len2); i++)
        {
            int min=Integer.MAX_VALUE;
            for(int a=0; a<len1; a++)
            {
                if(step[a]>=len2) continue;
                min=Math.min(min, nums1[a]+nums2[step[a]]);
            }
            for(int a=0; a<len1; a++)
            {
                if(step[a]>=len2) continue;
                if(nums1[a]+nums2[step[a]]==min)
                {
                    res.add(new int[]{nums1[a], nums2[step[a]]});
                    step[a]++;
                    break;
                }
            }
        }
        return res;
    }
}
X. Brute Force
http://www.cnblogs.com/grandyang/p/5653127.html
https://discuss.leetcode.com/topic/50514/java-brute-force-solution-with-priorityqueue-150ms
Time Complexity: O(mnlogK)
Space: O(K)
    public class Pair{
        int i1;
        int i2;
        int sum;
        public Pair(int sum, int i1, int i2){
            this.sum = sum;
            this.i1 = i1;
            this.i2 = i2;
        }
    }
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> result = new ArrayList<>();
        if(nums1 == null || nums2 == null) return result;
        int len1 = nums1.length, len2 = nums2.length;

        PriorityQueue<Pair> pq = new PriorityQueue<>((p1, p2) -> p2.sum - p1.sum);
        for(int i = 0; i < len1; i++){
            for(int j = 0; j < len2; j++){
                int sum = nums1[i] + nums2[j];
                if(pq.size() < k)
                    pq.offer(new Pair(sum, i, j));
                else if (sum < pq.peek().sum) {
                    pq.poll();
                    pq.offer(new Pair(sum, i, j));
                }
            }
        }
        
        while(!pq.isEmpty()){
            Pair p = pq.poll();
            result.add(0, new int[]{nums1[p.i1], nums2[p.i2]});
        }
        
        return result;
            
    }
}

    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int>> res;
        for (int i = 0; i < min((int)nums1.size(), k); ++i) {
            for (int j = 0; j < min((int)nums2.size(), k); ++j) {
                res.push_back({nums1[i], nums2[j]});
            }
        }
        sort(res.begin(), res.end(), [](pair<int, int> &a, pair<int, int> &b){return a.first + a.second < b.first + b.second;});
        if (res.size() > k) res.erase(res.begin() + k, res.end());
        return res;
    }

http://www.voidcn.com/blog/niuooniuoo/article/p-6091497.html
https://discuss.leetcode.com/topic/50450/slow-1-liner-to-fast-solutions
TODO
https://discuss.leetcode.com/topic/53126/o-n-from-paper-yes-o-rows

No comments:

Post a Comment

Labels

GeeksforGeeks (1107) LeetCode (993) Algorithm (795) Review (766) to-do (633) LeetCode - Review (514) Classic Algorithm (324) Dynamic Programming (293) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Different Solutions (120) Bit Algorithms (118) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (107) HackerRank (89) Binary Tree (82) Binary Search (81) Graph Algorithm (74) Greedy Algorithm (72) DFS (67) LeetCode - Extended (62) Interview Corner (61) Stack (60) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (48) Binary Search Tree (46) USACO (46) Trie (45) Mathematical Algorithm (42) ACM-ICPC (41) Interval (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) LeetCode Hard (39) Recursive Algorithm (39) Matrix (38) String Algorithm (38) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Union-Find (34) Array (33) prismoskills (33) Segment Tree (32) Sliding Window (32) Data Structure Design (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Microsoft 100 - July (28) Palindrome (28) to-do-must (28) Priority Queue (27) Random (27) Graph (26) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) Post-Order Traverse (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) Binary Indexed Trees (21) DFS + Review (21) Lintcode - Review (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Merge Sort (20) O(N) (20) Follow Up (19) Time Complexity (19) Two Pointers (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) KMP (13) Long Increasing Sequence(LIS) (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) Reverse Thinking (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Miscs (11) Princeton (11) Proof (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) Facebook Hacker Cup (10) HackerRank Easy (10) O(1) Space (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) DP-Multiple Relation (9) DP-Space Optimization (9) Divide and Conquer (9) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stack Overflow (9) Stock (9) System Design (9) TreeMap (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) LeetCode - DP (8) Left and Right Array (8) Linked List (8) Longest Common Subsequence(LCS) (8) Prime (8) Suffix Tree (8) Tech-Queries (8) Traversal Once (8) 穷竭搜索 (8) Algorithm Problem List (7) Expression (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Inversion (7) Kadane’s Algorithm (7) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) DP-Print Solution (6) Dijkstra (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Manacher (6) Minimum Spanning Tree (6) Morris Traversal (6) Multiple Data Structures (6) One Pass (6) Programming Pearls (6) Pruning (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) TreeSet (6) Xpost (6) reddit (6) AI (5) Algorithm - Brain Teaser (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) Cycle (5) DP-Include vs Exclude (5) Fast Slow Pointers (5) Find Rule (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Maze (5) Microsoft Interview (5) Pre-Sum (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) LeetCode - Recursive (4) LeetCode - TODO (4) MST (4) MinMax (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Probability (4) Programcreek (4) Spell Checker (4) Stock Maximize (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Algorithm - How To (3) Algorithm Design (3) B Tree (3) Big Data Algorithm (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Finite Automata (3) Github (3) GoLang (3) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) K (3) Knapsack-多重背包 (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) O(N) Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Stack - Smart (3) State Machine (3) Subtree (3) Transform Tree (3) Trie + DFS (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Ladder (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binary Search - Smart (2) Binomial Coefficient (2) Bit Counting (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Company-Snapchat (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) Edit Distance (2) Factor (2) Forward && Backward Scan (2) GoHired (2) Graham Scan (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Power (2) Median (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Regular Expression (2) Return Multiple Values (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Tree Without Tree Predefined (2) Word Break (2) Word Graph (2) Word Trie (2) Yahoo Interview (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Augmented BST (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Sarch Tree (1) Binary String (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Cloest (1) Clone (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Cont Improvement (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Diagonal (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Machine Learning (1) Maintain State (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-End BFS (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Element (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) PreProcess (1) Probabilistic Data Structure (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) Square (1) Streaming Algorithm (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Virtual Matrix (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts