Solutions by linear scan. Solve local and propagate linearly. If you cannot transform the problem to local units, things went wrong.
1. Trapping Rain Water (Leetcode)
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
Solution Notes:
1) Compare the height of two sides. Work on lower side.
If it decreases moving toward middle, then water can hold, but the more decrease hold more, so the basin base needs to store to be deducted in future;
2) If it increases, local units completed. Calculate local amount by width X sides - base;
This side is renewed and compared to the other side. We continue working on lower side.
3) Watch the end condition. I am not sure how to write it optimally. I added a judgement of l+1==r in decreasing case.
int trap(vector<int>& height) {
int l=0, r= height.size()-1;
if (l>=r) return 0;
int lBase=0, rBase=0;
int amount=0;
int lTop=height[l];
int rTop=height[r];
int l_ind=l, r_ind=r;
while (l<r){
if (lTop<=rTop){ //move l side
if (height[++l]<lTop) {
lBase+=height[l];
if (l+1==r) {
amount+= lTop*(l-l_ind)-lBase;
return amount;
}
}
else {
amount+= lTop*(l-l_ind-1)-lBase;
lBase=0;
lTop=height[l];
l_ind=l;
}
}else{ //move r side
if (height[--r]<rTop){
rBase+=height[r];
if (l+1==r) {
amount+= rTop*(r_ind-r)-rBase;
return amount;
}
}
else {
amount+= rTop*(r_ind-r-1)-rBase;
rBase=0;
rTop=height[r];
r_ind=r;
}
}
}
return amount;
}
2. Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Solution: Compare all pairs is O(n^2). Taking advantage of the position information can improve it to O(n).
Note that, first we use two ends to make a widest rectangle. Try to move lower side inward. If the height decrease, the rectangle becomes lower and narrow, just pass. Whenever it grows higher, we can evaluate if this narrower but higher rectangle bigger.
Note 2, Keep moving the lower side. Otherwise, some local high rectangle could be missed.
Note 3, To write this kind of l<r code, first is to clearly write down the initial condition and decide the variables. Otherwise the code can be messy.
int maxArea(vector<int>& height) {
if (height.empty()) return 0;
int l=0;
int r=height.size()-1;
if (r==0) return 0;
//initilize
int lTop=l;
int rTop=r;
int local=min(height[lTop],height[rTop])*(r-l), global=local;
while (l<r){
//move left
if (height[lTop]<=height[rTop]){
l++;
if (height[l]<=height[lTop]){ //getting lower and narrower, nothing change
continue;
} else if (height[l]<height[rTop]){ //higher than lTop, but still lower than rTop
local= height[l]*(r-l);
} else { //higher than rTop
local= height[rTop]*(r-l);
lTop=l;
}
global= max(local, global);
}else{
r--;
if (height[r]<=height[rTop]){ //getting lower and narrower, nothing change
continue;
} else if (height[r]<height[lTop]){ //higher than rTop, but still lower than lTop
local= height[r]*(r-l);
} else { //higher than lTop
local= height[lTop]*(r-l);
rTop=r;
}
global= max(local, global);
}
}
return global;
}
3. Merge interval (leetcode)
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
vector<Interval> merge(vector<Interval>& intervals) {
sort (intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start;});
int N=intervals.size();
vector<bool>marker(intervals.size(), true);
for (int i=0; i<N-1; ++i){
if (intervals[i].end>=intervals[i+1].start){
intervals[i+1].start=min(intervals[i].start, intervals[i+1].start);
intervals[i+1].end=max(intervals[i].end, intervals[i+1].end);
marker[i]= false;
}
}
vector<Interval> ret;
for( int i=0; i<N; ++i){
if (marker[i]){
ret.push_back(intervals[i]);
}
}
return ret;
}
4. Look for insert position (leetcode)
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
Solution: binary sort with judgement on m-1 or m+1;
int searchInsert(vector<int>& nums, int target) {
if (nums.empty()) return 0;
int N=nums.size();
int l=0, h=N-1;
while(l<=h){
int m=l+(h-l)/2;
if (nums[m]==target) return m;
else if (nums[m]<target){
if(m+1==N || nums[m+1]>=target) return m+1;
else l=m+1;
}else if (m==0 ||nums[m-1]<target) return m;
else h=m-1;
}
}
5. Insert Interval (leetcode)
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Solition: Bugs there, to fix later.
//binary search
int bs(vector<Interval>& intervals, int target){
int l= 0;
int r= intervals.size()-1;
int N= intervals.size();
while(l<=r){
int m=l+(r-l)/2;
if (intervals[m].start==target){
return m;
}else if (intervals[m].start<target){
if (m+1==N || intervals[m+1].start>target) return m+1;
else l=m+1;
}else {
if (m==0 || intervals[m-1].start<target) return m;
else r=m-1;
}
}
}
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
int ind_s= bs(intervals, newInterval.start);
int ind_e= bs(intervals, newInterval.end);
vector<Interval> ret;
int N= intervals.size();
if (intervals.empty()) {
ret.push_back(newInterval);
return ret;
}
//no interaction case , ind_s =3, ind_e=3 ; including s=e=0 case
if (ind_s==ind_e) {
ret= intervals;
if (ind_s==0 ) ret.insert(intervals.begin(), newInterval);
else {
if (intervals[ind_s].end<=newInterval.end){ //replace ind_s with newInterval
ret[ind_s]= newInterval;}
else if (intervals[ind_s-1].end > newInterval.end) { //combine to ind_s
ret[ind_s].start= min(ret[ind_s].start,newInterval.start );
ret[ind_s].end= max(ret[ind_s].end,newInterval.end );
}
}
return ret;
}
int end= max(intervals[ind_e-1].end, newInterval.end);
int start;
//ind_e >ind_s at least cross two intervals
if (ind_s==0) { //pack from s to e to one bin
Interval combine(min(intervals[ind_s].start, newInterval.start), end);
ret.push_back(combine);
for (int i=ind_e; i<N; ++i){
ret.push_back(intervals[i]);
}
}else{ //s at least 1
for (int i=0; i<ind_s-1; ++i){
ret.push_back(intervals[i]);
}
if (intervals[ind_s-1].end>= newInterval.start) {start=intervals[ind_s-1].start;}
else {ret.push_back(intervals[ind_s-1]); start= newInterval.start;};
Interval combine(start, end);
ret.push_back(combine);
for (int i=ind_e; i<N; ++i){
ret.push_back(intervals[i]);
}
}
return ret;
}
6. Best Time to Buy and Sell Stock(leetcode)
Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Solution: The problem is clear to maintain max profit when the price drops to be lower than old buy. But you have to wait until next drop to conclude local profit. Compare this local profit to the global max profit. One scan is ok, so it is O(n).
int maxProfit(vector<int>& prices) {
int profit=0;
int buy=0, sell=0;
if (prices.empty()|| prices.size()==1) return 0;
for (int i=1; i<prices.size(); ++i){
if (prices[i]> prices[buy]) {
sell= i;
int profit_local=prices[sell]- prices[buy];
if (profit_local>profit) profit= profit_local;
} else if (prices[i]<prices[buy]){
buy= i; //waiting for end
sell= i;
}
}
return profit;
}
7. Best Time to Buy and Sell Stock II(leetcode)
Say you have an array for which the ith 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).
Solution: The change here is to accumulate all local profit. The local condition becomes if (prices[i]<=prices[sell]) That is, if only current price is lower than last sell, last sell profit is done and sum in. We buy new at this point. If current is bigger than last sell, we just assume we sell it now. (update sell day and profit, who knows tomorrow?)
int maxProfit(vector<int>& prices) {
int sell=0, buy=0, profit_sum=0, profit=0;
if (prices.size()<2) return 0;
for (int i=1; i<prices.size(); ++i){
if (prices[i]>prices[sell]){
sell=i;
profit= prices[sell]- prices[buy];
}else if (prices[i]<=prices[sell]){
profit_sum+= profit;
buy=i;
sell=i;
profit=0;
}
}
profit_sum+= profit;
return profit_sum;
}
10. Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity.
Solution: I struggle on this problem for long. I wrote a couple of codes but all failed to be O(n). I thought about set or map. But I tried to count during building up. This problem becomes so easy if we just delete val+-1 from a set.
int longestConsecutive(vector<int>& nums) {
set<int> ss;
for (int n:nums) ss.insert(n);
int maxL=1;
for (int n:nums){
if(ss.erase(n)){
int L=1;
int val=n;
while (ss.erase(++val)){}
L+= val-1-n;
val=n;
while (ss.erase(--val)){}
L+= n-val-1;
if (L>maxL) maxL=L;
}
}
return maxL;
}
