LeetCode 435 - Non-overlapping Intervals


http://bookshadow.com/weblog/2016/10/30/leetcode-non-overlapping-intervals/
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:
  1. You may assume the interval's end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
https://zhuanlan.zhihu.com/p/26657786
简单的逻辑就是,当有两个interval相互重叠的时候,我们一定要删去一个。那么删去哪一个呢?答案是删去end比较大的那个。这个可以用prove by contradiction轻松证明
http://www.cnblogs.com/grandyang/p/6017505.html
这道题给了我们一堆区间,让我们求需要至少移除多少个区间才能使剩下的区间没有重叠,那么我们首先要给区间排序,根据每个区间的start来做升序排序,然后我们开始要查找重叠区间,判断方法是看如果前一个区间的end大于后一个区间的start,那么一定是重复区间,此时我们结果res自增1,我们需要删除一个,那么此时我们究竟该删哪一个呢,为了保证我们总体去掉的区间数最小,我们去掉那个end值较大的区间,而在代码中,我们并没有真正的删掉某一个区间,而是用一个变量last指向上一个需要比较的区间,我们将last指向end值较小的那个区间;如果两个区间没有重叠,那么此时last指向当前区间,继续进行下一次遍历
    int eraseOverlapIntervals(vector<Interval>& intervals) {
        int res = 0, n = intervals.size(), last = 0;
        sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b){return a.start < b.start;});
        for (int i = 1; i < n; ++i) {
            if (intervals[i].start < intervals[last].end) {
                ++res;
                if (intervals[i].end < intervals[last].end) last = i;
            } else {
                last = i;
            }
        }
        return res;
    }
https://leetcode.com/problems/non-overlapping-intervals/discuss/91713/Java%3A-Least-is-Most
Actually, the problem is the same as "Given a collection of intervals, find the maximum number of intervals that are non-overlapping." (the classic Greedy problem: Interval Scheduling). With the solution to that problem, guess how do we get the minimum number of intervals to remove? : )
Sorting Interval.end in ascending order is O(nlogn), then traverse intervals array to get the maximum number of non-overlapping intervals is O(n). Total is O(nlogn).
Actually, the problem is the same as "Given a collection of intervals, find the maximum number of intervals that are non-overlapping." (the classic Greedy problem: Interval Scheduling). With the solution to that problem, guess how do we get the minimum number of intervals to remove? : )
X. Sort by end
为了知道有哪些是重叠的,我们先给所有的间隔排个序,这样就可以一个一个地看是否有重叠,间隔排序不像数字排序那么直接,需要自己进行定义,到底是比end的大小还是比start的大小呢?我们选择比end,如果比start,有可能一个start更小但范围很大的间隔,却包含了后面好几个start更大但是范围很小的间隔,而比end就没有这个问题,end基本就限制了你的范围。

那么比较end如果相同,还需要判断start吗?其实不需要了,对于同一个end值的两个间隔,无论我们留哪一个(只要能留,也就是说只要范围没重叠),另一个都一定会被抛弃,且对后续的间隔没有任何影响。

排序我们就可以遍历间隔数组,比较后一个间隔的start是否大于前一个的end,大于则无重叠,我们就留下来,否则就抛弃掉。最后得出抛弃掉的数量就可以

Do you know why sort by end time instead of by start time?
[ [1,4], [2,3], [3,4] ], the interval with early start might be very long and incompatible with many intervals. But if we choose the interval that ends early, we'll have more space left to accommodate more intervals.
  1. Sort Intervals by end.
  2. Count valid intervals (non-overlapping).
  3. Answer is len - count
    public int eraseOverlapIntervals(Interval[] intervals) {
        
        if(intervals.length == 0)  return 0;
        
        Arrays.sort(intervals, new myComparator());
        int end = intervals[0].end;
        int count = 1;
        
        for(int i = 0; i < intervals.length; i++) {
            
            if(intervals[i].start >= end) {
                end = intervals[i].end;
                count++;
            }
        }
        
        return intervals.length - count;
    }
    
    class myComparator implements Comparator<Interval> {
        
        public int compare(Interval a, Interval b) {
            return a.end - b.end;
        }
    }
http://blog.csdn.net/mebiuw/article/details/53054380
1、按照起始位置排序 
2、按照顺序,两个指针遍历,一前一后,如果当前位置和上一个位置不冲突就顺序平移两个指针(后指针的值给前指针,然后后指针移动到下一位),如果冲突的话,那么前指针则变成当前两个指针当中覆盖最小的一个(贪心所在),后指针移动到下一个位置就好
public int eraseOverlapIntervals(Interval[] intervals) { // 按照起始位置进行排序 Arrays.sort(intervals,(x,y)->(x.start)-(y.start)); int count=0,j=0; // 贪心法,如果上一个位置j和当前位置i冲突了,那么进行判断,
如果当前位置的末尾小于上一个边界的末尾,那么删除上一个位置
(因为覆盖的更少,每步选择最有可能不造成重复的),反之如果当前位置尾部覆盖的更多,
那么就删除i的位置。删除的方式通过控制j的取值进行 for(int i=1;i<intervals.length;i++) { if(intervals[j].end>intervals[i].start){ j=intervals[i].end<intervals[j].end?i:j; count++; }else //没有重复 j=i; } return count; }

https://discuss.leetcode.com/topic/65828/java-solution-with-clear-explain
First we sort the array by below rules
  • 1) sort by end, smaller end in front
  • 2) if end is same, sort by start, bigger start in front
Then, visited array by end. If we visited next closest end interval, access the bigger start priority.
when end is same, the bigger start one has greater possibility of convergence. So we can put those front. Actually, we only sort by end is ok, like below
Arrays.sort(intervals, new Comparator<Interval>() {
    @Override
    public int compare(Interval o1, Interval o2) {
        return o1.end - o2.end;  //only sort by end
    }
});
public int eraseOverlapIntervals(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.end != o2.end) return o1.end - o2.end;  //first sort by end
                return o2.start - o1.start;  //second sort by start
            }
        });

        int end = Integer.MIN_VALUE;
        int count = 0;
        for (Interval interval : intervals) {
            if (interval.start >= end) end = interval.end;
            else count++;
        }

        return count;
    }
贪心算法(Greedy Algorithm)
优先按照终点,然后按照起点从小到大排序
利用变量end记录当前的区间终点,end初始化为负无穷
遍历排序后的区间,若当前区间的起点≥end,则更新end为当前区间的终点,并将计数器ans+1
ans为可以两两互不相交的最大区间数,len(intervals) - ans即为答案
def eraseOverlapIntervals(self, intervals): """ :type intervals: List[Interval] :rtype: int """ invs = sorted((x.end, x.start) for x in intervals) end = -0x7FFFFFFF ans = 0 for e, s in invs: if s >= end: end = e ans += 1 return len(intervals) - ans
X. Sort by start
https://blog.csdn.net/fuxuemingzhu/article/details/82728387
看到区间最值题一般想到排序+贪心。这个题和452. Minimum Number of Arrows to Burst Balloons挺相似。

这个题的做法也不难,这么思考:我们尽量移除那些覆盖最广的区间。

先对所有区间的起点进行排序,然后进行遍历,如果新的区间起点比老的区间终点小的话,说明有重叠,需要移除区间,移除哪个区间呢?当然是终点最靠后的终点。

我们使用last指针指向上个保留下来的节点,如果intervals[i].end < intervals[last].end,则代表新的区间终点更靠前,所以使用第i个节点代表last,也就是说移除了上面的那个last。然后统计移除了多少次区间即可。

https://zhuhan0.blogspot.com/2017/03/leetcode-non-overlapping-intervals.html
The idea is to sort the array based on the intervals start points and use a greedy approach.

After the array is sorted, iterate through the array and use a local variable "end" to keep track of the smallest end point of current overlapping intervals. The reason is that we want to delete all overlapping intervals except the one that has the smallest end point, so that the next interval won't overlap with it.

Once we iterate through a group of overlapping intervals, we update "end" to be the end point of the next interval.
    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals.length < 2) {
            return 0;
        }
        
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });
        
        int end = intervals[0].end;
        int min = 0;
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < end) {
                end = Math.min(end, intervals[i].end);
                min++;
            } else {
                end = intervals[i].end;
            }
        }
        
        return min;
    }
https://discuss.leetcode.com/topic/66200/simple-solution
  1. Order intervals by start point.
  2. Record the end of the last valid interval.
  3. For each interval, if is start point is >= the end of the last valid interval, increment the count of valid intervals, and move the end point to the end of the current interval. Otherwise just set the new end point to the minimum between the two overlapping intervals.
  4. Return the difference between the number of intervals in the input array and the number of valid intervals you found in the previous way.
public int eraseOverlapIntervals(Interval[] intervals) {
 if(intervals==null || intervals.length==0) return 0;
 Arrays.sort(intervals, new Comparator<Interval>() {
  public int compare(Interval i1, Interval i2) {
   return i1.start-i2.start;
  }
 });
 int count=1;
 int lastEnd = intervals[0].end;
 for(int i=1;i<intervals.length;i++) {
  Interval currentInterval = intervals[i];
  if(currentInterval.start>=lastEnd) {
   count++;
   lastEnd=currentInterval.end;
  } else {
   lastEnd=Math.min(currentInterval.end,lastEnd);
  }
 }
 return intervals.length-count;
}

https://hintpine.wordpress.com/2016/10/31/leetcode-non-overlapping-intervals/
First, let’s define solution to be a group who has maximum non-overlapping intervals, and the intervals are sorted by end values. There might be multiple solutions to the input. For example, if the input is [[1,2], [1,3], [5,6]], there are two solutions, [[1,2], [5,6]] and [[1,3], [5,6]].
Now, sort the intervals by end values. Then, we can say the first interval must belong to some solution.
Proof:
Suppose the first interval, name it A, does not belong to any solution. Then, use B to denote the first interval of solution. It must be either one of following cases:
  1. B is non-overlapping with A. In this case, A can be safely inserted before B to form a new solution.
  2. B is overlapping with A. Because all other intervals of the solution don’t overlap with B, we can safely replace B with A to form a new solution.
So, both cases contradict the assumption. Thus, A must belong to some solution. Q.E.D.
Since A is fixed, in that solution all those intervals who overlap with A definitely don’t belong to the solution. So, we can safely remove those intervals until an interval whose start value is greater than or equal to A’s end value. Then, as proven, we can add that interval into the solution.
Repeat the above way, we can generate a solution, and the count of those removed intervals is the final return value.

LeetCode 436 - Find Right Interval


http://bookshadow.com/weblog/2016/10/30/leetcode-find-right-interval/
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.
Note:
  1. You may assume the interval's end point is always bigger than its start point.
  2. You may assume none of these intervals have the same start point.
Example 1:
Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.
Example 2:
Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.
Example 3:
Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.
https://www.cnblogs.com/liujinhong/p/6399135.html
给定一系列的区间,对于任意一个区间,在所有区间中找到一个区间的起始点大于等于当前区间的结束点,并且要求这两个点最接近。
【思路】
首先对所有区间的起始点进行排序,然后对于每一个区间使用二分查找来找到与这个区间结束点最接近的起始点的区间,并且获得该区间的索引。
X. Use TreeMap to store intervals
Use TreeMap<Integer, PriorityQueue<Integer|Interval>> to handle duplicate start
https://leetcode.com/problems/find-right-interval/discuss/91789/java-clear-on-logn-solution-based-on-treemap
    public int[] findRightInterval(Interval[] intervals) {
        int[] result = new int[intervals.length];
        java.util.NavigableMap<Integer, Integer> intervalMap = new TreeMap<>();
        
        for (int i = 0; i < intervals.length; ++i) {
            intervalMap.put(intervals[i].start, i);    
        }
        
        for (int i = 0; i < intervals.length; ++i) {
            Map.Entry<Integer, Integer> entry = intervalMap.ceilingEntry(intervals[i].end);
            result[i] = (entry != null) ? entry.getValue() : -1;
        }
        
        return result;
    }
- When there is duplicate start
Given that, you are using a treemap, which derived from Map. if you put the same key with a different value it will replace the original one with the newer one. In such case, if you have case like
[[4,6],[1,2],[4,8]]
the correct answer should be
[-1,0,-1]
However, the answer you provide will give
[-1,2,1]
Because in the treeMap the [4,8] will store as 4->2 ,which replace the
previously inserted [4,6] stored as 4->0 for the Map property.
Anyway, you guys show me how to use treemap, still be a brilliant solution.
Updated:
Here attached my edited code which can fix this problem while passing all the test case.
  public int[] findRightInterval(Interval[] intervals) {
         TreeMap<Integer, PriorityQueue<Integer>> map = new TreeMap<>();
         int[] res = new int[intervals.length];
         for(int i=0;i<intervals.length;i++){ 
          if(map.get(intervals[i].start)==null){
           PriorityQueue<Integer> pq=new PriorityQueue<>();
           pq.add(i);
           map.put(intervals[i].start, pq);
          }
          else{
           map.get(intervals[i].start).add(i);
          }
         }
         for(int i=0;i<intervals.length;i++) {
             Integer key = map.ceilingKey(intervals[i].end);
             res[i] = key!=null ?map.get(key).peek() : -1;
         }
         return res;
     }

X. 排序(Sort)+ 二分查找(Binary Search) 按照区间起点排序,然后二分查找即可。
https://leetcode.com/problems/find-right-interval/discuss/91815/Commented-Java-O(n*logn)-solution.-Sort-%2B-Binary-Search.
public int[] findRightInterval(Interval[] intervals) {
        
        int n;
        // boundary case
        if (intervals == null || (n = intervals.length) == 0) return new int[]{};
        
        // output
        int[] res = new int[intervals.length];
        // auxilliary array to store sorted intervals
        Interval[] sintervals = new Interval[n];
        
        // sintervals don't have any use of 'end', so let's use it for tracking original index
        for (int i = 0; i < n; ++i) {
            sintervals[i] = new Interval(intervals[i].start, i);
        }
        
        // sort
        Arrays.sort(sintervals, (a, b)->a.start-b.start);
        
        int i = 0;
        for (; i < n; ++i) {
            int key = intervals[i].end;
            // binary search in sintervals for key
            int l = 0, r = n - 1;
            int right = -1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (sintervals[m].start == key) {
                    right = sintervals[m].end; // original index is stored in end
                    break;
                } else if (sintervals[m].start < key) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            
            // if we haven't found the key, try looking for 'start' that's just greater
            if ((right == -1) && (l < n) && (sintervals[l].start > key)) {
                right = sintervals[l].end; // original index is stored in end
            }
            
            res[i] = right;
        }
        
        return res;
    }
https://discuss.leetcode.com/topic/67399/java-concise-binary-search
http://www.cnblogs.com/javanerd/p/6061042.html
把这些interval按照start从小到大排序,然后对每一个interval用其end去在排好序的队列里面做二分查找,找到符合要求的一个interval
public int[] findRightInterval(Interval[] intervals){
        Interval[] sortedIntervals = Arrays.copyOf(intervals,intervals.length);
        Arrays.sort(sortedIntervals,(o1, o2) -> o1.start - o2.start);
        int[] result = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            Interval current = intervals[i];
            int insertIndex = Arrays.binarySearch(sortedIntervals, current, (o1, o2) -> o1.start - o2.end);
            if (insertIndex < 0){
                insertIndex = -insertIndex - 1;
            }
            if (insertIndex == intervals.length){
                result[i] = -1;
            }else {
                Interval match = sortedIntervals[insertIndex];
                for (int j = 0; j < intervals.length; j++){// bad....
                    if (i != j && match.start == intervals[j].start && match.end == intervals[j].end){
                       // System.out.println(",old index:"+j);
                        result[i] = j;
                    }
                }
            }

        }
        return result;
    }

If we are not allowed to use TreeMap:
  1. Sort starts
  2. For each end, find leftmost start using binary search
  3. To get the original index, we need a map
public int[] findRightInterval(Interval[] intervals) {
    Map<Integer, Integer> map = new HashMap<>();
    List<Integer> starts = new ArrayList<>();
    for (int i = 0; i < intervals.length; i++) {
        map.put(intervals[i].start, i);
        starts.add(intervals[i].start);
    }
    
    Collections.sort(starts);
    int[] res = new int[intervals.length];
    for (int i = 0; i < intervals.length; i++) {
        int end = intervals[i].end;
        int start = binarySearch(starts, end);
        if (start < end) {
            res[i] = -1;
        } else {
            res[i] = map.get(start);
        }
    }
    return res;
}

public int binarySearch(List<Integer> list, int x) {
    int left = 0, right = list.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (list.get(mid) < x) { 
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return list.get(left);
}
https://discuss.leetcode.com/topic/65641/commented-java-o-n-logn-solution-sort-binary-search
Time compexity: n*log(n)
n*log(n) for sorting
log(n) for binary search X n times is n*log(n)
Space complexity: n
n for auxilliary array
Algorithm:
  1. Clone intervals and update end with index.
  2. Sort clone-intervals by start
  3. Iterate over each interval and find the right by binary searching the clone-intervals.
  4. If found, shove the end i.e., the original index of the right interval from clone-intervals into the output array.
public int[] findRightInterval(Interval[] intervals) {
        
        int n;
        // boundary case
        if (intervals == null || (n = intervals.length) == 0) return new int[]{};
        
        // output
        int[] res = new int[intervals.length];
        // auxilliary array to store sorted intervals
        Interval[] sintervals = new Interval[n];
        
        // sintervals don't have any use of 'end', so let's use it for tracking original index
        for (int i = 0; i < n; ++i) {
            sintervals[i] = new Interval(intervals[i].start, i);
        }
        
        // sort
        Arrays.sort(sintervals, (a, b)->a.start-b.start);
        
        int i = 0;
        for (; i < n; ++i) {
            int key = intervals[i].end;
            // binary search in sintervals for key
            int l = 0, r = n - 1;
            int right = -1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (sintervals[m].start == key) {
                    right = sintervals[m].end; // original index is stored in end
                    break;
                } else if (sintervals[m].start < key) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            
            // if we haven't found the key, try looking for 'start' that's just greater
            if ((right == -1) && (l < n) && (sintervals[l].start > key)) {
                right = sintervals[l].end; // original index is stored in end
            }
            
            res[i] = right;
        }
        
        return res;
    }
X.
https://discuss.leetcode.com/topic/65585/java-sweep-line-solution-o-nlogn
  1. wrapper class: Point
    1. value
    2. flag: 1 indicates start, 2 indicates end
    3. index: original pos in intervals array
    4. Comparable: sort by value ascending, end in front of start if they have same value.
  1. Iterate intervals array and fill a points list, then sort it
  2. Iterate points list, since the sequence will be "order by position, and end will come before start".
    1. whenever meet a end point, keep a list(prevIdxs) before next start, save original index of curr interval to the list.
    2. whenever meet a start point, this start point is the right interval to the intervals in the list (prevIdxs). Take out each index in it and update to result.
class Point implements Comparable<Point>{
    int val;
    int flag; //1 start, 0 end
    int index;
    public Point(int val, int flag, int index) {
        this.val = val;
        this.flag = flag;
        this.index = index;
    }
    public int compareTo(Point o) {
        if (this.val == o.val) return this.flag - o.flag; //end in front of start
        return this.val - o.val;
    }
}
public int[] findRightInterval(Interval[] intervals) {
    if (intervals == null || intervals.length == 0) return new int[]{};
    
    int[] res = new int[intervals.length];
    Arrays.fill(res, -1);
    
    List<Point> points = new ArrayList<>();
    for (int i = 0; i < intervals.length; i++) {
        points.add(new Point(intervals[i].start, 1, i));
        points.add(new Point(intervals[i].end, 0, i));
    }
    
    Collections.sort(points);
    
    int prevEnd = 0;
    List<Integer> prevIdxs = new ArrayList<>();
    
    for (Point point: points) {
        if (point.flag == 1) {
                for (Integer prevIdx: prevIdxs) {
                   res[prevIdx] = point.index; 
                }
                prevIdxs = new ArrayList<>();
        } else {
            prevEnd = point.val;
            prevIdxs.add(point.index);
        }
    }
    
    return res;
}


http://www.voidcn.com/article/p-qrdsmkvw-bmq.html
public int[] findRightInterval(Interval[] intervals) {  
 int n=intervals.length;
 if(n==1){
  return new int[]{-1};
 }
 int[] result=new int[n];
 IntervalWithIndex[] intervalWithIndexs=new IntervalWithIndex[n];
 for(int i=0;i<n;i++){
  IntervalWithIndex in=new IntervalWithIndex(intervals[i], i);
  intervalWithIndexs[i]=in;
 }
 Arrays.sort(intervalWithIndexs, (a,b)->(a.interval.start-b.interval.start));
 for(int i=0;i<n;i++){
  int index=intervalWithIndexs[i].index;
  Interval interval=intervalWithIndexs[i].interval;
  boolean isFind=false;
  for(int j=i+1;j<n;j++){
   if(intervalWithIndexs[j].interval.start>=interval.end){
    isFind=true;
    result[index]=intervalWithIndexs[j].index;
    break;
   }
  }
  if(isFind==false){
   result[index]=-1;
  }
 }
 return result;
}

class IntervalWithIndex{
 Interval interval;
 int index;
 public IntervalWithIndex(Interval interval,int index) {
  this.interval=interval;
  this.index=index;
 }
}

http://www.cnblogs.com/grandyang/p/6018581.html

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts