Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

Problem link

Solution

  • one naive approach is to first sort the array, recursively find all permutations on that array, the permutation right after the input one is what we want. In the worst case, it is O(n!)
  • Time Limit Exceeded, also this solution needs extra space
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        vector<int> v(num.begin(), num.end()); // make a new copy
        sort(v.begin(), v.end());
        vector<bool> u(num.size(), false);
        vector<int> next;
        bool equal = false;
        rec(num, v, u, next, equal);
        if (!equal) num = v;
    }
    
    void rec(vector<int> &num, vector<int> &v, vector<bool> &u, vector<int> &next, bool equal){
        for (int i=0; i<v.size(); i++){
            if (!u[i]){
                next.push_back(v[i]);
                if (next.size() == v.size()){
                    if (equal==false){
                        if (next == num) equal = true;
                    }else{
                        num = next;
                        return;
                    }
                }else{
                    u[i] = true;
                    rec(num, v, u, next, equal);
                    if (next.size() == v.size() && equal){
                        num = next;
                        return;   
                    } 
                    u[i] = false;
                }
                next.pop_back();
            }
        }
    }
};

In-place solution using swapping

  • expanding the right segment when all the elements in the right segment are sorted in decreasing order
  • after expansion, reverse all elements in the right segments
  • be careful about equal elements in the array
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        // find right segment
        int right;
        int n=num.size();
        int i;
        int j;
        for (i=n-1; i>=1 && num[i-1]>=num[i]; --i);
        if (i==0){// start from lowest possible order
            sort(num.begin(), num.end());
            return;
        }
        // i is boundary of the right segment, find next element in right that is greater than num[right-1]
        right = i;
        for (i=n-1; num[right-1]>=num[i]; --i);
        swap(num[right-1], num[i]);
        // reverse right:n-1
        i=right; j=n-1;
        while (i<j){
            swap(num[i],num[j]);
            i++;
            j--;
        }
    }
};
Next Permutation

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.

Problem link

Solution

  • find the station with maximum difference, M, start from there. Because if it is possible from reach M from some other station, there must be gas left. It is sufficient but not necessary
  • save partial path in array, to avoid going over and over again
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int modi = gas.size()-1;
        int start = gas.size()-1;
        int left = 0;
        while (true){
            while ((left += gas[modi] - cost[modi])>=0){
                modi++;
                modi = modi % gas.size();
                if (modi == start){
                    return left>=0? start: -1;
                }
            }
            start--;
            if (start<0) return -1;
            if (modi == start){
                return left>=0? start: -1;
            }
            while ((left+= gas[start] - cost[start])<0 || gas[start] - cost[start]<0 ){
                start--;
                if (start<0) return -1;
                if (modi == start){
                    return left>=0? start: -1;
                }
            }
            modi++;
            modi = modi % gas.size();
            if (modi == start){
                return left>=0? start: -1;
            }
        }
        return -1;
    }
};

An improved solution

  • after one scan, if totalSum>0 and curSum>0, the sum of right of start < 0, curSum should be enough to support a cyclic visit
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int totalGas = 0;
        int curGas = 0;
        int start = 0;
        int diff;
        for (int i=0; i<gas.size(); ++i){
            diff = gas[i] - cost[i];
            curGas += diff;
            totalGas += diff;
            if (curGas<0){
                start = i+1;
                curGas = 0;
            }
        }
        return totalGas<0 ? -1:start;
    }
};
Gas Station

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Problem link

Solution

  • the first element in preorder is the root of the tree
class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if (preorder.size()!=inorder.size()) return NULL;
        return rec(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
    
    TreeNode* rec(vector<int> &preorder, int s1, int e1, vector<int> &inorder, int s2, int e2){
        if (s1>e1||s2>e2) return NULL;
        TreeNode* r = new TreeNode(preorder[s1]);
        int rIdx = -1;
        for (int i=s2; i<=e2; ++i){
            if (preorder[s1]==inorder[i]){
                rIdx = i;
                break;
            }
        }
        if (rIdx==-1) return NULL;
        int left = rIdx - s2;
        int right = e2 - rIdx;
        r->left = rec(preorder, s1+1, s1+left, inorder, s2, rIdx-1);
        r->right = rec(preorder, s1+left+1, s1+left+right, inorder, rIdx+1, e2);
        return r;
    }
};
Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Problem link

Solution

  • it is rather difficult to write the code without a systematic approach, need to be very careful about writing indices
  • key observation: the last node in postorder sequence is the root of the entire tree
class Solution
{
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        if (inorder.size()!=postorder.size()) return NULL;
        return rec(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
    }

    TreeNode* rec(vector<int> &inorder, int li, int ri, vector<int> &postorder, int lp, int rp)
    {
        TreeNode* left=NULL;
        TreeNode* parent=NULL;
        while (li<=ri && lp<=rp) {
            while (li<=ri && lp<=rp && inorder[li]==postorder[lp]) { // left child
                parent = new TreeNode(inorder[li]);
                parent->left = left;
                left = parent;
                ++li;
                ++lp;
            }
            if (li>ri){
                return parent; // finish constructing tree
            }
            // find the root first
            parent = new TreeNode(inorder[li]);
            parent -> left = left;
            int old_lp=lp;
            while (inorder[li]!=postorder[lp]) {
                lp++;
            }
            // right subtree store in inorder[li+1:li+lp-old_lp] and post order[old_lp:lp-1]
            parent->right = rec(inorder, li+1, li+lp-old_lp, postorder, old_lp, lp-1);
            li = li+lp-old_lp+1;
            lp = lp+1;
            left = parent;
        }
        return parent;
    };
};

A cleaner yet slower code

  • recursively construct both left and right subtrees
  • use the fact that the last element in postorder is the root
class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        if(inorder.size()!=postorder.size()) return NULL;
        int n = inorder.size();
        return buildBT(inorder, postorder, 0, n-1, 0, n-1);
    }
    
    TreeNode *buildBT(vector<int> &inorder, vector<int> &postorder, int s1, int e1, int s2, int e2) {
        if(s1>e1 || s2>e2) return NULL;
        TreeNode *root = new TreeNode(postorder[e2]);
        
        // find the rootIndex in inorder, and use it seperate the left and right subtrees
        int rootIndex = -1;
        for(int i=s1; i<=e1; i++) {
            if(inorder[i]==root->val) {
                rootIndex = i;
                break;
            }
        }
        if(rootIndex==-1) return NULL;
        int leftTreeSize = rootIndex - s1;
        int rightTreeSize = e1 - rootIndex;
        
        root->left = buildBT(inorder, postorder, s1, rootIndex-1, s2, s2+leftTreeSize-1);
        root->right = buildBT(inorder, postorder, rootIndex+1, e1, e2-rightTreeSize, e2-1);
        return root;
    }
};
Construct Binary Tree from Inorder and Postorder Traversal

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Problem link

Solution

  • apply the idea of reusing array like in pascal triangle II
  • reversing the traversal ordering to avoid overwriting important information
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if (triangle.empty()) return 0;
        vector<int> v(triangle.size(), INT_MAX);
        int i;
        int j;
        v[0] = triangle[0][0];
        for (i=1; i<triangle.size(); ++i){
            for (j=i; j>=0; --j){
                if (j==0){
                    v[0] = triangle[i][0] + v[0];
                }else if (j==i){
                    v[i] = triangle[i][i] + v[i-1];
                }else{
                    v[j] = min(v[j], v[j-1]) + triangle[i][j];
                }
            }
            
        }
        int ret = v[0];
        for (i=1; i<triangle.size(); ++i){
            if (v[i]<ret) ret = v[i];
        }
        return ret;        
    }
};
Triangle

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, abcd)
  • The solution set must not contain duplicate quadruplets.
    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

Problem link

Solution

  • two loops over the first and second indices and navigate the rest of the two using two pointers approach
class Solution {
public:
  vector<vector<int> > fourSum(vector<int> &num, int target) {
	vector<vector<int> > vv;
	if (num.size()<4) return vv;
	sort(num.begin(), num.end());
	int first_idx, second_idx, third_idx, four_idx;
	// loop through the first number
	int sum;
	for (first_idx = 0; first_idx<num.size()-3; ++first_idx){
	  if (first_idx>0 && num[first_idx-1]==num[first_idx]) continue;
	  for (second_idx = first_idx+1; second_idx<num.size()-2; ++second_idx){
		if (second_idx>first_idx+1 && num[second_idx-1]==num[second_idx]) continue;
		third_idx = second_idx + 1;
		four_idx = num.size() - 1;
		while (third_idx<four_idx){
		  sum = num[first_idx]+num[second_idx]+num[third_idx]+num[four_idx];
		  if (sum==target){ // found
			vector<int> v;
			v.push_back(num[first_idx]);
			v.push_back(num[second_idx]);
			v.push_back(num[third_idx]);
			v.push_back(num[four_idx]);
			vv.push_back(v);
			++third_idx;
			--four_idx;
			// only to avoid generating the solution
			while (third_idx<four_idx && num[third_idx]==num[third_idx-1]) ++third_idx;
			while (third_idx<four_idx && num[four_idx]==num[four_idx+1]) --four_idx;
		  }else if (sum<target) {
			++third_idx;
		  }else{
			--four_idx;
		  }
		}       
	  }
	}
	return vv;    
  }
}; 

An extension to kSum

  • use two pointers method for the last two elements
class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int>> allSol;
        vector<int> sol;
        sort(num.begin(),num.end());
        kSum(num, 0, num.size()-1, target, 4, sol, allSol);
        return allSol;
    }
    
    void kSum(vector<int> &num, int start, int end, int target, int k, vector<int> &sol, vector<vector<int>> &allSol) {
        if(k<=0) return;
        if(k==1) {
            for(int i=start; i<=end; i++) {
                if(num[i]==target) {
                    sol.push_back(target);
                    allSol.push_back(sol);
                    sol.pop_back();
                    return;
                }
            }
        } 
        
        if(k==2) {
            twoSum(num, start, end, target, sol, allSol);
            return;
        }
    
        for(int i=start; i<=end-k+1; i++) {
            if(i>start && num[i]==num[i-1]) continue;
            sol.push_back(num[i]);
            kSum(num, i+1, end, target-num[i], k-1, sol, allSol);
            sol.pop_back();
        }
    }
    
    void twoSum(vector<int> &num, int start, int end, int target, vector<int> &sol, vector<vector<int>> &allSol) {
        while(start<end) {
            int sum = num[start]+num[end];
            if(sum==target) {
                sol.push_back(num[start]);
                sol.push_back(num[end]);
                allSol.push_back(sol);
                sol.pop_back();
                sol.pop_back();
                start++;
                end--;
                while(num[start]==num[start-1]) start++;
                while(num[end]==num[end+1]) end--;
            }
            else if(sum<target)
                start++;
            else
                end--;
        }
    }
};
4Sum

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Problem link

Solution

  • modified from 3Sum solution
class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        int close = INT_MAX;
        int close_sum = INT_MAX;
        if (num.size()<3) return close_sum;
        sort(num.begin(), num.end());
        int first_idx, second_idx,  third_idx;
        // loop through the first number
        int sum;
        for (first_idx = 0; first_idx<num.size()-2; ++first_idx){
            second_idx = first_idx + 1;
            third_idx = num.size() - 1;
            while (second_idx<third_idx){
                sum = num[first_idx]+num[second_idx]+num[third_idx];
                if (sum==target){ // found
                    return sum;
                }else if (sum<target) {
                    if (close>abs(sum-target)){
                        close_sum = sum;
                        close = abs(sum-target);
                    }
                    ++second_idx;
                }else{
                    if (close>abs(sum-target)){
                        close_sum = sum;
                        close = abs(sum-target);
                    }
                    --third_idx;
                }
                
            }
        }
        return close_sum;    
    }
};
3Sum Closest