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

https://discuss.leetcode.com/topic/50885/simple-java-o-klogk-solution-with-explanation
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://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).
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/50435/java-easy-understandable-bfs-with-priorityqueue
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[][]

    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;
    } 
}
X. O(k) solution
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. 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

No comments:

Post a Comment

Labels

GeeksforGeeks (959) Algorithm (811) LeetCode (630) to-do (595) Classic Algorithm (334) Review (327) Classic Interview (299) Dynamic Programming (262) Google Interview (224) LeetCode - Review (224) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (118) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Interview Corner (61) Greedy Algorithm (59) List (58) Binary Tree (56) DFS (54) Algorithm Interview (53) Codility (52) ComProGuide (52) Advanced Data Structure (51) LeetCode - Extended (47) USACO (46) Geometry Algorithm (44) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Interval (38) Jobdu (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Array (33) prismoskills (33) Segment Tree (32) Space Optimization (32) Trie (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (26) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Queue (22) DFS + Review (21) Hash (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Follow Up (15) Iterator (15) Merge Sort (15) O(N) (15) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Bisection Method (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Divide and Conquer (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) System Design (8) Tech-Queries (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Suffix Tree (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) Time Complexity (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Kadane’s Algorithm (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (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) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quadtrees (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Sweep Line (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (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) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (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) Binomial Coefficient (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) 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) GoHired (2) Graham Scan (2) Graph - Bipartite (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) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Master Theorem (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (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 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) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (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) 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 - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (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) 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) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (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) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (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) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (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) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (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