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

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. Problem link Solution

  • recursive solution, only when last element is not  (the same and used)
class Solution {
public:
    vector<vector > permuteUnique(vector &num) {
        sort(num.begin(), num.end());
        vector<vector> vv;
        vector v;
        vector u(num.size(), false);
        rec(vv, v, u, num);
        return vv;
    }
    
    void rec(vector<vector> &vv, vector &v, vector &u, vector &num){
        for (int i=0; i<num.size(); ++i){
            if (!u[i] && (i==0 || i>0 && !(num[i]==num[i-1] && !u[i-1]))){
                v.push_back(num[i]);
                u[i] = true;
                if (v.size()==num.size()){
                    vv.push_back(v);
                }else{
                    rec(vv, v, u, num);
                }
                v.pop_back();
                u[i] = false;
            }
        }
    }
};
Permutations II

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Problem link

Solution

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string>> vv;
        vector<int> v;
        rec(vv, v, n);
        return vv;
    }
    
    void rec(vector<vector<string>> &vv, vector<int> &v, int n){
        for (int i=0; i<n; ++i){
            if (!conflict(v, i)){
                v.push_back(i);
                if (v.size()==n){
                    vv.push_back(conv(v));
                }else{
                    rec(vv, v, n);
                }
                v.pop_back();
            }
        }
    }
    
    vector<string> conv(vector<int> &v){
        int n=v.size();
        vector<string> vs(n, string(n,'.'));
        for (int i=0; i<n; ++i){
            vs[i][v[i]] = 'Q';
        }
        return vs;
    }
    
    bool conflict(vector<int> &assign, int new_queen){
        // check for conflict with all previously existing queens
        for (int i=0; i<assign.size(); i++){
            if (assign[i]==new_queen || assign.size()-i == abs(new_queen - assign[i])){
                return true;
            }
        }
        return false;
    }
};
N-Queens

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.


Problem link

Solution

  • use stack for backtracking
class Solution {
public:
    int totalNQueens(int n) {
        vector<int> assign;
        int sol_count = 0;
        int i;
        
        while (true){
            // place a new queen
            for (i=0; i<n; i++){
                if (!conflict(assign, i)){
                    assign.push_back(i);
                    if (assign.size()==n) {
                        // found a solution, backtracking
                        sol_count++;
                        if (!backtrack(assign, n))
                            return sol_count;
                    }
                    break;
                }
            }
            
            // no way to place it, backtracking
            if (i==n){
                if (!backtrack(assign, n)){
                    return sol_count;
                }
            }
        }
    }
    
private:
    bool backtrack(vector<int> &assign, int n){
        // iteratively backtrack starting from the last element in 
        // the assignment by increasing the last element by one
        int i;
        while (!assign.empty()){
            i = assign.back()+1;
            assign.pop_back();
            while (i<n){
                if (!conflict(assign, i)){
                    assign.push_back(i);
                    return true;
                }
                i++;
            }
        }
        return false;
    }
    
    bool conflict(vector<int> &assign, int new_queen){
        // check for conflict with all previously existing queens
        for (int i=0; i<assign.size(); i++){
            if (assign[i]==new_queen || assign.size()-i == abs(new_queen - assign[i])){
                return true;
            }
        }
        return false;
    }
};

A recursive solution

  • much easier to write
class Solution {
public:
    int totalNQueens(int n) {
        vector<int> assign;
        int sol_count = 0;
        rec(assign, n, sol_count);
        return sol_count;
    }
    
    void rec(vector<int> &assign, int n, int &sol_count){
        for (int i=0; i<n; i++){
            if (!conflict(assign, i)){
                assign.push_back(i);
                if (assign.size()==n){
                    ++sol_count;
                }else{
                    rec(assign, n, sol_count);    
                }
                assign.pop_back();
            }
        }
    }
    
    bool conflict(vector<int> &assign, int new_queen){
        // check for conflict with all previously existing queens
        for (int i=0; i<assign.size(); i++){
            if (assign[i]==new_queen || assign.size()-i == abs(new_queen - assign[i])){
                return true;
            }
        }
        return false;
    }
};
N-Queens II

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Problem link

Solution

  • progressively increase the size of substrings
  • use simple recursion, yet there are lots of duplication checks
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> vv;
        if (s.empty()) return vv;
        vector<string> v;
        rec(vv, v, s, 0, s.size()-1);
        return vv;
    }
    
    void rec(vector<vector<string>> &vv, vector<string> &v, string &s, int l, int r){
        for (int i=l; i<=r; ++i){
            string str = s.substr(l, i-l+1);
            if (check(str)){ // if pass the test
                v.push_back(str);
                if (i+1<=r){
                    rec(vv, v, s, i+1, r);
                }else{ // i==r
                    vv.push_back(v);
                }
                v.pop_back();
            }
        }
    }
    
    bool check(string &s){
        // check if the string is a palindrome
        int l = 0;
        int r = s.size()-1;
        while (l<=r){
            if (s[l]!=s[r]) return false;
            ++l;
            --r;
        }
        return true;
    }
};

An improved solution

  • saving the palindrome answers in a matrix
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> vv;
        vector<string> v;
        vector<vector<bool>> pal(s.size(), vector<bool>(s.size(), false));
        // two pointer method
        for (int i=s.size()-1; i>=0; --i){ 
            // reverse the order of i so that shorter subtrings are considered first
            for (int j=i; j<s.size(); ++j){
                if (s[i]==s[j] && (i+1>=j-1||pal[i+1][j-1])) pal[i][j] = true;
            }
        }
        rec(vv, v, s, pal, 0);
        return vv; 
    }
    
    void rec(vector<vector<string>> &vv, vector<string> &v, string &s, vector<vector<bool>> &pal, int l){
        for (int i=l; i<= s.size()-1; ++i){
            if (pal[l][i]){ // if pass the test
                v.push_back(s.substr(l, i-l+1));
                if (i+1<=s.size()-1){
                    rec(vv, v, s, pal, i+1);
                }else{ // i==r
                    vv.push_back(v);
                }
                v.pop_back();
            }
        }
    }
};
Palindrome Partitioning

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Problem link

Solution

  • use recursion to implement k-nested loops
  • be careful about the case when input is empty
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> v;
        if (digits.empty()){
            v.push_back(digits);
            return v;    
        } 
        string dict[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string s(digits.size(),'\0'); // string of all '\0' chars
        rec(v, s, digits, dict, 1);
        return v;
    }
    
    void rec(vector<string> &v, string &s, string &digits, string d[], int l){
        string lett = d[digits[l-1]-'0'];
        for (int i=0; i<lett.size(); ++i){
            s[l-1]=lett[i];
            if (l==digits.size()){
                v.push_back(s);
            }else{
                rec(v, s, digits, d, l+1);    
            }
        }
    }
};
Letter Combinations of a Phone Number

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