[LeetCode] Combinations

Problem Statement (link):

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Analysis:
Another classic DFS problem. Once we see "all possible" key words, we need to consider using DFS idea.

Two things to think about:
1) Avoid duplicates - we use a int st to avoid choosing the same combination again. In other words, we only choose the numbers larger than current numbers.
2) Choose k numbers - we decrease k each time we choose a number.

Code:

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > outv;
        if (k==0 || n<k) return outv;
        vector<int> res;
        recur(outv, res, n, k, 0);
        return outv;
    }

    void recur(vector<vector<int>> &outv, vector<int> &res, int n, int k, int st) {
        if (k==0) {
            outv.push_back(res);
            return;
        }

        for (int i=st; i<n; i++) {
            res.push_back(i+1);
            recur(outv, res, n, k-1, i+1);
            res.pop_back();
        }
        return;
    }
};

[LeetCode] Insertion Sort List

Problem Statement (link):
Sort a linked list using insertion sort.
Analysis:
We traverse the linked list, once we find a node has a smaller value than that of its previous node, we start another traversal from the very beginning of the linked list to find the right position for that node to insert in.

Note:
- Once we found an unordered node and re-insert it to the right position, we should not advance the prev pointer. For instance: we have 2->4->1->3, the prev pointer points to node 4, and the tmp pointer points to node 1, i.e., we need to re-insert node 1 to its right position. After re-insertion, the list becomes: 1->2->4->3, the prev pointer still points to node 4, if we advance prev to node 3, we would miss re-insertion of node 3. The bool flag is for this purpose.

Extra link:
A very good review of sorting algorithms is summarized here by Yu.

Code: 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head==NULL) return NULL;
        bool inserted=false;
        ListNode *prev=new ListNode(INT_MIN);
        prev->next=head;
        ListNode *begin=prev;

        while(prev->next->next!=NULL) {
            ListNode *cur=prev->next;
            ListNode* tmp=cur->next;
            if (cur->val>tmp->val) {
                locate(begin, cur, tmp);
                inserted=true;
            }
            else if (prev->next->next!=NULL && inserted==false) {
                prev=prev->next;
                inserted=false;
            }
            else
                prev=prev->next;
        }
        return begin->next;
    }

    // locate and insert target node
    void locate(ListNode* begin, ListNode* prev, ListNode* target) { 
        while(begin->next->val<target->val)
            begin=begin->next;

        // insert
        ListNode* tmp=target->next;
        target->next=begin->next;
        prev->next=tmp;
        begin->next=target;
    }
};

[LeetCode] Count and Say

Problem Statement (link):

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.

Analysis:
No particular algorithms applied to this problem. Simply go through n rounds, wherein we calculate the time of each repeated characters and append to output string.

Code:

class Solution {
public:
    string countAndSay(int n) {
        string sout;
        string s="1";
        while(n-->1) {
            sout=helper(s);
            s=sout;
        }
        return s;
    }

    string helper(string s) {
        int count=0;
        char last=s[0];
        string sout="";
        for (int i=0; i<=s.length(); i++) {
            if (s[i]==last) count++;
            else {
                sout+=to_string(count)+s[i-1];
                last=s[i];
                count=1;
            }
        }
        return sout;
    }
};

Tower of Hanoi

Problem Statement (Wikipedia link):

Move N disks from one peg to another.

Analysis:
The Wikipedia page gives a pretty good explanation of the algorithm. Here we only consider recursive solution.

Suppose we have the following initial setup. Our goal is to move all disks from peg A to peg C.

Let's name the disk from 1, ..., N, where N corresponds to each disk's size.

Our goal is to move all disks from A to C, where A is the source and C is the destination. Thinking about this goal, the only situation that we could be successful is that all other 1, ..., N-1 disks are on peg B - spare, then we could move disk N from A to C. Hence, For these N-1 smaller disks, B is their source peg and C is destination peg. Recursively, the same logic applies to these N-1 disks.

With that, we have the following recursive logic:
1) Move N-1 disks from A to B;
2) Move disk N from A to C;
3) Move N-1 disks from B to C;

For a size N tower of hanoi problem, we need to perform 2^N - 1 movements. Hence, the time complexity is exponential.

Code:

void solveHanoi(int count, char src, char spare, char dest) {
    if (count==1)
        cout<<"Move disk from "<<src<<" to "<<dest<<endl;
    else {
        solveHanoi(count-1, src, dest, spare);
        solveHanoi(1, src, spare, dest);
        solveHanoi(count-1, spare, src, dest);
    }
}

Knight's Tours

Problem Statement (Wikipedia Link):

On a NxN chess board, find all legal Knight's Tours.

Fig., a valid Knight's Tour demo on N=5 chess board, courtesy of Wikipedia

Analysis:
Same as N-Queens problem, Knight's Tour is a classic problem that can be solved using backtracking. As other backtracking problems, the time complexity is exponential.

I have run a N=5 case, there are in total 304 possible solutions.

Note that the backtracking is not the optimal solution for the problem. See the wiki page here for other better algorithms, such as Divide and Conquer and Neural Networks (here).

Code:

// Main function
int numSols;
bool knightTour(int n, vector<vector<int>>& out) {
    int xmove[8]={-2,-2,-1,-1,1,1,2,2};
    int ymove[8]={1,-1,2,-2,2,-2,1,-1};

    // initialization
    for (int i=0; i<n; i++)
        out.push_back(vector<int> (n, -1));

    // start at upper left corner
    numSols=0;
    out[0][0]=0;
    return recur(0, 0, n, 1, xmove, ymove, out);
}

bool recur(int x, int y, int n, int visited, int xmove[], int ymove[], vector<vector<int>>& out) {
    if (visited>=n*n) {
        numSols++;
        printTour(n, out);
    }
    else { // try next move
        for (int i=0; i<8; i++) {
            if (isValid(x+xmove[i], y+ymove[i], n, out)) {
                out[x+xmove[i]][y+ymove[i]]=visited;
                if (recur(x+xmove[i], y+ymove[i], n, visited+1, xmove, ymove, out))
                    return true;
                else
                    out[x+xmove[i]][y+ymove[i]]=-1;
            }
        }
    }
    return true;
}

bool isValid(int x, int y, int n, vector<vector<int>> out) {
    if (x>=0 && x<n && y>=0 && y<n && out[x][y]==-1) return true;
    return false;
}

void printTour(int n, vector<vector<int>> out) {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cout<<out[i][j]<<"\t";
        }
        cout<<endl;
    }
    cout<<"\n";
}

[LeetCode] N-Queens I && II

N-Queens I

Problem Statement (link):

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.."]
]

Analysis:
Eight queens puzzle is a classic problem in use of DFS backtracking algorithm, it can be generalized to a N-queens puzzle.

The high-level idea of the backtracking algorithm is to choose any location as a start, try all possible positions until no violation to the rule has found. If a violation is found, we immediately abandon current placement and move the next possible position, if all possibilities has been tried for current queen, we go back to the previous queen and move that queen to its next possible position.

As describe in the statement, the rule for this game is: only one queen is placed in each row and column. This rule is used to check whether a position is legal for placing a queen.

Thus, the pseudo code looks like this:

1. Place the first queen in the left upper corner of the table.
2. Save the attacked positions.
3. Move to the next queen (which can only be placed to the next line).
4. Search for a valid position. If there is one go to step 8.
5. There is not a valid position for the queen. Delete it (the x coordinate is 0).
6. Move to the previous queen.
7. Go to step 4.
8. Place it to the first valid position.
9. Save the attacked positions.
10. If the queen processed is the last stop otherwise go to step 3.

The time complexity is exponential, same as all other backtracking algorithms.

A space-saving trick is we use 1-D vector to store the queens' 2-D location, where A[i]=j indicates row i, col j has a queen.

Code:

class Solution {
public:
    vector<vector<string> > out;
    // main function
    vector<vector<string> > solveNQueens(int n) {
        if (n==0) return out;
        vector<int> A(n, -1);   // Stores state for current solution, A[i]=j indicates row i, col j has a queen
        placeQueen(A, 0, n);    // starts from row 0
        return out;
    }

    // iterate thru row
    void placeQueen(vector<int> A, int cur, int n){ // cur - current row #
        if (cur==n) printOut(A, n);
        else {
            for (int i=0; i<n; i++){    // traverse thru each row, i-col
                A[cur]=i;
                if (isValid(A,cur)) {
                    placeQueen(A, cur+1, n);
                }
            }
        }
    }

    // To check if the current position is valid to place a queue
    bool isValid(vector<int> A, int row){
        for (int k=0; k<row; k++) { // row iteration
            if (A[k]==A[row] || (abs(A[k]-A[row])==(row-k))) {
                return false;
            }
        }
        return true;
    }

    // Update out to include current solution
    void printOut(vector<int> A, int n) {
        vector<string> v;   // a solution
        for (int i=0; i<n; i++){
            string s(n,'.');    // for each row
            s[A[i]] = 'Q';
            v.push_back(s);
        }

        out.push_back(v);
    }
};

N-Queens II

Problem statement (link):

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

Analysis:
The algorithm is exactly the same as in N-Queens I. Only difference is that instead of populating the location of each queens when we find a solution, we only need to count the number of solutions.

Code:

class Solution {
public:
    vector<vector<string> > out;
    int num;
    // main function
    int totalNQueens(int n) {
        if (n==0) return 0;
        vector<int> A(n, -1);   // Stores state for current solution, A[i]=j indicates row i, col j has a queen
        num = 0;
        placeQueen(A, 0, n);    // starts from row 0
        return num;
    }

    // iterate thru row
    void placeQueen(vector<int> A, int cur, int n){ // cur - current row #
        if (cur==n) num++;
        else {
            for (int i=0; i<n; i++){    // traverse thru each row, i-col
                A[cur]=i;
                if (isValid(A,cur)) {
                    placeQueen(A, cur+1, n);
                }
            }
        }
    }

    // To check if the current position is valid to place a queue
    bool isValid(vector<int> A, int row){
        for (int k=0; k<row; k++) { // row iteration
            if (A[k]==A[row] || (abs(A[k]-A[row])==(row-k))) {
                return false;
            }
        }
        return true;
    }
};

[LeetCode] Minimum Window Substring

Problem Statement (link):

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Analysis:
We use two index pointers to maintain a sub-string window that contains the chars in T. Two hash tables are used, one contains all the chars in T as key field and their occurrences as value field; the other one is dynamic hash table that maintains chars in the sub-string window and their occurrences, these chars are only those appear in T. Further, an int is used to keep track of the number of matching chars in the sub-string window. This int is important as it closely associates with the movement of the two index pointers.

The pseudo-code goes like this:
Initialize parameters, two indexes == 0
Scan through T to update needtoFind hash table;
Start from the beginning of S, for each end value:
    if current char is not in T, continue;
    otherwise, add current char to hasFound hash table;
    if the occurrences of current char in hasFound is no larger than that in needtoFind, increase count;

    if count equals T size:
        if current char does not exist in T or its occurrences in hasFound is larger than that in needtoFind, we advance begin pointer, meanwhile, if current char exists in T and hasFound has larger occurrences, decrease the value in hasFound
        if current window is smaller, update the minimum string and its size

To better understand the algorithm, e.g., S = "DOBECAODEBAANC", T = "AABC", the red chars represent the dynamic window.

S	Variables
DOBECAODEBAANC	begin = 0, end = 0
DOBECAODEBAANC	begin = 0, end = 10	Advance end until find a match
DOBECAODEBAANC	begin = 5, end = 10	Advance begin
DOBECAODEBAANC	begin = 5, end = 11	count stays the same, advance end, increase hasFound['A']
DOBECAODEBAANC	begin = 5, end = 13	Advance end, increase hasFound['C']
DOBECAODEBAANC	begin = 6, end = 13	Advance begin, decrease hasFound['C']
DOBECAODEBAANC	begin = 9, end = 13	Advance begin, decrease hasFound['A']

Take-aways:
In C++11, we could manipulate the nonexistent keys in unordered_map directly without initialize that key value, and the initial value of that key is 0. For instance, the following code is legal:

unordered_map<char, int> map;
int val = map['a'];   // val==0
map['b']--;     // map['b']==-1
int sz = map.size();   // sz==2

Code:

class Solution {
public:
    string minWindow(string S, string T) {
        int begin=0, end=0;  // for scanning S
        int m=INT_MAX;  // min window size
        string ms="";      // min string
        int count=0;    // matching num of chars in current window

        unordered_map<char, int> hasFound;      // for string S
        unordered_map<char, int> needtoFind;    // for string T

        for (int i=0; i<T.size(); i++)
            needtoFind[T[i]]++;

        for (int end=0; end<S.size(); end++) {
            // skip chars not in T
            if (needtoFind.find(S[end])==needtoFind.end()) continue;
            // o.w. add char into hasFound table
            hasFound[S[end]]++;
            if (hasFound[S[end]] <= needtoFind[S[end]]) count++;

            if (count==T.size()) {
                // advance begin pointer
                while (needtoFind.find(S[begin])==needtoFind.end() || hasFound[S[begin]]>needtoFind[S[begin]]) {
                    if (needtoFind.find(S[begin])!=needtoFind.end() && hasFound[S[begin]]>needtoFind[S[begin]]) hasFound[S[begin]]--;
                    begin++;
                }

                // update min string
                int winLen=end-begin+1;
                if (winLen<m) {
                    m=winLen;
                    ms=S.substr(begin, winLen);
                }
            }
        }
        return ms;
    }
};