Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

Naive Way: I first think about Greedy. Go as far as possible each jump. But a future longer jump may lie in previous step. So I just think greedy is not able to handle this problem. Then I turn to DP. It seems DP will handle this problem easily.The basic logic is

opt[i] // whether a position can be reached or not
// base case
opt[0] = true;
// iteration
opt[i] = (opt[t] && A[t]+t >= i) for all 0<=t < i

But this approach get Time Limited Error.

An O(n^2) DP will get TLE, which implies an O(n) solution exists.

Then I think about DFS with path memorizing. Start from the end, trace backward to see if a particular position can reach the final stage. I am having trouble correctly writing the algorithm so far.


An ideal approach is a greedy one. Keep a range [start, end] that you are going to traversal. Update the range [end, new_end] according to farest distance one can go on [start, end].

 public class Solution {  
   public boolean canJump(int[] A) {  
     // Greedy  
     if(A == null || A.length==0) return true;  
     int start = 0, end = A[0];  
     while(start <= end){  
       if(end >= A.length-1) return true;  
       int pre_end = end;  
       for(int i = start;i <= pre_end;i++)  
         end = Math.max(end, i+A[i]);  
       start = pre_end+1;  
     }  
     return false;  
   }  
 }  

Improved Way: A much more simple greedy idea. Update current coverage each step.

 public class Solution {  
   public boolean canJump(int[] A) {  
     // Greedy  
     int coverage = 0;  
     for(int i = 0;i < A.length;i++)  
       if(coverage < i)   
         return false;  
       else  
         coverage = Math.max(coverage, A[i]+i);  
     return true;  
   }  
 }  

Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Naive Way: I try to draw an example like [1 2 1 3 2 1 2 1]. It turns out that for a given number h[i], whether the next position is great than h[i] or no greater than h[i] won't determine the largest capacity using h[i]. Only the last h[j] >= h[i] matters. So I tried two pointers, one from left and one from right, using two hashmap to keep track of number->position pairs.

Below code is based on that idea.

 public class Solution {  
   public int maxArea(int[] height) {  
     Map<Integer, Integer> rightMost = new HashMap<Integer,Integer>();  
     Map<Integer, Integer> leftMost = new HashMap<Integer, Integer>();  
     int left = 0, right = height.length-1;  
     int max = 0;  
     while(left < right){  
       while(left < right && leftMost.containsKey(height[left])) left++;  
       leftMost.put(height[left],left);  
       if(rightMost.containsKey(height[left])) max = Math.max(max,(right-left)*height[left]);  
       else{  
         while(left < right && height[right] < height[left]){  
           max = Math.max(max,(right-left)*height[right]);  
           rightMost.put(height[right], right);  
           right--;  
         }  
         for(int i = height[left];i <= height[right];i++)  
           rightMost.put(i,right);  
         max = Math.max(max,(right-left)*height[left]);  
       }  
     }  
     return max;  
   }  
 }  

This code has a big shortcoming in that it is not exact O(n), if two numbers are far away, say 2 and 200000, need to put into the map 200000 times. It is definitely not an ideal solution.

Improved Way: I finally realize that when a number as large as 200000 was met on the right, it matches almost all the left numbers. Right pointer don't need to move any more, Which means only the minimum of left and right should move! And integrate with the idea that only left and right boundaries matter. I finally come up with this code. Real O(n).

 public class Solution {  
   public int maxArea(int[] height) {  
     int left = 0, right = height.length-1;  
     int max = 0;  
     while(left < right){  
       max = Math.max(max, (right-left)*Math.min(height[left],height[right]));  
       if(height[left] < height[right])  
         left++;  
       else  
         right--;  
     }  
     return max;  
   }  
 }  

Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Naive Way: The problem said "You should pack your words in a greedy approach". So I will pack the words greedily. Grad as many words as I can each time to form a line. To calculate the space, use an extra var to hold the remaining space after evenly distributes. For the last column, could assign an extra check.

Combining one word case and the last line case is feasible.

 public class Solution {  
   public List<String> fullJustify(String[] words, int L) {  
     List<String> list = new ArrayList<String>();  
     int i = 0;  
     while(i < words.length){  
       int j = i;  
       int len = 0;  
       // grab as many words as I can  
       while(j < words.length && len+ (j-i) + words[j].length() <= L) len += words[j++].length();  
       // # of space need to be inserted between each word is j==i?0:(L-len)/(j-i)  
       int space = j<=i+1?0:(L-len)/(j-i-1);  
       // # of space remained, L - len - space*(j-i);  
       int remain = L -len- space*(j-i-1);  
       // construct a line  
       StringBuilder s = new StringBuilder();  
       // one word case & last line case  
       if(j==words.length || j<=i+1){  
         for(int t = i;t < j;t++){  
           s.append(words[t]);  
           if(t!=j-1) s.append(" ");  
         }  
         remain += space*(j-i-1)-(j-i-1);  
         for(int t = 0;t < remain;t++) s.append(" ");  
       }else{  
         // general case  
         for(int t = i;t < j;t++,remain--){  
           s.append(words[t]);  
           if(t!=j-1) for(int u = 0;u < space;u++) s.append(" ");  
           if(remain > 0) s.append(" ");  
         }  
       }  
       // add line  
       list.add(s.toString());  
       i = j;  
     }  
     return list;  
   }  
 }  

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

Naive Way: A brute force way is to start at each gas station and go as far as possible to see if the car can traversal through. That would be O(n^2) time complexity. The redundancy lies in that once you traversal far away starting from one gas station, the travel starting at next gas station can be predicted.

So the final approach is when the car fail at certain station, set the start point at the next station of that certain station. Because starting before that station would lead to failure at that certain station.

That makes the run time O(n), and O(1) space.

 public class Solution {  
   public int canCompleteCircuit(int[] gas, int[] cost) {  
     // edge case   
     if(gas.length==1) return gas[0] >= cost[0]?0:-1;  
     // genral case  
     boolean allVisited = false;  
     int i = 0;  
     while(i < gas.length){  
       // initialize tank  
       int j = (i+1)%gas.length;  
       if(j==0) allVisited = true; // check if all stations are visited  
       int tank = gas[i]-cost[i];  
       // travel as far as possible  
       while(tank >= 0){  
         tank += gas[j]-cost[j];  
         // check if meets start  
         if(j==i) return i;  
         // step forward  
         j++;  
         j %= gas.length;  
         if(j==0) allVisited = true;  
       }  
       // check ending condition  
       if(allVisited) break;  
       else i = j;  
     }  
     return -1;  
   }  
 }  

Improved Way: There is a better approach, just pick the i+1 -th  station on gas[i]-cost[i] = min(gas[j]-cost[j]) for all j. The solution is here.

Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Naive Way: I don't like the idea of rating children. This question is hard. Really Hard! To generate candy assignment in one pass is unaffordable. I turn to two pass. And it becomes more clear after I assign each children 1 candy at first.

Below solution requires two pass(three pass including sum up), O(n) space.

 public class Solution {  
   public int candy(int[] ratings) {  
     // initialize  
     int candy[] = new int[ratings.length];  
     int sum = 0;  
     Arrays.fill(candy,1); // crucial step!  
     // forward pass, assign candy for increasing ones  
     for(int i = 1;i < ratings.length;i++)  
       if(ratings[i] > ratings[i-1])  
         candy[i] = candy[i-1]+1;  
     // backforward pass, assign candy for decreasing ones  
     for(int i = ratings.length-2;i >= 0;i--)  
       if(ratings[i] > ratings[i+1]){  
         if(i-1 >= 0 && ratings[i-1] <= ratings[i])  
           candy[i] = Math.max(candy[i+1]+1, candy[i]);  
         else  
           candy[i] = candy[i+1] + 1;  
       }  
     // sum up candy  
     for(int i = 0;i < candy.length;i++)  
       sum += candy[i];  
     return sum;  
   }  
 }  

Improved Way: And this question of course can be solved in one pass. An good code with explanation is here

Maximum Gap

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Naive Way: 最初的想法是如果能排序，就能一次遍历求得最大gap，但是排序就是O(nlogn)了。要求在O(n)的时间内做出，唯一能利用的就是O(n)的space了。考虑最坏的情况是所有数字都具有相同间隔，比如[1 3 5 7 9]，在不改变区间范围的情况下，任意改变其中某个数都会使结果变大，也就是说，如果能确定数组的区间范围，(max-min)/size 就是最差的情况，任意有数不是在分割点上，说明本该在那个分割点上的数改变了，max gap也就改变了。

举个例子说明：[1,4,5,7,9]
最大是1，最小是9，一共5个数。5个数应该有4个分区，(平均分)。然后遍历一遍数组将每个数字归入自己所在分区。

[1,3)-> 最小值是1，最大值是1。
[3,5)-> 最小值是4，最大值是4。
[5,7)-> 最小值是5，最大值是5。
[7,9]-> 最小值是7，最大值是9。

这样就可以知道一旦某一区段最小值不是区段下限，就可以知道max gap 可能由它产生。遍历一遍区段，一旦有以上情况就要左右追溯，找出可能的max gap。

算法复杂度可以达到O(n)， space O(n)。

public class Solution {
    public int maximumGap(int[] num) {
        int maxGap = 0;
        // edge case
        if(num.length < 2) return maxGap;
        // find min and max
        int min = num[0], max = min;
        for(int i = 1;i < num.length;i++){
            min = Math.min(min,num[i]);
            max = Math.max(max,num[i]);
        }
        // form gaps
        int dis = (max-min)/(int)Math.min(max-min,num.length-1);
        List<List<Integer>> gaps = new ArrayList<List<Integer>>();
        for(int i = 0;i < (max-min)/dis;i++){
            List<Integer> gap = new ArrayList<Integer>();
            gap.add(-1);
            gap.add(-1);
            gaps.add(gap);
        }
        // fill in gaps
        for(int i = 0;i < num.length;i++){
            List<Integer> gap = gaps.get((int)Math.min(gaps.size()-1,(num[i]-min)/dis));
            if(gap.get(0)==-1)  gap.set(0,num[i]);
            else gap.set(0,Math.min(num[i],gap.get(0)));
            if(gap.get(1)==-1) gap.set(1,num[i]);
            else gap.set(1,Math.max(num[i],gap.get(1)));
        }
        // find maximum gap
        for(int i = 0;i < gaps.size();i++){
            List<Integer> gap = gaps.get(i);
            if(gap.get(0)==-1) continue; // means current gap is empty
            
            int j = i-1;
            // traversal lower level gaps
            while(j >= 0 && gaps.get(j).get(1)==-1) j--;
            if(j>=0) maxGap = Math.max(maxGap, gap.get(0)-gaps.get(j).get(1));
            
            // traversal upper level gaps
            j = i+1;
            while(j < gaps.size() && gaps.get(j).get(0)==-1) j++;
            if(j<gaps.size()) maxGap = Math.max(maxGap, gaps.get(j).get(0)-gap.get(1));
            
            // edge case for one gap
            maxGap = Math.max(maxGap, gap.get(1)-gap.get(0));
        }
        return maxGap;
    }
    
}


Improved Way:这种方法原来叫做bucket sort，原是一种排序的算法，特别适合用来求Gap。Discuss里无一例外全是这种方法，但是施行的也有好有坏，写得最好的我觉得是下面这个。

来自leetcode用户liaison ，使用了数组来存gap，连续的两个位置表示一个bucket。

public int maximumGap(int[] num) {
    if(num.length < 2){
        return 0;
    }

    // Find the min and max elements in the list.
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for(int e : num){
        min = Math.min(e, min);
        max = Math.max(e, max);
    }

    // Put the n elements into (n-1) buckets.
    double div = (max-min)*1.0/(num.length-1);

    // bucket[i]  : min value in the bucket i/2;
    // bucket[i+1]: max value in the bucket i/2;
    // Note: the elements are all non-negatives.
    int [] bucket = new int[num.length*2];
    for(int e : num){
        int i = (int)((e-min)/div) * 2;

        bucket[i]   = bucket[i] == 0 ? e : Math.min(e, bucket[i]);
        bucket[i+1] = bucket[i+1] == 0 ? e : Math.max(e, bucket[i+1]);
    }

    // Calculate the maximum distance between buckets,
    //  which is aslo the maximum gap between elements.
    int last_bound = min;
    int max_gap = Integer.MIN_VALUE;
    for(int i=0; i<num.length*2; i+=2){
        if(bucket[i] == 0){
            // no element in this bucket.
            continue;
        }

        max_gap = Math.max(bucket[i]-last_bound, max_gap);
        last_bound = bucket[i+1];
    }

    return max_gap;
}

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

 

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Naive Way: 这个感觉这样一改就跟原题不是一个套路了。很直观的感觉就是，买，直到下一个不是递增的，卖。一开始应该得先找到第一个递增区间的起点。

算法复杂度是O(n)

public class Solution {
    public int maxProfit(int[] prices) {
        int opt = 0;
        int begin = 0, end = 0;
        while(end + 1< prices.length){
            begin = end+1;
            while(begin < prices.length){
                if(prices[begin] > prices[begin-1])
                    break;
                begin++;
            }
            begin--;
            end = begin;
            while(end + 1 < prices.length){
                if(prices[end+1] < prices[end])
                    break;
                end++;
            }
            opt += prices[end] - prices[begin];
        }
        return opt;
    }
}


Improved Way: Discuss里有一种Greedy的算法，很好。一旦有股票的价格比前一天的高，就可以加上这个差价，即能赚就买。因为比如：
1  2  3  4  5
max profit = 5-1 = 4;
greedy      = 5-4 + 4-3 + 3-2 + 2-1 = 4;

虽然题目不让在同一天买卖，但实际上在递增的区间中同一天买卖和第一天买最后一天卖是一样。这是否也说明了炒股票应该见好就收呢。

public class Solution {
    public int maxProfit(int[] prices) {
        int opt = 0;
        int p = 0;
        while(++p < prices.length){
            opt += Math.max(prices[p]-prices[p-1],0);
        }
        return opt;
    }
}