Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Problem link

Solution

• using a priority queue to keep the organize the k current candidates
• note that the default priority_queue in cpp is max_heap, I need to implement my own comparator function that supports min_heap with pointers as elements

struct compNode {
bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> q;
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        ListNode* min_node;
        for (auto n:lists){
            if (n){
                q.push(n);
            }
        }
        while (!q.empty()){
            min_node = q.top();
            q.pop();
            cur -> next = min_node;
            cur = cur->next;
            min_node = min_node->next;
            if (min_node) q.push(min_node);
        }
        cur -> next = NULL;
        cur = dummy->next;
        delete (dummy);
        return cur;
    }
};

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Problem link

Solution

• the random pointer may point to a node that hasn’t been created yet
• create the linked list first, and then add random pointers in the second pass using hashtable constant-time lookup
• need two passes

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // two lookups: ori.cur ->(using pointer) ori.rand -> new.rand
        unordered_map<RandomListNode*, RandomListNode*> h;
        RandomListNode* dummy = new RandomListNode(0);
        RandomListNode* cur = head;
        RandomListNode* new_cur = dummy;
        // linking next pointers
        while (cur){
            new_cur->next = new RandomListNode(cur->label);
            h[cur] = new_cur->next;
            cur = cur->next;
            new_cur = new_cur->next;
        }
        new_cur->next = NULL;
        // linking random pointers
        cur = head;
        new_cur = dummy->next;
        while (cur){
            new_cur->random = cur->random? h[cur->random]:NULL;
            new_cur = new_cur->next;
            cur = cur->next;
        }
        new_cur = dummy->next;
        delete(dummy);
        return new_cur;
    }
};

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Problem link

Solution

• The original head could be removed, therefore introduce dummy head to simplify the program
• be careful about the case where reading the end and still need to delete elements

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* dummy = new ListNode(0);
        if (!head) return NULL;
        dummy->next = head;
        ListNode* pre = dummy;
        int same = false;
        while (head->next){
            if (head->val == head->next->val){
                same = true;
            }else{ // not equal for now
                if (same == true){
                    pre->next = head->next; // delete
                    same = false;
                }else{
                    pre = head;
                }
            }
            head = head->next;
        }
        if (same == true){
            pre->next = head->next;
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Problem link

Solution

• calculate from right to left

class Solution {
public:
    string addBinary(string a, string b) {
        if (a.empty()) return b;
        if (b.empty()) return a;
        int m = a.size();
        int n = b.size();
        string c;
        bool carry=false;
        int i,j;
        int sum;
        for (i=m-1, j=n-1; i>=0 && j>=0; --i, --j){
            sum = a[i]-'0' + b[j]-'0' + carry;
            carry = sum/2? true:false;
            c = to_string(sum%2) + c;
        }
        if (j>=0){ // run out of a
            for (; j>=0; --j){
                sum = b[j]-'0' + carry;
                carry = sum/2? true:false;
                c = to_string(sum%2) + c;
            }
        }else if (i>=0){ // run out of b
            for (; i>=0; --i){
                sum = a[i]-'0' + carry;
                carry = sum/2? true:false;
                c = to_string(sum%2) + c;
            }
        }
        if (carry==1){
            c = "1" + c;
        }
        return c;
    }
};

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,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,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--;
        }
    }
};

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Problem link

Solution

• dummy head, to avoid checking the head node

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        int i;
        int start = 0;
        ListNode* next;
        ListNode* cur = head->next;
        ListNode* pre;
        while (cur){
            for (i=0; i<k && cur; i++, cur = cur->next); // check whether there are sufficient 
            if (i==k){
                pre = head->next;
                cur = pre->next;
                for (i=0; i<k-1; i++){
                    next = cur->next;
                    cur->next = pre;
                    pre = cur;
                    cur = next;
                }
                head->next->next = cur;
                next = head->next;
                head->next = pre;
                head = next;
                cur = head->next;
            }else{ // reaching the end of list
                head = dummy->next;
                delete dummy;
                return head;
            }
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

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

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Problem link

Solution

• backtrack with stack

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector< vector<int> > vv;
        int i;
        unsigned n=num.size();
        vector<int> v;
        vector<bool> used(n, false);

        i=0;
        while (true){
            // only stop the loop when it is at level zero and i goes over
            v.push_back(i);
            used[i]=true;
            for (i=0; i<n; i++){// looks for next available position to select
                if (used[i]==false){
                    break;
                }
            }
            if (v.size()==n){
                // a complete sequence is generated, backtrack
                vector<int> tmp;
                for (int j=0; j<v.size(); j++){
                    tmp.push_back(num[v[j]]);
                }
                vv.push_back(tmp);
                int j;
                do{
                    j=v.back();
                    v.pop_back();
                    used[j]=false;
                    for (++j; j<n; ++j){// starting from current indices, looks for next available position to select
                        if (used[j]==false){
                        break;
                        }
                    }
                }while(j>=n&&!v.empty()|| (j<n&&used[j]));
                if (j>=n&&v.empty()){
                    break;
                }
                i=j;
            }
        }
        return vv;
    }
};

Recursive solution

• use an auxiliary array to track whether the current element has been used in the current permutation

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int>> vv;
        vector<bool> u(num.size(), false); // used or 
        vector<int> v;
        rec(vv, v, u, num);
        return vv;
    }
    
    void rec(vector<vector<int>> &vv, vector<int> &v, vector<bool> &u, vector<int> &num){
        for (int i=0; i<num.size(); i++){
            if (!u[i]){ // if i is not used
                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;
            }
        }
    }
};

Count and Say

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 n^th sequence.

Note: The sequence of integers will be represented as a string.

Problem link

Solution

• careful about the order of strings added to the output

class Solution {
public:
    string countAndSay(int n) {
        string in="1";
        for (int i=1; i<n; i++){
            in = helper(in);
        }
        return in;
    }
    
    string helper(string &in) {
        string out;
        char c = in[0];
        int count=1;
        char countChar;
        for (int i=1; i<in.size(); i++) {
            if (in[i]==c) {
                count++;
            } else {
                countChar = count+'0';
                out = out + countChar;
                out = out + c;
                c = in[i];
                count = 1;
            }
        }
        countChar = count+'0';
        out = out + countChar;
        out = out + c;
        return out;
    }
};

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;
    }
};