My LeetCode Notebook

My LeetCode Notebook in C++.

Aug 8, 2016

Insert Delete GetRandom O(1) (medium)

// Runtime: 96ms, beat ?%
class RandomizedSet {
private:
    unordered_map<int, int> pos;
    vector<int> nums;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {

    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if (pos.find(val) != pos.end()) {
            return false;
        } else {
            pos[val] = nums.size();
            nums.push_back(val);
            return true;
        }
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if (pos.find(val) == pos.end()) {
            return false;
        } else {
            nums[pos[val]] = nums.back();
            pos[nums.back()] = pos[val];
            nums.pop_back();
            pos.erase(val);
            return true;
        }
    }

    /** Get a random element from the set. */
    int getRandom() {
        return nums[rand() % nums.size()];
    }
};
/**
  * Your RandomizedSet object will be instantiated and called as such:
  * RandomizedSet obj = new RandomizedSet();
  * bool param_1 = obj.insert(val);
  * bool param_2 = obj.remove(val);
  * int param_3 = obj.getRandom();
  */

Kth Smallest Element in a Sorted Matrix (medium)

// Runtime: 148ms, beat ?%
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        priority_queue<pair<long long, pair<int,int>>>  pq; // <value, <i, j>>
        pq.push(make_pair(-matrix[0][0], make_pair(0, 0)));
        for (int i = 1; i < k; i++) {
            int x = pq.top().second.first;
            int y = pq.top().second.second;
            pq.pop();
            if (y == 0 && x + 1< n) {
                pq.push(make_pair(-matrix[x+1][0], make_pair(x+1, 0)));
            }
            if (y + 1 < n) {
                pq.push(make_pair(-matrix[x][y+1], make_pair(x, y+1)));
            }
        }
        return -pq.top().first;
    }
};

July 30, 2016

Bulls and Cows (easy)

// Runtime: 4ms, beat 65.87%
class Solution {
public:
    string getHint(string secret, string guess) {
        int bull = 0, cow = 0;
        vector<int> cnt(10, 0);  // +1 if in secret, -1 if in guess
        for (int i = 0; i < secret.length(); i++) {
            if (secret[i] == guess[i]) {
                bull++;
            } else {
                cow += (cnt[secret[i] - '0']++) < 0;
                cow += (cnt[guess[i] - '0']--) > 0;
            }
        }
        return to_string(bull) + "A" + to_string(cow) + "B";
    }
};

Roman to Integer (easy)

// Runtime: 36ms, beat 82.16%
class Solution {
public:
    int romanToInt(string s) {
        static vector<int> val(26, 0);
        val['I'-'A'] = 1;
        val['V'-'A'] = 5;
        val['X'-'A'] = 10;
        val['L'-'A'] = 50;
        val['C'-'A'] = 100;
        val['D'-'A'] = 500;
        val['M'-'A'] = 1000;
        int result = s.empty() ? 0 : val[s.back()-'A'];
        for (int i = s.length() - 2; i >= 0; i--) {
            int crt_val = val[s[i]-'A'];
            if (crt_val < val[s[i+1]-'A']) {
                result -= crt_val;
            } else {
                result += crt_val;
            }
        }
        return result;
    }
};

Nim Game (easy)

Notes, n

• 1, 2, 3: win
• 4: lose
• 5: take one stone, win
• 6: take two stones, win
• 7: take three stones, win
• 8: lose

// Runtime: 0ms
class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

Power of Three (easy)

Solution 1 (learned online)

• This method only works for “Power of b“ where b is a prime number.
• Suppose 0<x=b^a<=INT_MAX.
  Let y be the maximum power of b no larger than INT_MAX.
  We must have y%x==0

// Runtime: 132ms, beat 75.75%
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0; //1162261467=3^19
    }
};

Solution 2

// Runtime: 136ms, beat 68.51%
class Solution {
public:
    bool isPowerOfThree(int num) {
        double tmp = log(num)/log(3);
        return num > 0 && abs(tmp - round(tmp)) < 1e-10;
    }
};

Power of Four (easy)

Similar to the problem of “Power of Two”, the first two conditions check whether num is power of two.
If so, we also check whether the only 1 bit is in the right position.
The number of trailing zeros in the binary form should be even).

// Runtime: 8ms, beat 13.80%
class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && !(num & (num-1)) && (num & 0x55555555);
    }
};

Power of Two (easy)

Naive implementation

// Runtime: 4ms, beat 9.91%
class Solution {
public:
    bool isPowerOfTwo(int n) {
        while (n) {
            if (n & 1) {
                return n == 1;
            }
            n >>= 1;
        }
        return false;
    }
};

Smarter solution: Suppose n is power of two, say n=8.

• Its binary form looks like 01000, and n-1 looks like 00111.
• Therefore, n & (n-1) must be zero.

// Runtime: 4ms, beat 9.91%
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (!(n & (n-1)));
    }
};

Implement Queue using Stacks (easy)

// Runtime: 0ms
class Queue {
private:
    stack<int> s;
public:
    // Push element x to the back of queue.
    void push(int x) {
        stack<int> tmp;
        while (!s.empty()) {
            tmp.push(s.top());
            s.pop();
        }
        s.push(x);
        while (!tmp.empty()) {
            s.push(tmp.top());
            tmp.pop();
        }
    }

    // Removes the element from in front of queue.
    void pop(void) {
        s.pop();
    }

    // Get the front element.
    int peek(void) {
        return s.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return s.empty();
    }
};

Implement Stack using Queues (easy)

// Runtime: 0ms
class Stack {
private:
    queue<int> q;
public:
    // Push element x onto stack.
    void push(int x) {
        int old_size = q.size();
        q.push(x);
        while (old_size-- > 0) {
            int tmp = q.front();
            q.pop();
            q.push(tmp);
        }
    }

    // Removes the element on top of the stack.
    void pop() {
        q.pop();
    }

    // Get the top element.
    int top() {
        return q.front();
    }

    // Return whether the stack is empty.
    bool empty() {
        return q.empty();
    }
};

Compare Version Numbers (easy)

// Runtime: 0ms
class Solution {
public:
    int compareVersion(string version1, string version2) {
        version1+=".";
        version2+=".";
        size_t i = 0, j = 0;
        do {
            size_t nxt_i = version1.find_first_of('.', i);
            size_t nxt_j = version2.find_first_of('.', j);
            int v1 = stoi(version1.substr(i, nxt_i - i));
            int v2 = stoi(version2.substr(j, nxt_j - j));
            if (v1 < v2) {
                return -1;
            } else if (v1 > v2) {
                return 1;
            }
            i = nxt_i + 1;
            j = nxt_j + 1;
        } while (i < version1.length() && j < version2.length());
        if (i == version1.length() && j == version2.length()) {
            return 0;
        } else if (i < version1.length()) {
            // version1 is longer
            return version1.find_first_not_of("0.", i) != string::npos ? 1 : 0;
        } else {
            // version2 is longer
            return version2.find_first_not_of("0.", j) != string::npos ? -1 : 0;
        }
    }
};

Recursive implementation

July 29, 2016

Binary Tree Level Order Traversal II (easy)

// Runtime: 8ms, beat 25.28%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> q_crt, q_nxt;
        if (root != NULL) q_nxt.push(root);
        while (!q_nxt.empty()) {
            q_crt.swap(q_nxt);
            result.push_back(vector<int>());
            while (!q_crt.empty()) {
                TreeNode *q = q_crt.front();
                result.back().push_back(q->val);
                q_crt.pop();
                if (q->left) q_nxt.push(q->left);
                if (q->right) q_nxt.push(q->right);
            }
        }

        for (int i = 0; i < result.size() / 2; i++) {
            result[i].swap(result[result.size() - i - 1]);
        }
        return result;
    }
};

Recursive implementation.

// Runtime: 4ms, beat 91.32%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    void levelOrderBottomHelper(TreeNode* root, int level, vector<vector<int>> &result) {
        if (root != NULL) {
            if (result.size() < level + 1) {
                result.resize(level + 1);
            }
            result[level].push_back(root->val);
            levelOrderBottomHelper(root->left, level+1, result);
            levelOrderBottomHelper(root->right, level+1, result);
        }
    }
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        levelOrderBottomHelper(root, 0, result);
        for (int i = 0; i < result.size() / 2; i++) {
            result[i].swap(result[result.size() - i - 1]);
        }
        return result;
    }
};

Intersection of Two Linked Lists (easy)

// Runtime: 48ms, beat 95.28%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
private:
    int getLen(ListNode *head) {
        int len = 0;
        while (head != NULL) {
            len++;
            head = head->next;
        }
        return len;
    }
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = getLen(headA), lenB = getLen(headB);
        while (lenA > lenB) {
            headA = headA->next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB->next;
            lenB--;
        }
        while (lenA > 0) {
            if (headA == headB) return headA;
            headA = headA->next;
            headB = headB->next;
        }
        return NULL;
    }
};

Symmetric Tree (easy)

// Runtime: 4ms, beat 28.55%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    bool isSymmetricHelper(TreeNode* root1, TreeNode *root2) {
        if (root1 == NULL) return root2 == NULL;
        if (root2 == NULL) return root1 == NULL;
        // root1 != NULL && root2 !=NULL
        return root1->val == root2->val && isSymmetricHelper(root1->left, root2->right) && isSymmetricHelper(root1->right, root2->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        return root == NULL || isSymmetricHelper(root->left, root->right);
    }
};

Balanced Binary Tree (easy)

// Runtime: 16ms, beat 17.00%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    // return the height if balanced
    // return -1 otherwise
    int isBalancedHelper(TreeNode *root) {
        if (root == NULL) return 0;
        int ret_left = isBalancedHelper(root->left);
        int ret_right = isBalancedHelper(root->right);
        if (ret_left < 0 || ret_right < 0 || abs(ret_left - ret_right) > 1) {
            return -1;  // unbalanced
        } else {
            return 1 + max(ret_left, ret_right);
        }
    }
public:
    bool isBalanced(TreeNode* root) {
        return isBalancedHelper(root) >= 0;
    }
};

Factorial Trailing Zeroes (easy)

We need to find out how many “fives” are there.

// Runtime: 4ms, beat 18.80%
class Solution {
public:
    int trailingZeroes(int n) {
        int cnt_five = 0;
        while (n > 0) {
            cnt_five += n / 5;
            n /= 5;
        }
        return cnt_five;
    }
};

Pascal’s Triangle II (easy)

// Runtime: 0ms, beat 24.78%
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ret(rowIndex + 1, 1);
        for (int i = 2; i <= rowIndex; i++) {
            for (int j = i - 1; j >= 1; j--) {
                ret[j] = ret[j-1] + ret[j];
            }
        }
        return ret;
    }
};

Pascal’s Triangle (easy)

// Runtime: 0ms, beat 28.29%
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        for (int i = 0; i < numRows; i++) {
            result.emplace_back(i + 1, 1);
            for (int j = 1; j < i; j++) {
                result[i][j] = result[i-1][j-1] + result[i-1][j];
            }
        }
        return result;
    }
};

Path Sum (easy)

// Runtime: 12ms, beat 21.69%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        if (!root->left && !root->right) {
            return sum == root->val;
        } else {
            return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
        }
    }
};

Valid Sudoku (easy)

// Runtime: 12ms, beat 56.30%
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unsigned int row[9] = {0}, col[9] = {0}, block[9] = {0};
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    unsigned int mask = 1 << (board[i][j] - '0');
                    if (row[i] & mask) {
                        return false;
                    } else {
                        row[i] |= mask;
                    }
                    if (col[j] & mask) {
                        return false;
                    } else {
                        col[j] |= mask;
                    }
                    if (block[i/3*3+j/3] & mask) {
                        return false;
                    } else {
                        block[i/3*3+j/3] |= mask;
                    }
                }
            }
        }
        return true;
    }
};

Linked List Cycle (easy)

// Runtime: 12ms, beat 25.00%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head ? head->next : NULL;
        ListNode *fast = slow ? slow->next : NULL;
        while (fast != NULL && fast != slow) {
            slow = slow->next;
            fast = fast->next;
            if (fast != NULL) {
                fast = fast->next;
            }
        }
        return fast != NULL;
    }
};

Lowest Common Ancestor of a Binary Search Tree (easy)

// Runtime: 40ms, beat 66.05%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val < root->val && q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else {
          return root;
        }
    }
};

Number of 1 Bits (easy)

// Runtime: 4ms, beat 60.49%
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while (n > 0) {
            cnt += n & 1;
            n >>= 1;
        }
        return cnt;
    }
};

Count and Say (easy)

It is unclear what will happen if cnt>9. The problem description is not clear about this.

// Runtime: 0ms, beat 73%
class Solution {
public:
    string countAndSay(int n) {
        if (n <= 0) return "";
        string res = "1";
        while (--n > 0) {
            string prev{""};
            prev.swap(res);
            for (int i = 0, cnt = 0; i < prev.length(); i += cnt) {
                cnt = 1;
                for (int j = i + 1; j < prev.length() && prev[j] == prev[i]; j++) {
                    cnt++;
                }
                res.append(1, cnt + '0');
                res.append(1, prev[i]);
            }
        }
        return res;
    }
};

Reverse Bits (easy)

// Runtime: 4ms, beat 49.42%
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t r = 0;
        for (int i = 0; i < 32; i++, n>>=1) {
            r = (r << 1) | (n & 1);
        }
        return r;
    }
};

Longest Common Prefix (easy)

// Runtime: 4ms, beat 53.44%
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";

        int len = 0;
        bool ok = true;
        while (len < strs[0].length() && ok) {
            for (int i = 1; i < strs.size() && ok; i++) {
                ok &= (strs[i][len] == strs[0][len]);
            }
            if (ok) len++;
        }
        return strs[0].substr(0, len);
    }
};

Implement strStr() (easy)

Naive implementation

// Runtime: 4ms, beat 33.56%
class Solution {
public:
    int strStr(string haystack, string needle) {
        int len1 = haystack.length();
        int len2 = needle.length();
        for (int i = 0; i <= len1 - len2; i++) {
            bool ok = true;
            for (int j = 0; j < len2 && ok; j++) {
                ok &= (haystack[i+j] == needle[j]);
            }
            if (ok) return i;
        }
        return -1;
    }
};

ZigZag Conversion (easy)

For each position in the returned string, calculate its original position in s.

// Runtime: 16ms, beat 76.68%
class Solution {
public:
    string convert(string s, int numRows) {
        // corner cases
        if (numRows == 1) return s;
        // normal cases
        int len = s.length(), x = numRows * 2 - 2;
        string result(s);
        int result_pos = 0;
        for (int i = 0; i < numRows; i++) {
            int s_pos = i, s_pos1 = i + 2 * (numRows - i - 1);
            while (s_pos < len) {
                result[result_pos++] = s[s_pos];
                if (i != 0 && i != numRows - 1 && s_pos1 < len) {
                    result[result_pos++] = s[s_pos1];
                }
                s_pos += x;
                s_pos1 += x;
            }
        }
        return result;
    }
};

Reverse Integer (easy)

// Runtime: 8ms, beat 50.08%
class Solution {
public:
    int reverse(int x) {
        long long tmp = labs(x);
        long long result = 0;
        while (tmp > 0) {
            result = result * 10 + tmp % 10;
            tmp /= 10;
        }
        if (x < 0) {
            result *= -1;
            return result < INT_MIN ? 0 : result;
        } else {
            return result > INT_MAX ? 0 : result;
        }
    }
};

Another implementation using string.

// Runtime: 12ms, beat 9.63%
class Solution {
public:
    int reverse(int x) {
        // x -> string -> reverse -> result
        string str = to_string(labs(x));
        std::reverse(str.begin(), str.end());
        long long result = std::stol(str);
        // return
        result *= (x < 0) ? -1 : 1;
        return result >= INT_MIN && result < INT_MAX ? result : 0;
    }
};

Valid Parentheses (easy)

// Runtime: 0ms, beat 15.40%
class Solution {
public:
    bool isValid(string s) {
        stack<char> p;
        for (auto ch : s) {
            if (ch == '(' || ch == '[' || ch == '{') {
                p.push(ch);
            } else {
                char check = ch == ')' ? '(' : (ch == ']' ? '[' : '{');
                if (p.empty() || p.top() != check) {
                    return false;
                } else {
                    p.pop();
                }
            }
        }
        return p.empty();
    }
};

Length of Last Word (easy)

// Runtime: 0ms, beat 99.33%
class Solution {
public:
    int lengthOfLastWord(string s) {
        int len = 0;
        for (int i = (int)s.length() - 1; i >= 0; i--) {
            if (s[i] != ' ') {
                len++;
            } else if (len > 0) {
                break;
            }
        }
        return len;
    }
};

Design Twitter (medium)

// Runtime: 72ms, beat 89.48%
class Twitter {
private:
    struct Tweet{
        int tweetId;
        unsigned int timestamp;
        Tweet* next;
        Tweet(int tweetId, unsigned int timestamp, Tweet* next) : tweetId(tweetId), timestamp(timestamp), next(next) {}
    };
    unsigned int num_users {0};
    unordered_map<int, unsigned int> userNewId;  // map user id to consequtive ids
    vector<unordered_set<unsigned int>> followSet;  // use the new id
    vector<Tweet*> tweets;

    unsigned int getNewUserId(int userId) {
        auto itr = userNewId.find(userId);
        if (itr == userNewId.end()) {
            // user not found
            userNewId[userId] = num_users++;
            followSet.push_back(unordered_set<unsigned int>({num_users-1}));  // follow herself
            tweets.push_back(new Tweet(0, 0, NULL));  // dummy head
            return num_users - 1;
        } else {
            return itr->second;
        }
    }

public:
    /** Initialize your data structure here. */
    Twitter() {

    }

    ~Twitter() {
        for (int i = 0; i < num_users; i++) {
            Tweet* crt = tweets[i];
            while (crt != NULL) {
                Tweet* nxt = crt->next;
                delete crt;
                crt = nxt;
            }
        }
    }

    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        static unsigned int timer = 0;
        userId = getNewUserId(userId);
        Tweet* new_tweet = new Tweet(tweetId, timer++, tweets[userId]->next);
        tweets[userId]->next = new_tweet;
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    vector<int> getNewsFeed(int userId) {
        unsigned int id = getNewUserId(userId);
        auto compare = [](const Tweet* a, const Tweet* b) -> bool {return a->timestamp < b->timestamp;};
        priority_queue<Tweet*, vector<Tweet*>, decltype(compare)> top10(compare);
        // initialize the priority_queue
        for (auto watch : followSet[id]) {
            if (tweets[watch]->next != NULL) {
                top10.push(tweets[watch]->next);
            }
        }
        vector<int> ret;
        while (ret.size() < 10 && !top10.empty()) {
            ret.push_back(top10.top()->tweetId);
            Tweet* nxt = top10.top()->next;
            top10.pop();
            if (nxt != NULL) {
                top10.push(nxt);
            }
        }
        return ret;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            unsigned int id1 = getNewUserId(followerId);
            unsigned int id2 = getNewUserId(followeeId);
            followSet[id1].insert(id2);
        }
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            unsigned int id1 = getNewUserId(followerId);
            unsigned int id2 = getNewUserId(followeeId);
            followSet[id1].erase(id2);
        }
    }
};

/**
  * Your Twitter object will be instantiated and called as such:
  * Twitter obj = new Twitter();
  * obj.postTweet(userId,tweetId);
  * vector<int> param_2 = obj.getNewsFeed(userId);
  * obj.follow(followerId,followeeId);
  * obj.unfollow(followerId,followeeId);
  */

Peeking Iterator (medium)

// Runtime: 4ms, beat 2.97%
// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {
    struct Data;
    Data* data;
public:
    Iterator(const vector<int>& nums);
    Iterator(const Iterator& iter);
    virtual ~Iterator();
    // Returns the next element in the iteration.
    int next();
    // Returns true if the iteration has more elements.
    bool hasNext() const;
};


class PeekingIterator : public Iterator {
private:
    int peek_result;
    bool has_peeked;
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        // Initialize any member here.
        // **DO NOT** save a copy of nums and manipulate it directly.
        // You should only use the Iterator interface methods.
        // peek the next one
        if (has_peeked = Iterator::hasNext()) {
            peek_result = Iterator::next();
        }
    }

    // Returns the next element in the iteration without advancing the iterator.
    int peek() {
        return peek_result;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    int next() {
        int ret = peek_result;
        // peek the next one
        if (has_peeked = Iterator::hasNext()) {
            peek_result = Iterator::next();
        }
        return ret;
    }

    bool hasNext() const {
        return has_peeked;
    }
};

Binary Search Tree Iterator (medium)

// Runtime: 28ms, beat 15.69%
/**
  * Definition for binary tree
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class BSTIterator {
private:
    stack<TreeNode*> s;
public:
    BSTIterator(TreeNode *root) {
        while (root != NULL) {
            s.push(root);
            root = root->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *ret = s.top();
        s.pop();
        TreeNode *crt = ret->right;
        while (crt != NULL) {
            s.push(crt);
            crt = crt->left;
        }
        return ret->val;
    }
};
/**
  * Your BSTIterator will be called like this:
  * BSTIterator i = BSTIterator(root);
  * while (i.hasNext()) cout << i.next();
  */

A faster but longer implementation: use a fixed length vector as the stack.

// Runtime: 24ms, beat 80.09%
/**
  * Definition for binary tree
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class BSTIterator {
private:
    vector<TreeNode*> s;  // stack
    int s_top;  //s stack top
    static int height(TreeNode *root) {
        return root == NULL ? 0 : max(height(root->left), height(root->right)) + 1;
    }
public:
    BSTIterator(TreeNode *root) {
        s.resize(height(root));
        s_top = 0;
        while (root != NULL) {
            s[s_top++] = root;
            root = root->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return s_top != 0;
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *ret = s[--s_top];
        TreeNode *crt = ret->right;
        while (crt != NULL) {
            s[s_top++] = crt;
            crt = crt->left;
        }
        return ret->val;
    }
};

/**
  * Your BSTIterator will be called like this:
  * BSTIterator i = BSTIterator(root);
  * while (i.hasNext()) cout << i.next();
  */

Wiggle Subsequence (medium)

// Runtime: 0ms
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int up = nums[0], up_cnt = 1;
        int down = nums[0], down_cnt = 1;
        for (int i = 1; i < nums.size(); i++) {
            // new up: up -> new up / down -> new up
            int new_up = max(up, nums[i]), new_up_cnt = up_cnt;
            if (nums[i] > down && down_cnt + 1 > new_up_cnt) {
                new_up = nums[i];
                new_up_cnt = down_cnt + 1;
            }
            // new down: down -> new down / up -> new down
            int new_down = min(down, nums[i]), new_down_cnt = down_cnt;
            if (nums[i] < up && up_cnt + 1 > new_down_cnt) {
                new_down_cnt = up_cnt + 1;
                new_down = nums[i];
            }
            // move on
            up = new_up;
            up_cnt = new_up_cnt;
            down = new_down;
            down_cnt = new_down_cnt;
        }
        return max(up_cnt, down_cnt);
    }
};

July 28, 2016

Game of Life (medium)

Solution

• First pass: use one bit to keep the new status.
• Second pass: update status

// Runtime: 3ms, beat 27.28%
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        if (board.empty() || board[0].empty()) return;

        static const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
        static const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        int n = board.size(), m = board[0].size();
        // first pass
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int live_neighbor = 0;
                for (int k = 0; k < 8; k++) {
                    int ii = i + dx[k], jj = j + dy[k];
                    if (ii >= 0 && jj >= 0 && ii < n && jj < m) {
                        live_neighbor += (board[ii][jj] & 1) > 0;
                    }
                }
                if (board[i][j] == 1) {
                    if (live_neighbor == 2 || live_neighbor == 3) {
                        board[i][j] |= 2;  // live in the next step
                    }
                } else {
                    if (live_neighbor == 3) {
                        board[i][j] |= 2;
                    }
                }
            }
        }
        // second pass
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] >>= 1;
            }
        }
    }
};

Container With Most Water (medium)

// Runtime: 28ms, beat 11.36%
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_area = 0;
        int i = 0, j = -1 + height.size();
        while (i < j) {
            if (height[i] <= height[j]) {
                max_area = max(max_area, height[i] * (j - i));
                i++;
            } else {
                max_area = max(max_area, height[j] * (j - i));
                j--;
            }
        }
        return max_area;
    }
};

Sort Colors (medium)

Notes

• Cannot swap two while!!!!!!!!

// Runtime: 4ms, beat 13.60%
class Solution {
public:
    void sortColors(vector<int>& nums) {
        for (int i = 0, nxt_zero = 0, nxt_two = nums.size() - 1; i <= nxt_two; i++) {
            while (nums[i] == 2 && i < nxt_two) swap(nums[nxt_two--], nums[i]);
            while (nums[i] == 0 && i > nxt_zero) swap(nums[nxt_zero++], nums[i]);
        }
    }
};

Kth Largest Element in an Array (medium)

// Runtime: 12ms, beat 87.53%
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        k--;
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int rand_pos = rand() % (right - left + 1) + left;
            int pivot = nums[rand_pos];
            swap(nums[rand_pos], nums[right]);
            int i = left - 1, j = left;
            while (j < right) {
                if (nums[j] > pivot) {
                    swap(nums[++i], nums[j]);
                }
                j++;
            }
            swap(nums[++i], nums[right]);
            if (i == k) {
                return nums[i];
            } else if (i < k) {
                left = i + 1;
            } else {
                right = i - 1;
            }
        }
        return nums[left];
    }
};

Search in Rotated Sorted Array II (medium)

// Runtime: 8ms, beat 27.64%
class Solution {
private:
    bool binSearch(vector<int> &nums, int target, int l, int r) {
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return false;
    }
public:
    bool search(vector<int>& nums, int target) {
        if (nums.empty()) return false;
        if (nums.front() < nums.back()) {
            // sorted
            return binSearch(nums, target, 0, nums.size() - 1);
        }
        int l = 0, r = nums.size() - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == nums[l]) {
                l++;
            } else if (nums[mid]  < nums[l]) {
                r = mid;
            } else {
                l = mid;
            }
        }
        int min_idx = nums[l] < nums[r] ? l : r;
        if (target < nums[min_idx]) {
            return false;
        } else {
            return binSearch(nums, target, 0, min_idx - 1) || binSearch(nums, target, min_idx, nums.size() - 1);
        }
    }
};

Unique Binary Search Trees II (medium)

First implementation, O(2^n).

// Runtime: 52ms, beat 0.67%

/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    // search for all possible trees
    vector<TreeNode*> generateTreesHelper(int left, int right) {
        vector<TreeNode*> result;
        if (left > right) {
            result.push_back(NULL);
        } else {
            for (int mid = left; mid <= right; mid++) {
                for (TreeNode* ptr_left: generateTreesHelper(left, mid - 1)) {
                    for (TreeNode* ptr_right: generateTreesHelper(mid + 1, right)) {
                        TreeNode* root = new TreeNode(mid);
                        root->left = ptr_left;
                        root->right = ptr_right;
                        result.push_back(root);
                    }
                }
            }
        }
        return result;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        return n == 0 ? vector<TreeNode*>() : generateTreesHelper(1, n);
    }
};

Optimized a little bit..

// Runtime: 24ms, beat 39.22%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    // search for all possible trees
    vector<TreeNode*> generateTreesHelper(int left, int right) {
        vector<TreeNode*> result;
        if (left == right) {
            result.push_back(new TreeNode(left));
        } else {
            for (TreeNode* ptr_right: generateTreesHelper(left + 1, right)) {
                TreeNode* root = new TreeNode(left);
                root->right = ptr_right;
                result.push_back(root);
            }
            for (TreeNode* ptr_left: generateTreesHelper(left, right - 1)) {
                TreeNode* root = new TreeNode(right);
                root->left = ptr_left;
                result.push_back(root);
            }
            for (int mid = left + 1; mid <= right - 1; mid++) {
                for (TreeNode* ptr_left: generateTreesHelper(left, mid - 1)) {
                    for (TreeNode* ptr_right: generateTreesHelper(mid + 1, right)) {
                        TreeNode* root = new TreeNode(mid);
                        root->left = ptr_left;
                        root->right = ptr_right;
                        result.push_back(root);
                    }
                }
            }
        }
        return result;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        return n == 0 ? vector<TreeNode*>() : generateTreesHelper(1, n);
    }
};

Different Ways to Add Parentheses (medium)

First implementation, parse the string first

// Runtime: 12ms, beat 3.62%
class Solution {
private:
    vector<int> diffWaysToComputeHelper(const vector<int> &val, const vector<char> &op, int first_op, int last_op) {
        if (first_op > last_op) {
            return vector<int>(1, val[first_op]);
        }
        vector<int> r;
        for (int i = first_op; i <= last_op; i++) {
            for (int a : diffWaysToComputeHelper(val, op, first_op, i-1)) {
                for (int b : diffWaysToComputeHelper(val, op, i+1, last_op)) {
                    r.push_back(op[i] == '*' ? a * b: (op[i] == '+' ? a + b : a - b));
                }
            }
        }
        return r;
    }
public:
    vector<int> diffWaysToCompute(string input) {
        // parse the string
        vector<int> val;
        vector<char> op;
        int crt_val = 0;
        for (auto ch : input) {
            if (isdigit(ch)) {
                crt_val = crt_val * 10 + ch - '0';
            } else {
                // symbol, the previous char must be a digit
                val.push_back(crt_val);
                crt_val = 0;
                op.push_back(ch);
            }
        }
        val.push_back(crt_val);
        // get all results
        return diffWaysToComputeHelper(val, op, 0, (int)op.size() - 1);
    }
};

Second implementation, do not parse the string in advance.

// Runtime: 8ms, beat 11.14%
class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> result;
        size_t i = input.find_first_of("+-*");
        while (i != string::npos) {
            for (int a : diffWaysToCompute(input.substr(0, i))) {
                for (int b : diffWaysToCompute(input.substr(i+1))) {
                    result.push_back(input[i] == '*' ? a * b : (input[i] == '+' ? a + b : a - b));
                }
            }
            i = input.find_first_of("+-*", i + 1);
        }
        if (result.empty()) {
            result.push_back(stoi(input));
        }
        return result;
    }
};

Search a 2D Matrix II (medium)

// Runtime: 208ms, beat 54.66%
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) return false;
        int n = matrix.size();
        int i = 0, j = (int)matrix[0].size() - 1;
        while (i < n && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;  // won't find in this row
            } else {
                j--;  // won't find in this column
            }
        }
        return false;
    }
};

Search a 2D Matrix (medium)

// Runtime: 12ms, beat 26.53%
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int x = mid / m, y = mid % m;
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return false;
    }
};

July 27, 2016

Super Ugly Number (medium)

// Runtime: 145ms, beat 45.01%
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {

        vector<int> f(n, INT_MAX);
        int k = primes.size();
        vector<int> idx(k, 0);

        f[0] = 1;
        for (int i = 1; i <n; i++) {
            for (int j = 0; j < k; j++) {
                f[i] = min(f[i], f[idx[j]] * primes[j]);
            }
            for (int j = 0; j < k; j++) {
                if (f[i] == f[idx[j]] * primes[j]) {
                    idx[j]++;
                }
            }
        }

        return f.back();
    }
};

Increasing Triplet Subsequence (medium)

// Runtime: 8ms, beat 20.56%
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int len1 = INT_MAX, len2 = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]  > len2) {
                return true;
            } else if (nums[i] > len1) {
                len2 = min(len2, nums[i]);
            } else {
                len1 = nums[i];
            }
        }
        return false;
    }
};

July 26, 2016

Flatten Binary Tree to Linked List (medium)

// Runtime: 8ms, beat 24.96%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    // return the tail
    TreeNode* flattenHelper(TreeNode *root) {
        if (root == NULL) {
            return NULL;
        }
        TreeNode* left_tail = flattenHelper(root->left);
        TreeNode* right_tail = flattenHelper(root->right);
        if (root->left != NULL && root->right != NULL) {
            TreeNode* bak_prev_right = root->right;
            root->right = root->left;
            root->left = NULL;
            left_tail->right = bak_prev_right;
            return right_tail;
        } else if (root->left != NULL && root->right == NULL) {
            root->right = root->left;
            root->left = NULL;
            return left_tail;
        } else if (root->left == NULL && root->right != NULL) {
            return right_tail;
        } else {
            return root;  // leaf
        }
    }
public:
    void flatten(TreeNode* root) {
        flattenHelper(root);
    }
};

Verify Preorder Serialization of a Binary Tree (medium)

Notes

• If we see a non-leaf node, we are expecting to see two more nodes in the future.

// Runtime: 4ms, beat 70.41%
class Solution {
public:
    bool isValidSerialization(string preorder) {
        int i = 0, len = preorder.length();
        int capacity = 1;  // for the root
        while (i < len && capacity > 0) {
            capacity--;
            if (preorder[i] != '#') {
                capacity+=2;  // for two future leaves
                while (i < len && preorder[i] != ',') i++;
                i++;
            } else {
                i += 2;
            }
        }
        return i >= len && capacity == 0;
    }
};

Sum Root to Leaf Numbers (medium)

// Runtime: 4ms, beat 11.58%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    void sumNumbersHelper(TreeNode* crt, int parent_value, int &result) {
        if (crt != NULL) {
            parent_value = parent_value * 10 + crt->val;
            if (crt->left != NULL || crt->right != NULL) {
                sumNumbersHelper(crt->left, parent_value, result);
                sumNumbersHelper(crt->right, parent_value, result);
            } else {
                result += parent_value;
            }
        }
    }
public:
    int sumNumbers(TreeNode* root) {
        int result = 0;
        sumNumbersHelper(root, 0, result);
        return result;
    }
};

Maximum Subarray (medium)

// Runtime: 8ms, beat 74.15%
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = nums[0];
        int sum = nums[0];
        int min_sum = sum < 0 ? sum : 0;
        for (int i = 1; i < nums.size(); i++) {
            sum += nums[i];
            result = max(result, sum - min_sum);
            min_sum = min(min_sum, sum);
        }
        return result;
    }
};

Combination Sum IV (medium)

DP

// Runtime: 4ms, beat ??%
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* head1 = new ListNode(0), *tail1 = head1;
        ListNode* head2 = new ListNode(0), *tail2 = head2;
        while (head != NULL) {
            if (head->val < x) {
                tail1->next = head;
                tail1 = tail1->next;
            } else {
                tail2->next = head;
                tail2 = tail2->next;
            }
            head = head->next;
        }
        tail1->next = head2->next;
        tail2->next = NULL;
        // clear
        ListNode *ret = head1->next;
        delete head1;
        delete head2;
        return ret;
    }
};

Triangle (medium)

// Runtime: 8ms, beat 16.07%
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int num_row = triangle.size();
        vector<int> temp(triangle.back());  // last row
        for (int row = num_row - 2; row >= 0; row--) {
            for (int i = 0; i <= row; i++) {
                temp[i] = triangle[row][i] + min(temp[i], temp[i+1]);
            }
        }
        return temp[0];
    }
};

Ugly Number II (medium)

Dynamic programming

// Runtime: 16ms, beat 61.32%
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> ugly(n, 0);
        ugly[0] = 1;
        int mul2 = 0, mul3 = 0, mul5 = 0;
        for (int i = 1; i < n; i++) {
            ugly[i] = min(ugly[mul2]*2, min(ugly[mul3]*3, ugly[mul5]*5));
            if (ugly[i] == ugly[mul2] * 2) {
                mul2++;
            }
            if (ugly[i] == ugly[mul3] * 3) {
                mul3++;
            }
            if (ugly[i] == ugly[mul5] * 5) {
                mul5++;
            }
        }
        return ugly.back();
    }
};

Delete Node in a Linked List (easy)

// Runtime: 16ms, beat 15.47%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        ListNode* rm = node->next;
        node->next = node->next->next;
        delete rm;
    }
};

Move Zeroes (easy)

// Runtime: 20ms, beat 27.77%
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int last_zero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                nums[last_zero++] = nums[i];
            }
        }
        fill(nums.begin() + last_zero, nums.end(), 0);
    }
};

Remove Element (easy)

// Runtime: 4ms, beat 14.16%
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int new_size = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[new_size++] = nums[i];
            }
        }
        return new_size;
    }
};

Populating Next Right Pointers in Each Node II :hard:

// Runtime: 36ms, beat 78.42%
/**
  * Definition for binary tree with next pointer.
  * struct TreeLinkNode {
  *  int val;
  *  TreeLinkNode *left, *right, *next;
  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
  * };
  */
class Solution {
private:
      void GetFirstNonleaf(TreeLinkNode *&crt, TreeLinkNode *&child) {
        while (crt != NULL) {
            if (crt->left != NULL) {
                child = crt->left;
                break;
            }
            if (crt->right != NULL) {
                child = crt->right;
                break;
            }
            crt = crt->next;
        }
    }
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) return;
        TreeLinkNode *crt = root;
        // while we can find a non-leaf node in the next level
        while (crt != NULL) {
            // find the leftmost node of the next level
            TreeLinkNode *nxt_leftmost = NULL;
            GetFirstNonleaf(crt, nxt_leftmost);
            // link the nodes in the next level
            while (crt != NULL) {
                // find the next non-leaf node in this level
                TreeLinkNode *nxt = crt->next, *nxt_first_son = NULL;
                GetFirstNonleaf(nxt, nxt_first_son);
                if (crt->left != NULL) {
                    if (crt->right != NULL) {
                        crt->left->next = crt->right;
                        crt->right->next = nxt_first_son;
                    } else {
                        crt->left->next = nxt_first_son;
                    }
                } else {
                    crt->right->next = nxt_first_son;
                }
                crt = nxt;
            }
            crt = nxt_leftmost;
        }
    }
};

Populating Next Right Pointers in Each Node (medium)

// Runtime: 24ms, beat 50.20%
/**
  * Definition for binary tree with next pointer.
  * struct TreeLinkNode {
  *  int val;
  *  TreeLinkNode *left, *right, *next;
  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
  * };
  */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) return;

        TreeLinkNode *crt = root;
        while (crt->left != NULL) {
            TreeLinkNode *nxt_leftmost = crt->left;
            while (true) {
                crt->left->next = crt->right;
                if (crt->next != NULL) {
                    crt->right->next = crt->next->left;
                    crt = crt->next;
                } else {
                    break;
                }
            }
            crt = nxt_leftmost;
        }
    }
};

Find Peak Element (medium)

Binary search.

// Runtime: 4ms, beat 69.74%
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == left || nums[mid] > nums[mid-1]) {
                // mid > its left side
                if (mid == right || nums[mid] > nums[mid+1]) {
                    // mid > its right side
                    return mid;
                } else {
                    left = mid + 1;
                }
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

Same Tree (easy)

// Runtime: 12ms, beat 17.62%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL || q == NULL) return p == q;
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Valid Anagram (easy)

// Runtime: 12ms, beat 65.57%
class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> cnt(26, 0);
        for (auto ch: s) {
            cnt[ch-'a']++;
        }
        for (auto ch : t) {
            cnt[ch-'a']--;
        }
        for (auto c : cnt) {
            if (c != 0) return false;
        }
        return true;
    }
};

July 25, 2016

Lowest Common Ancestor of a Binary Tree (medium)

// Runtime: 27ms, beat 40.83%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    // 0: not found, 1: find p, 2: find q, 3: find both
    int lowestCommonAncestorHelper(TreeNode* root, TreeNode *p, TreeNode *q, TreeNode *&result) {
        if (result != NULL || root == NULL) return 0;  // no need to search
        int crt_status = ((root == p) ? 1 : 0) + ((root == q) ? 2 : 0);
        int left_status = lowestCommonAncestorHelper(root->left, p, q, result);
        int right_status = lowestCommonAncestorHelper(root->right, p, q, result);
        int subtree_status = crt_status + left_status + right_status;
        if (subtree_status == 3 && result == NULL) {
            result = root;
        }
        return subtree_status;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* result = NULL;
        lowestCommonAncestorHelper(root, p, q, result);
        return result;
    }
};

Contains Duplicate II (easy)

// Runtime: 32ms, beat 49.89%
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) s.erase(nums[i-k-1]);
            if (s.find(nums[i]) != s.end()) return true;
            s.insert(nums[i]);
        }
        return false;
    }
};

Contains Duplicate (easy)

An awesome one-line code from the discussion board.

// Runtime: 48ms, beat 54.45%
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        return nums.size() > (unordered_set<int>(nums.begin(), nums.end())).size();
    }
};

Contains Duplicate III (medium)

Notes

• OK: m.lower_bound(value)

// Runtime: 48ms, beat 36%
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        map<long long, int> m;// value, latest position
        for (int i = 0; i < nums.size(); i++) {
            // if necessary, increase i to make sure that j - i <= k
            if (i > k) {
                auto itr = m.find(nums[i-k-1]);
                if (itr != m.end() && itr->second == i-k-1) {
                    m.erase(itr);
                }
            }
            // test
            auto itr = m.lower_bound((long long)nums[i] - t);
            if (itr != m.end() && itr->first <= (long long)nums[i] + t) {
                return true;
            }
            // add nums[i] to the map
            m[nums[i]] = i;
        }
        return false;
    }
};

Kth Largest Element in an Array (medium)

Notes

• Modify k: 1st largest, k=0!!!!!!!!

// Runtime: 12ms, beat 82.53%
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        k--;
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int rand_pos = rand() % (right - left + 1) + left;
            int pivot = nums[rand_pos];
            swap(nums[rand_pos], nums[right]);
            int i = left - 1, j = left;
            while (j < right) {
                if (nums[j] > pivot) {
                    swap(nums[++i], nums[j]);
                }
                j++;
            }
            swap(nums[++i], nums[right]);
            if (i == k) {
                return nums[i];
            } else if (i < k) {
                left = i + 1;
            } else {
                right = i - 1;
            }
        }
        return nums[left];
    }
};

Binary Tree Zigzag Level Order Traversal (medium)

// Runtime: 4ms, beat 17%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        stack<TreeNode*> crt, nxt;
        if (root) {
            crt.push(root);
        }
        bool left_right = true;
        while (!crt.empty()) {
            result.push_back(vector<int>());
            while (!crt.empty()) {
                TreeNode *ptr = crt.top();
                crt.pop();
                result.back().push_back(ptr->val);
                if (left_right) {
                    if (ptr->left) nxt.push(ptr->left);
                    if (ptr->right) nxt.push(ptr->right);
                } else {
                    if (ptr->right) nxt.push(ptr->right);
                    if (ptr->left) nxt.push(ptr->left);
                }
            }
            crt.swap(nxt);
            left_right = !left_right;
        }
        return result;
    }
};

Pow(x, n) (medium)

Be careful of the possible overflow while writing n=-n.

// Runtime: 4ms, beat 19.88%
class Solution {
public:
    double myPow(double x, int n) {
        if (x == 0.0) return 0.0;
        double result = 1.0;
        long long nn = n;
        if (nn < 0) {
            x = 1 / x;
            nn = -nn;
        }
        while (nn > 0) {
            if (nn & 1) result*=x;
            nn >>= 1;
            x*=x;
        }
        return result;
    }
};

Group Anagrams (medium)

// Runtime: 64ms, beat 86.22%
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, int> m;  // sorted_string -> result id
        vector<vector<string>> result;
        for (const auto &str : strs) {
            string tmp{str};
            sort(tmp.begin(), tmp.end());
            auto itr = m.find(tmp);
            if (itr != m.end()) {
                result[itr->second].push_back(str);
            } else {
                m[tmp] = result.size();
                result.push_back(vector<string>(1, str));
            }
        }
        return result;
    }
};

Decode Ways (medium)

Dynamic programming.

// Runtime: 4ms, beat 14.34%
class Solution {
public:
    int numDecodings(string s) {
        // corner cases
        if (s.empty() || s[0] == '0') return 0;
        // init
        vector<int> f(s.length() + 1, 0);
        f[0] = 1;
        // dp
        for (int j = 1; j <= s.length(); j++) {
            f[j] = (s[j-1] == '0') ? 0 : f[j-1];
            if (j >= 2 && (s[j-2] == '1' || (s[j-2] == '2' && s[j-1] <= '6'))) {
                f[j] += f[j-2];
            }
        }
        return f.back();
    }
};

4Sum (medium)

First implementation, O(n^3), an extension of the solution to the 3Sum problem.

// Runtime: 93ms, beat 51.11%
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // prepare
        sort(nums.begin(), nums.end());
        // solve
        vector<vector<int>> results;
        vector<int> temp(4);
        int n = nums.size();
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            temp[0] = nums[i];
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j-1]) continue;
                temp[1] = nums[j];
                int l = j + 1, r = n - 1;
                int target2 = target - nums[i] - nums[j];
                while (l < r) {
                    if (l > j + 1 && nums[l] == nums[l-1]) {
                        l++;
                        continue;
                    }
                    int sum2 =  nums[l] + nums[r];
                    if (sum2 > target2) {
                        r--;
                    } else if (sum2 < target2) {
                        l++;
                    } else {
                        temp[2] = nums[l++];
                        temp[3] = nums[r--];
                        results.push_back(temp);
                    }
                }
            }

        }
        return results;

    }
};

(Will work on the O(nlogn) implementation later.)

3Sum (medium)

// Runtime: 56ms, beat 54.56%
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // prepare
        sort(nums.begin(), nums.end());
        // solve
        vector<vector<int>> results;
        vector<int> temp(3);
        for (int i = 0; i + 2< nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            temp[0] = nums[i];
            int target = -nums[i];
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                if (l > i + 1 && nums[l] == nums[l-1]) {
                    l++;
                    continue;
                }
                if (nums[l] + nums[r] > target) {
                    r--;
                } else if (nums[l] + nums[r] < target) {
                    l++;
                } else {
                    temp[1] = nums[l++];
                    temp[2] = nums[r--];
                    results.push_back(temp);
                }
            }
        }
        return results;
    }
};

Remove Duplicates from Sorted List II (medium)

// Runtime: 12ms, beat 10.02%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *super_head = new ListNode(0);
        super_head->next = head;

        ListNode *ptr = super_head;
        while (ptr != NULL) {
            // chech whether we want to remove the next node
            if (ptr->next != NULL && ptr->next->next != NULL && ptr->next->val == ptr->next->next->val) {
                int target = ptr->next->val;
                while (ptr->next != NULL && ptr->next->val == target) {
                    ptr->next = ptr->next->next;
                }
            } else {
                ptr = ptr->next;
            }
        }

        ListNode* result = super_head->next;
        delete super_head;
        return result;
    }
};

Divide Two Integers (medium)

// Runtime: 12ms, beat 9.72%
class Solution {
public:
    int divide(int dividend, int divisor) {
        // overflow cases
        if (!divisor || (dividend == INT_MIN && divisor == -1)) {
            return INT_MAX;
        }
        // normal cases
        int sign = (dividend > 0 ^ divisor > 0) ? -1 : 1;
        long long a = labs(dividend), b = labs(divisor);
        int result = 0;
        while (a >= b) {
            long long i = 1;
            long long tmp = b;
            while (a >= tmp) {
                tmp <<= 1;
                i <<= 1;
            }
            tmp >>= 1;
            i >>= 1;
            result += i;
            a -= tmp;
        }
        return sign * result;
    }
};

Fraction to Recurring Decimal (medium)

// Runtime: 4ms, beat 8%
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";

        string result = "";
        if (numerator < 0 ^ denominator < 0) {
            result += "-";
        }
        long a = numerator, b = denominator;
        a = a > 0 ? a : (-a);
        b = b > 0 ? b : (-b);
        result += to_string(a/b);
        long rmd = a % b;

        if (rmd > 0) {
            result += ".";
        }
        unordered_map<long, long> m;  // rmd -> pos
        while (rmd) {
            rmd *= 10;
            int quotient = rmd / b;
            if (m.find(rmd) != m.end()) {
                result.insert(m[rmd], 1, '(');
                result += ")";
                break;
            }
            m[rmd] = result.length();
            result += to_string(quotient);
            rmd = rmd % b;
        }

        return result;
    }
}


## Linked List Cycle II     (medium)

Notes

-   HEAD  &#x2013;(length a) &#x2013; First node in the cycle &#x2013; (length b) &#x2013; Fast&Slow pointers meet here (length c) &#x2013; First node in the cycle
-   Slow: a+b
-   Fast: a+b+c+b
-   2slow = fast -> a=c

```c++
// Runtime: 12ms, beat 30.09%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return NULL;
        }
        ListNode *fast = head->next->next, *slow = head->next;
        while (fast != NULL && fast != slow) {
            fast = fast->next;
            if (fast == NULL) return NULL;
            fast = fast->next;
            slow = slow->next;
        }
        if (fast == NULL) {
            return NULL;
        } else {
            fast = head;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    }
};

Convert Sorted List to Binary Search Tree (medium)

Notes

• Get the length of the sorted list.
• Use a reference of pointer (ListNode *&head) to keep track of the current list node.

// Runtime: 28ms, beat 66.89%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    int getListLen(ListNode* head) {
        int len = 0;
        while (head != NULL) {
            head = head->next;
            len++;
        }
        return len;
    }
    TreeNode* sortedListToBSTHelper(ListNode *&head, int start, int end) {
        if (start > end) return NULL;
        int mid = start + (end - start) / 2;
        TreeNode* crt_node = new TreeNode(0);
        crt_node->left = sortedListToBSTHelper(head, start, mid - 1);
        crt_node->val = head->val;
        head = head->next;
        crt_node->right = sortedListToBSTHelper(head, mid + 1, end);
        return crt_node;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int list_len = getListLen(head);
        return sortedListToBSTHelper(head, 0, list_len-1);
    }
};

Reverse Linked List II (medium)

// Runtime: 4ms, beat 4.97%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *super_head = new ListNode(0);
        super_head->next = head;
        // find the node at position m-1
        ListNode *before_reverse = super_head;
        for (int i = 1; i < m; i++) {
            before_reverse = before_reverse->next;
        }
        // reverse
        ListNode *reverse_tail = before_reverse->next;
        ListNode *ptr = reverse_tail->next;
        for (int i = 0; i < n - m; i++) {
            ListNode *bak = ptr->next;
            ptr->next = before_reverse->next;
            before_reverse->next = ptr;
            ptr = bak;
        }
        reverse_tail->next = ptr;
        // return
        ListNode *result = super_head->next;
        delete super_head;
        return result;
    }
};

Palindrome Partitioning II :hard:

// Runtime: 24ms, beat 73.17%
class Solution {
public:
    int minCut(string s) {
        int n = s.length();
        bool is_pal[n][n];
        int min_cut[n+1];
        min_cut[0] = -1;
        for (int right = 0; right < n; right++) {
            min_cut[right + 1] = right;
            for (int left = 0; left <= right; left++) {
                if (s[left] == s[right] && (right - left < 2 || is_pal[left+1][right-1])) {
                    is_pal[left][right] = true;
                    min_cut[right + 1] = min(min_cut[right + 1], 1 + min_cut[left]);
                } else {
                    is_pal[left][right] = false;
                }
            }
        }
        return min_cut[n];
    }
};

Palindrome Partitioning (medium)

// Runtime: 16ms, beat 62.76%
class Solution {
private:
    void dfs(int pos, string s, const vector<vector<bool>> &is_pal, vector<string> &temp, vector<vector<string>> &result) {
        if (pos == s.length()) {
            result.push_back(temp);
        } else {
            for (int last_char = pos; last_char < s.length(); last_char++) {
                if (is_pal[pos][last_char]) {
                    temp.push_back(s.substr(pos, last_char - pos + 1));
                    dfs(last_char + 1, s, is_pal, temp, result);
                    temp.pop_back();
                }
            }
        }
    }
public:
    vector<vector<string>> partition(string s) {
        int n = s.length();
        vector<vector<bool>> is_pal(n, vector<bool>(n, true));
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                is_pal[i][j] = (s[i] == s[j]) && (len == 2 || is_pal[i+1][j-1]);
            }
        }
        vector<vector<string>> result;
        vector<string> temp;
        dfs(0, s, is_pal, temp, result);
        return result;
    }
};

July 24, 2016

Combinations (medium)

// Runtime: 88ms, beat 91.14%
class Solution {
private:
void dfs(int k, int pos, int first_num, int last_num, vector<int> &temp, vector<vector<int>> &result) {
    if (pos == k) {
        result.push_back(temp);
    } else {
        for (int i = first_num; i <= last_num - (k - pos) + 1; i++) {
            temp[pos] = i;
            dfs(k, pos+1, i+1, last_num, temp, result);
        }
    }
}
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> temp(k, 0);
        dfs(k, 0, 1, n, temp, result);
        return result;
    }
};

Permutation Sequence (medium)

// Runtime: 3ms, beat 48.69%
class Solution {
public:
    string getPermutation(int n, int k) {
        // init
        vector<int> used(n, false);
        int n_fact = 1;
        for (int i = 1; i <= n; i++) {
            n_fact *= i;
        }
        // fill the result char by char
        k--;  // n=3, k=1->k=0, return "123"
        string str;
        for (int pos = n; pos >= 1; pos--) {
            n_fact /= pos;
            for (int i = 0, unused = -1; i < n; i++) {
                if (used[i]) continue;
                unused++;
                if (unused == k / n_fact) {
                    str.append(1, '0' + i + 1);
                    used[i] = true;
                }
            }
            k %= n_fact;
        }
        return str;
    }
};

Permutations II (medium)

// Runtime: 60mb, beat 5.67%
class Solution {
private:
    void dfs(int n, int pos, vector<int> nums, vector<vector<int>> &result) {
        if (pos == n - 1) {
            result.push_back(nums);
        } else {
            for (int i = pos; i < n; i++) {
                if (i == pos || nums[i] != nums[pos]) {
                    swap(nums[i], nums[pos]);
                    dfs(n, pos + 1, nums, result);
                }
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        dfs(nums.size(), 0, nums, result);
        return result;
    }
};

Combination Sum II (medium)

// Runtime: 16ms, beat 41.90%
class Solution {
private:
    void dfs(int n, int pos, int goal, vector<int> &cand, vector<int> &cnt, vector<vector<int>> &result) {
        if (pos == n) {
            if (goal == 0) {
                result.push_back(vector<int>());
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < cnt[i]; j++) {
                        result.back().push_back(cand[i]);
                    }
                }
            }
        } else {
            int next = pos;
            while (next < n && cand[next] == cand[pos]) next++;
            // skip this one
            dfs(n, next, goal, cand, cnt, result);
            for (int i = 1; i <= min(next - pos, goal / cand[pos]); i++) {
                cnt[pos] = i;
                dfs(n, next, goal - i * cand[pos], cand, cnt, result);
            }
            cnt[pos] = 0;
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // sort the values
        std::sort(candidates.begin(), candidates.end());
        // prepare
        vector<vector<int>> result;
        vector<int> cnt(candidates.size(), 0);
        // search
        dfs(candidates.size(), 0, target, candidates, cnt, result);
        return result;
    }
};

Combination Sum (medium)

Notes

• Be careful when write dfs (e.g., i and the search position).

// Runtime: 20ms, beat 56.38%
class Solution {
private:
    void dfs(int n, int pos, int goal, const vector<int> &cand, vector<int> &cnt, vector<vector<int>> &result) {
        if (pos == n) {
            if (goal == 0) {
                result.push_back(vector<int>());
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < cnt[i]; j++) {
                        result.back().push_back(cand[i]);
                    }
                }
            }
        } else {
            // skip this one
            cnt[pos] = 0;
            dfs(n, pos + 1, goal, cand, cnt, result);
            // use this one
            for (int i = 1; i <= goal / cand[pos]; i++) {
                cnt[pos] = i;
                dfs(n, pos + 1, goal - i * cand[pos], cand, cnt, result);
            }
            cnt[pos] = 0;
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // remove duplicates
        sort(candidates.begin(), candidates.end());
        auto itr = unique(candidates.begin(), candidates.end());
        candidates.resize(itr - candidates.begin());
        // find the result
        vector<vector<int>> result;
        vector<int> cnt(candidates.size(), 0);
        dfs(candidates.size(), 0, target, candidates, cnt, result);
        return result;
    }
};

Guess Number Higher or Lower II (medium)

Dynamic programming

// Runtime: 64ms, beat 36.59%
class Solution {
public:
    int getMoneyAmount(int n) {
        int worst = 0;
        vector<vector<int>> f(n, vector<int>(n, 0));
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                f[i][j] = i + 1 + f[i+1][j];
                for (int x = i + 1; x <= j - 1; x++) {
                    f[i][j] = min(f[i][j], x + 1 + max(f[i][x-1], f[x+1][j]));
                }
                worst = max(worst, f[i][j]);
            }
        }
        return worst;
    }
};

Guess Number Higher or Lower (easy)

// Runtime: 0ms, beat 12.53%
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int l = 1, r = n;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int tmp = guess(mid);
            if (tmp == 0) {
                return mid;
            } else if (tmp < 0) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
};

Gray Code (medium)

// Runtime: 4ms, beat 22.89%
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        result.push_back(0);
        for (int i = 0; i < n; i++) {
            int inc = 1 << i;
            for (int j = result.size() - 1; j >= 0; j--) {
                result.push_back(result[j] + inc);
            }
        }
        return result;
    }
};

Gas Station (medium)

Greedy: O(n)

• The gas station: [0, 1, ..., n-2, n-1, 0, 1, ..., n-2, n-1, ...]
• If we cannot reach the “next station”, restart at the “next station”.
• The last possible starting gas station is n-1.
  If we are standing at the second n-2 station, and we cannot reach the nxt_station, we return -1.

// Runtime: 8ms, beat 14.53%
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int start = 0, nxt_station = 1 % n;
        int gas_tank = gas[0] - cost[0];

        for (int cnt = 0; cnt < 2 * n - 1; cnt++) {
            if (gas_tank < 0) {
                // cannot goto the next station, restart
                start = nxt_station;
                gas_tank = gas[start] - cost[start];
            } else {
                if (start == nxt_station) return start;
                gas_tank += gas[nxt_station] - cost[nxt_station];
            }
            nxt_station = (nxt_station + 1) % n;
        }

        return -1;
    }
};

Remove Duplicates from Sorted List II (medium)

// Runtime: 12ms, beat 81.03%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* ptr = head;
        while (ptr != NULL) {
            while (ptr->next != NULL && ptr->val == ptr->next->val) {
                // the next node is a duplicate node
                ptr->next = ptr->next->next;
            }
            ptr = ptr->next;
        }
        return head;
    }
};

Rotate Image (medium)

// Runtime: 4ms, beat 18.64%
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (n <= 1) return;
        // rotate
        for (int i = 0; i < n / 2; i++) {
            int row1 = i, row2 = n - i - 1;
            int col1 = i, col2 = n - i - 1;
            for (int shift = 0; shift < col2 - col1; shift++) {
                int bak = matrix[row1][col1+shift];
                matrix[row1][col1+shift] = matrix[row2-shift][col1];
                matrix[row2-shift][col1] = matrix[row2][col2-shift];
                matrix[row2][col2-shift] = matrix[row1+shift][col2];
                matrix[row1+shift][col2] = bak;
            }
        }
    }
};

Minimum Height Trees (medium)

Solution:

• Perform level-by-level BFS, from leaves to the inside nodes.
• The last level should contain one or two nodes, they are what we want.

// Runtime: 108ms, beat 68.94%
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        if (n == 1) return vector<int>(1, 0);
        // graph
        vector<unordered_set<int>> neighbors(n);
        for (auto e : edges) {
            neighbors[e.first].insert(e.second);
            neighbors[e.second].insert(e.first);
        }
        // bfs
        queue<int> q_crt, q_nxt;
        for (int i = 0; i < n; i++) {
            if (neighbors[i].size() == 1) {
                q_crt.push(i);
            }
        }
        while (n > 2) {
            while (!q_crt.empty()) {
                int u = q_crt.front();
                q_crt.pop();
                n--;
                for (auto v : neighbors[u]) {
                    neighbors[v].erase(u);
                    if (neighbors[v].size() == 1) {
                        q_nxt.push(v);
                    }
                }
            }
            q_crt.swap(q_nxt);
        }
        // result
        vector<int> result;
        while (!q_crt.empty()) {
            result.push_back(q_crt.front());
            q_crt.pop();
        }
        return result;
    }
};

July 23, 2016

Longest Increasing Subsequence (medium)

If duplicates elements are allowed in the LIS,
we should replace nums[i]>f[max_len-1] by nums[i]>=f[max_len-1],
and replace lower_bound by upper_bound.

// Runtime: 4ms, beat 62.20%
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // the corner case
        if (nums.empty()) return 0;

        int max_len = 1;
        // f[i-1]: the last element for LIS with length i
        vector<int> f(nums.size(), 0);
        f[0] = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > f[max_len - 1]) {
                f[max_len++] = nums[i];
            } else if (nums[i] < f[max_len - 1]) {
                auto itr = std::lower_bound(f.begin(), f.begin() + max_len, nums[i]);
                *itr = nums[i];
            }
        }

        return max_len;
    }
};

Permutations (medium)

DFS

// Runtime: 12ms, beat 76.80%
class Solution {
private:
    void dfs(int i, vector<int>& nums, vector<vector<int>> &result) {
        if (i == nums.size()) {
            result.push_back(nums);
        } else {
            for (int j = i; j < nums.size(); j++) {
                swap(nums[i], nums[j]);
                dfs(i+1, nums, result);
                swap(nums[i], nums[j]);
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        dfs(0, nums, result);
        return result;
    }
};

Next Permutation (medium)

Notes

• Find the largest i so that nums[i-1] < nums[i]. (e.g., 7 8 6 [9,i] 8 7 2)
• If we cannot find such an i, we sort the entire nums and return.
• Otherwise, find the smallest value nums[j] in nums[i..last] that is larger than nums[i] (e.g, 7 in the above example).
• Swap nums[i-1] and nums[j], and sort nums[i..last].

// Runtime: 12ms, beat 21.72%
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 1;
        while (i > 0 && nums[i-1] >= nums[i]) {
            i--;
        }
        if (i == 0) {
            reverse(nums.begin(), nums.end());  // == sort
        } else {
            // find the first number in nums[i..] that is larger
            int j = nums.size() - 1;
            while (nums[j] <= nums[i - 1]) {
                j--;
            }
            swap(nums[i - 1], nums[j]);
            reverse(nums.begin() + i, nums.end());  // == sort
        }
    }
};

Repeated DNA Sequences (medium)

First implementation, use an unordered_map to keep the hash values.

// Runtime: 116ms, beat 63.84%
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        // count
        unsigned int hash_value = 0;
        unordered_map<unsigned int, int> dna;  // hash -> count
        unsigned int C_mask = 1 << 18, G_mask = 2 << 18, T_mask = 3 << 18;
        vector<string> result;
        for (int i = 0; i < s.length(); i++) {
            hash_value >>= 2;
            if (s[i] == 'C') {
                hash_value |= C_mask;
            } else if (s[i] == 'G') {
                hash_value |= G_mask;
            } else if (s[i] == 'T') {
                hash_value |= T_mask;
            }
            if (i >= 9) {
                dna[hash_value]++;
                if (dna[hash_value] == 2) {
                    result.push_back(s.substr(i - 9, 10));
                }
            }
        }
        return result;
    }
};

Faster, use larger spaces to keep the hash values.

// Runtime: 12ms, beat 97.07%
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        // count
        unsigned int hash_value = 0;
        char dna[1<<21] = {0};  // hash -> count
        unsigned int C_mask = 1 << 18, G_mask = 2 << 18, T_mask = 3 << 18;
        vector<string> result;
        for (int i = 0; i < 9; i++) {
            hash_value >>= 2;
            hash_value |= s[i] == 'C' ? C_mask : (s[i] == 'G' ? G_mask : (s[i] == 'T' ? T_mask : 0));
        }
        for (int i = 9; i < s.length(); i++) {
            hash_value >>= 2;
            hash_value |= s[i] == 'C' ? C_mask : (s[i] == 'G' ? G_mask : (s[i] == 'T' ? T_mask : 0));
            if (dna[hash_value] <= 2) {
                dna[hash_value]++;  // to prevent overflow
                if (dna[hash_value] == 2) {
                    result.push_back(s.substr(i - 9, 10));
                }
            }
        }
        return result;
    }
};

Additive Number (medium)

Be careful about the length of the string when using substr.

// Runtime: 0ms
class Solution {
private:
    bool check(string str1, string str2, string str3) {
        // check the sum
        string sum = getSum(str1, str2);
        if (str3.compare(0, sum.length(), sum) != 0) {
            return false;
        }
        return sum.length() == str3.length() || check(str2, sum, str3.substr(sum.length()));
    }
    string getSum(string str1, string str2) {
        if (str1.length() < str2.length()) {
            str1.swap(str2);
        }
        // str1 is longer
        int carry = 0;
        for (int i = str1.length() - 1, j = str2.length() - 1; i >= 0; i--, j--) {
            carry += (str1[i] - '0') + (j >= 0 ? str2[j] - '0' : 0);
            str1[i] = (carry % 10) + '0';
            carry /= 10;
        }
        return carry > 0 ? "1" + str1 : str1;
    }
public:
    bool isAdditiveNumber(string num) {
        int len = num.length();
        if (len < 3) return false;
        int i_end = (num[0] == '0') ? 1 : (len / 2);
        for (int i = 1; i <= i_end; i++) {
            int j_end = (num[i] == '0') ? 1 : (len / 2);
            for (int j = 1; j <= j_end; j++) {
                if (i + j < len && check(num.substr(0, i), num.substr(i, j), num.substr(i+j))) {
                    return true;
                }
            }
        }
        return false;
    }
};

Majority Element II (medium)

// Runtime: 20ms, beat 36.68%
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if (nums.size() <= 1) return nums;

        int n1 = 0, n2 = 0, c1 = 0, c2 = 0;
        // find two integers
        for (auto value : nums) {
            if (value == n1) {
                c1++;
            } else if (value == n2) {
                c2++;
            } else if (c1 == 0) {
                n1 = value;
                c1 = 1;
            } else if (c2 == 0) {
                n2 = value;
                c2 = 1;
            } else {
                c1--;
                c2--;
            }
        }
        // check
        int true_c1 = 0, true_c2 = 0;
        for (auto value : nums) {
            if (value == n1) {
                true_c1++;
            } else if (value == n2) {
                true_c2++;
            }
        }
        // return
        vector<int> result;
        if (true_c1 > nums.size() / 3) {
            result.push_back(n1);
        }
        if (true_c2 > nums.size() / 3) {
            result.push_back(n2);
        }
        return result;
    }
};

July 22, 2016

Set Matrix Zeroes (medium)

O(1) extra space:

• Find a position (x,y) so that matrix[x][u]==0.
• If there is no such position, done.
• Use that row and column to mark rows and columns that we have to reset. Then, reset.

// Runtime: 77ms, beat 18.93%
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        // find a zero position (x, y)
        int n = matrix.size(), m = matrix[0].size();
        int x = -1, y = -1;  // x<0, not found
        for (int i = 0; i < n && x < 0; i++) {
            for (int j = 0; j < m && x < 0; j++) {
                if (matrix[i][j] == 0) {
                    x = i;
                    y = j;
                }
            }
        }
        // check
        if (x < 0) return;  // no zero elements
        // mark rows and columns that we have to reset
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    matrix[x][j] = 0;  // mark column-j
                    matrix[i][y] = 0;  // mark row-j
                }
            }
        }
        // set rows
        for (int i = 0; i < n; i++) {
            if (i != x && matrix[i][y] == 0) {
                for (int j = 0; j < m; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        // set columns
        for (int j = 0; j < m; j++) {
            if (j != y && matrix[x][j] == 0) {
                for (int i = 0; i < n; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
        // set the cross centered by (x, y)
        for (int i = 0; i < n; i++) {
            matrix[i][y] = 0;
        }
        for (int j = 0; j < m; j++) {
            matrix[x][j] = 0;
        }
    }
};

Jump Game (medium)

Greedy, keep the maximum distance that we can reach.

// Runtime: 16ms
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int stand = 0;
        for (int reach = 0; stand < n && stand <= reach; ++stand)
            reach = max(stand + nums[nums], reach);
        return stand == n;
    }
};

Unique Paths II (medium)

// Runtime: 4ms
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        int f[m];  // vector<int> f(m, 0);
        // first row
        for (int j = 0; j < m; j++) {
            f[j] = obstacleGrid[0][j] ? 0 : (j > 0 ? f[j-1] : 1);
        }
        // the remaining rows
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f[j] = obstacleGrid[i][j] ? 0 : (f[j] + (j > 0 ? f[j-1] : 0));
            }
        }
        return f[m-1];
    }
};

Minimum Path Sum (medium)

// Runtime: 12ms, beat 26.71%
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int n = grid.size(), m = grid[0].size();
        vector<int> f(m, 0);
        // first row
        for (int j = 0; j < m; j++) {
            f[j] = grid[0][j] + (j > 0 ? f[j-1] : 0);
        }
        // the remaining
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f[j] = grid[i][j] + (j == 0 ? f[j] : min(f[j], f[j-1]));
            }
        }
        return f[m-1];
    }
};

Unique Paths (medium)

// Runtime: 0ms, beat %
class Solution {
private:
    int choose(int n, int k) {
        // n! / ( k! (n - k)! )
        k = min(k, n-k);
        if (k == 0) return 1;
        double result = 1.0;
        for (int i = 1; i <= k; i++)
            result = result * (n - k + i) / i;
        return round(result);
    }
public:
    int uniquePaths(int m, int n) {
        // down m-1 times, right n-1 times
        // return C(m+n-2, m-1)
        return choose(m+n-2, m-1);
    }
};

Basic Calculator II (medium)

// Runtime: 36ms, beat 31.78%
class Solution {
public:
    int calculate(string s) {
        stack<int> val;
        stack<char> op;
        int value = -1;  // <0 means we are not parsing numbers

        s += '#';  // stop sign
        for (auto ch : s) {
            if (isdigit(ch)) {
                if (value < 0) {
                    value = ch - '0';
                } else {
                    value = value * 10 + ch - '0';
                }
            } else {
                if (value >= 0) val.push(value);
                value = -1;
                if (ch == ' ') continue;
                while (!op.empty()) {
                    char top_op = op.top();
                    if ((ch == '*' || ch == '/') && (top_op == '+' || top_op == '-')) {
                        break;
                    }
                    op.pop();
                    int b = val.top(); val.pop();
                    int a = val.top(); val.pop();
                    switch (top_op) {
                        case '*': {val.push(a*b); break;}
                        case '/': {val.push(a/b); break;}
                        case '+': {val.push(a+b); break;}
                        case '-': {val.push(a-b); break;}
                    }
                }
                op.push(ch);
            }
        }

        // return!
        return val.top();
    }
};

Word Break (medium)

// Runtime: 4ms, beat 85.01%
class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        vector<bool> ok(s.length() + 1, false);
        ok[0] = true;
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int last_end = q.front();
            q.pop();
            // ok[last_end] == true
            for (auto word : wordDict) {
                if (last_end + word.length() > s.length() || ok[last_end + word.length()]) {
                    // to long, or we have been there already
                    continue;
                }
                bool success = true;
                for (int i = 0; i < word.size() && success; i++) {
                    success &= (s[last_end + i] == word[i]);
                }
                if (success) {
                    ok[last_end + word.length()] = true;
                    q.push(last_end + word.length());
                }
            }
        }
        return ok[s.length()];
    }
};

Sort List (medium)

// Runtime: 67ms, beat 27.84%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    void mergeList(ListNode *head1, ListNode *head2, ListNode *next, ListNode *&new_head, ListNode *&new_tail) {
        // input: head -> ... tail1 -> head2 -> ... tail2 -> next
        // output: new_head -> ... -> new_tail -> (NULL)
        static ListNode *super_head = new ListNode(0);
        new_tail = super_head;
        ListNode *stop1 = head2, *stop2 = next;
        while (head1 != stop1 || head2 != stop2) {
            if (head1 != stop1 && (head2 == stop2 || head1->val < head2->val)) {
                new_tail->next = head1;
                head1 = head1->next;
            } else {
                new_tail->next = head2;
                head2 = head2->next;
            }
            new_tail = new_tail->next;
        }
        new_tail->next = NULL;
        new_head = super_head->next;
    }
    ListNode* sortList(ListNode* head) {
        static ListNode *super_head = new ListNode(0);
        super_head->next = head;
        for (int seg = 1; ; seg <<= 1) {
            ListNode *tail = super_head;
            ListNode *head1 = super_head->next;
            while (head1 != NULL) {
                // the head of the second segment
                ListNode *head2 = head1;
                for (int j = 0; j < seg && head2 != NULL; j++) {
                    head2 = head2->next;
                }
                if (head2 == NULL) {
                    tail->next = head1;
                    break;  // no need to merge
                }
                ListNode *next = head2;
                for (int j = 0; j < seg && next != NULL; j++) {
                    next = next->next;
                }
                // merge
                ListNode *new_head, *new_tail;
                mergeList(head1, head2, next, new_head, new_tail);
                tail->next = new_head;
                tail = new_tail;
                // the head of the next next segments
                head1 = next;
            }
            if (tail == super_head) {
                break;  // no merge in this iteration
            }
        }
        return super_head->next;
    }
};

Reconstruct Itinerary (medium)

// Runtime: 40ms, beat 37.67%
class Solution {
private:
    bool findItineraryDFS(int num_tickets, vector<pair<string,string>> &tickets, vector<bool> &used, int i, vector<string> &path) {
        if (i == num_tickets) {
            return true;
        }
        // search for the next stop
        string crt_airport = path.back();
        auto pr = make_pair(crt_airport, string("AAA"));
        auto itr = std::lower_bound(tickets.begin(), tickets.end(), pr);
        // try
        while (itr != tickets.end() && itr->first == crt_airport) {
            if (!used[itr-tickets.begin()]) {
                // search
                used[itr-tickets.begin()] = true;
                path.push_back(itr->second);
                if (findItineraryDFS(num_tickets, tickets, used, i+1, path)) {
                    return true;
                }
                // recover
                used[itr-tickets.begin()] = false;
                path.pop_back();
            }
            itr++;
        }
        // cannot find path
        return false;
    }
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        // sort tickets according to the lexical order
        std::sort(tickets.begin(), tickets.end());
        // prepare for the DFS
        int num_tickets = tickets.size();
        vector<bool> used(num_tickets, false);
        vector<string> path(1, "JFK");
        // DFS
        findItineraryDFS(num_tickets, tickets, used, 0, path);
        return path;
    }
};

Summary Ranges (medium)

// Runtime: 0ms
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;

        int i = 0;
        while (i < nums.size()) {
            int j = i;
            while (j + 1 < nums.size() && nums[j+1] == nums[j] + 1) {
                j++;
            }
            // [i->j];
            if (i != j) {
                result.push_back(to_string(nums[i])+"->"+to_string(nums[j]));
            } else {
                result.push_back(to_string(nums[i]));
            }
            i = j + 1;
        }

        return result;
    }
};

Coin Change (medium)

DP

// Runtime: 132ms, beat 67.30%
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int f[amount+1];
        f[0] = 0;
        for (int i = 1; i <= amount; i++){
            f[i] = -1;
            for (auto coin : coins) {
                if (i-coin >= 0 && f[i-coin] != -1 && (f[i] == -1 || f[i-coin] + 1 < f[i])) {
                    f[i] = f[i-coin] + 1;
                }
            }
        }
        return f[amount];
    }
};

Clone Graph (medium)

Notes

• itr = some_map.find(key)
• Use itr->second to get the value, not *itr!!!!!!!!!!!

// Runtime: 72ms, beat 94.46%
/**
  * Definition for undirected graph.
  * struct UndirectedGraphNode {
  *     int label;
  *     vector<UndirectedGraphNode *> neighbors;
  *     UndirectedGraphNode(int x) : label(x) {};
  * };
  */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL) return NULL;
        // init
        unordered_map<int, UndirectedGraphNode*> cloned_nodes;  // label -> cloned node
        queue<pair<UndirectedGraphNode*, UndirectedGraphNode*>> todo;  // old new
        UndirectedGraphNode *root = new UndirectedGraphNode(node->label);
        cloned_nodes[node->label] = root;
        todo.emplace(node, root);
        // search
        while (!todo.empty()) {
            UndirectedGraphNode* old_node = todo.front().first;
            UndirectedGraphNode* new_node = todo.front().second;
            todo.pop();
            // copy old_new-> new_node
            for (UndirectedGraphNode* neighbor : old_node->neighbors) {
                int label = neighbor->label;
                auto itr = cloned_nodes.find(label);
                if (itr == cloned_nodes.end()) {
                    // construct a new node
                    UndirectedGraphNode *tmp = new UndirectedGraphNode(label);
                    cloned_nodes[label] = tmp;
                    new_node->neighbors.push_back(tmp);
                    todo.emplace(neighbor, tmp);  // old new
                } else {
                    new_node->neighbors.push_back(itr->second);
                }
            }
        }
        // return the cloned "root node"
        return root;
    }
};

Maximal Square (medium)

// Runtime: 12ms, beat 36.48%
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<int> last_row(m, 0), crt_row(m, 0);
        int max_size = 0;  // return max_size * max_size
        for (int i = 0; i < n; i++) {
            last_row.swap(crt_row);
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '0') {
                    crt_row[j] = 0;
                } else {
                    crt_row[j] = 1 + ((j > 0) ? min(crt_row[j-1], min(last_row[j-1], last_row[j])) : 0);
                    max_size = max(max_size, crt_row[j]);
                }
            }
        }
        return max_size * max_size;
    }
};

Evaluate Reverse Polish Notation (medium)

Be careful when check whether a string is an integer.

// Runtime: 16ms, beat 34.14%
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // assume the expression is valid
        stack<int> s;
        for (auto str: tokens) {
            if (str.length() == 1 && !isdigit(str[0])){
                int b = s.top(); s.pop();
                int a = s.top(); s.pop();
                switch (str[0]) {
                    case '+': {s.push(a+b); break;}
                    case '-': {s.push(a-b); break;}
                    case '*': {s.push(a*b); break;}
                    case '/': {s.push(a/b); break;}
                }
            } else {
                s.push(std::stoi(str, nullptr));
            }
        }
        return s.top();
    }
};

Restore IP Addresses (medium)

Should double check whether the leading zero in the returned address is okay.

// Runtime: 0ms, beat 89.18%
class Solution {
private:
    void restoreIpAddressesDFS(string s, int slen, int count, int start,
                            string ipaddr[], vector<string> &result) {
        if (count == 4 || start == slen) {
            if (count == 4 && start == slen) {
                result.push_back(ipaddr[0] + "." + ipaddr[1] + "." + ipaddr[2] + "." + ipaddr[3]);
            }
            return;
        }
        // prune
        int chars_left = slen - start;
        int pos_left = 4 - count;
        if (chars_left < pos_left || chars_left > pos_left * 3) return;
        // search
        for (int i = 1; i <= min(3, chars_left); i++) {
            string temp = s.substr(start, i);
            if (i > 1 && temp[0] == '0') continue;  // leading zero
            if (i <= 2 || std::stoi(temp, nullptr, 10) < 256) {
                ipaddr[count] = temp;
                restoreIpAddressesDFS(s, slen, count+1, start+i, ipaddr, result);
            }
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        int slen = s.length();
        vector<string> result;
        string ipaddr[4];

        restoreIpAddressesDFS(s, slen, 0, 0, ipaddr, result);

        return result;
    }
};

Longest Palindromic Substring (medium)

Naive check.

// Runtime: 76ms, beat 51.98%
class Solution {
public:
    string longestPalindrome(string s) {
        int length = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < s.length() && s[l] == s[r]) {
                l--;
                r++;
            }
            if (r - l - 1 > length) {
                length = r - l - 1;
                start = l + 1;
            }
            l = i, r = i + 1;
            while (l >= 0 && r < s.length() && s[l] == s[r]) {
                l--;
                r++;
            }
            if (r - l - 1 > length) {
                length = r - l - 1;
                start = l + 1;
            }
        }
        return s.substr(start, length);
    }
};

Wiggle Sort II (medium)

This is hard. >.

// Runtime: 112ms with nth_element
```c++
// Runtime: 388ms with quickSelect....
class Solution {
private:
    int quickSelect(vector<int> &nums, int left, int right, int k) {
        if (left == right) return nums[left];
        int rand_pos = rand() % (right - left + 1) + left;  // rand([l,r])
        int pivot = nums[rand_pos];
        swap(nums[rand_pos], nums[right]);
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (nums[j] < pivot) {
                swap(nums[++i], nums[j]);  // put it in the first half
            }
        }
        swap(nums[++i], nums[right]);  // nums[i] = pivot
        if (i - left == k) {
            return nums[i];
        } else if (i - left > k) {
            return quickSelect(nums, left, i - 1, k);
        } else {
            return quickSelect(nums, i+1, right, k - (i - left + 1));
        }
    }
    int true_pos(int n, int i) {
        return (i * 2 + 1) % (n|1);
    }
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        // find the medium
        vector<int>::iterator nth = next(nums.begin(), n / 2);
        nth_element(nums.begin(), nth, nums.end());
        int mid = *nth;
        // move around elements (three-way partition)
        int i = 0, j = 0;
        int right = n - 1;
        while (j <= right) {
            if (nums[true_pos(n,j)] > mid) {
                swap(nums[true_pos(n,i++)], nums[true_pos(n,j++)]);
            } else if (nums[true_pos(n,j)] < mid) {
                swap(nums[true_pos(n,j)], nums[true_pos(n,right--)]);
            } else {
                j++;
            }
        }
    }
};

Reorder List (medium)

Ideas

• Find the middle element
• Reverse the second half
• Merge two lists

// Runtime: 64ms, beat 51.24%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
private:
    ListNode* cutMid(ListNode *head) {
        // assume head != NULL
        ListNode *fast = head, *slow = head, *before_mid = NULL;
        while (fast != NULL) {
            fast = fast->next;
            if (fast != NULL) {
                fast = fast->next;
            }
            if (fast == NULL) {
                before_mid= slow;
            }
            slow = slow->next;
        }
        before_mid->next = NULL;  // cut here
        return slow;
    }
    ListNode* reverseList(ListNode *head) {
        // assume head != NULL
        ListNode* super_head = new ListNode(0);
        while (head != NULL) {
            ListNode *nxt = head->next;
            head->next = super_head->next;
            super_head->next = head;
            head = nxt;
        }
        // clear and return
        ListNode* result = super_head->next;
        delete super_head;
        return result;
    }
    ListNode* mergeLists(ListNode *head1, ListNode *head2) {
        // assume head1 != NULL && head2 != NULL
        ListNode *super_head = new ListNode(0), *tail = super_head;
        // merge
        while (head1 != NULL) {
            tail->next = head1;
            head1 = head1->next;
            tail = tail->next;
            if (head2 != NULL) {
                tail->next = head2;
                head2 = head2->next;
                tail = tail->next;
            }
        }
        // clear and return
        ListNode* result = super_head->next;
        delete super_head;
        return result;
    }
public:
    void reorderList(ListNode* head) {
        if (head == NULL || head->next == NULL) return;
        ListNode *mid_head = cutMid(head);
        mid_head = reverseList(mid_head);
        head = mergeLists(head, mid_head);
    }
};

Rotate List (medium)

If k<len, we only need to scan the list in one pass.

// Runtime: 8ms, beat 85.93%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || k == 0) return head;

        // First pass
        // 1, 2, 3, [4], 5, [6] (len = 6, k = 2)
        // 1[ptr_fast, len=1], 2, 3, 4, 5, 6
        // 1, 2[ptr_fast, len=2], 3, 4, 5, 6
        // 1, 2, 3[ptr_fast, len=3], 4, 5, 6
        // 1, 2[ptr_slow], 3, 4[ptr_fast, len=4], 5, 6
        // 1, 2, 3, 4[ptr_slow], 5, 6[ptr_fast, len=6]
        int len = 1;
        ListNode *ptr_fast = head, *ptr_slow = head;
        while (ptr_fast->next != NULL) {
            if (len > k) ptr_slow = ptr_slow->next;
            ptr_fast = ptr_fast->next;
            len++;
        }

        if (k >= len) {
            k = k % len;
            for (int i = 0; i < len - k - 1; i++) {
                ptr_slow = ptr_slow->next;
            }
        }

        if (k != 0) {
            ptr_fast->next = head;
            head = ptr_slow->next;
            ptr_slow->next = NULL;
        }

        return head;
    }
};

Slower, clearer, always two passes.

// Runtime: 12ms, beat 9.38%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || k == 0) return head;

        int len = 1;
        ListNode *tail = head;
        while (tail->next != NULL) {
            tail = tail->next;
            len++;
        }

        k = k % len;

        if (k != 0) {
            ListNode *new_tail = head;
            for (int i = 0; i < len - k - 1; i++) {
                new_tail = new_tail->next;
            }
            tail->next = head;
            head = new_tail->next;
            new_tail->next = NULL;
        }

        return head;
    }
};

Spiral Matrix II (medium)

// Runtime: 4ms
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        if (n == 0) return vector<vector<int>>();

        vector<vector<int>> result(n, vector<int>(n, 1));
        int wall_left = -1, wall_up = -1;
        int wall_right = n, wall_down = n;
        int dir = 0;
        for (int i = 2, x = 0, y = 0; i <= n * n;) {
            if (dir == 0) {
                if (y + 1 < wall_right) {
                    y++;
                    result[x][y] = i++;
                } else {
                    dir = 1;
                    wall_up++;
                }
            } else if (dir == 1) {
                if (x + 1 < wall_down) {
                    x++;
                    result[x][y] = i++;
                } else {
                    dir = 2;
                    wall_right--;
                }
            } else if (dir == 2) {
                if (y - 1 > wall_left) {
                    y--;
                    result[x][y] = i++;
                } else {
                    dir = 3;
                    wall_down--;
                }
            } else if (dir == 3) {
                if (x - 1 > wall_up) {
                    x--;
                    result[x][y] = i++;
                } else {
                    dir = 0;
                    wall_left++;
                }
            }
        }
        return result;
    }
};

Spiral Matrix (medium)

// Runtime: 0ms
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return vector<int>();

        int n = matrix.size(), m = matrix[0].size();
        vector<int> result(n * m);
        int wall_up = -1, wall_down = n;
        int wall_left = -1, wall_right = m;
        int dir = 0;

        result[0] = matrix[0][0];
        for (int i = 1, x = 0, y = 0; i < n * m; ) {
            if (dir == 0) {
                if (y + 1 < wall_right) {
                    y = y + 1;
                    result[i++] = matrix[x][y];
                } else {
                    wall_up++;
                    dir = 1;
                }
            } else if (dir == 1) {
                if (x + 1 < wall_down) {
                    x = x + 1;
                    result[i++] = matrix[x][y];
                } else {
                    wall_right--;
                    dir = 2;
                }
            } else if (dir == 2) {
                if (y - 1 > wall_left) {
                    y = y - 1;
                    result[i++] = matrix[x][y];
                } else {
                    wall_down--;
                    dir = 3;
                }
            } else if (dir == 3) {
                if (x - 1 > wall_up) {
                    x = x - 1;
                    result[i++] = matrix[x][y];
                } else {
                    wall_left++;
                    dir = 0;
                }
            }
        }

        return result;
    }
};

Maximum Product Subarray (medium)

Greedy

• Get the product of a contiguous sequence that does not contain zero.
• If the product is negative, try to remove the first few elements or

the last few elements of the sequence so that the product is positive.

// Runtime: 8ms, beat 8.08%
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // boundary cases
        if (nums.size() == 1) return nums.front();

        // normal cases
        long long result = 0;
        for (int start = 0; start < nums.size(); ) {
            if (nums[start] == 0) {
                start++;
                continue;
            }
            long long prod = nums[start];  // prod of nums[start..end]
            long long neg = nums[start];  // shortest sequence from start, negative
            result = max(result, prod);

            int end = start + 1;
            while (end < nums.size() && nums[end] != 0) {
                prod *= nums[end];
                if (neg > 0) neg *= nums[end];
                result = max(result, max(prod, prod/neg));
                end++;
            }
            start = end;
        }

        return result;
    }
};

Simplify Path (medium)

// Runtime: 8ms, beat 54.92%
class Solution {
public:
    string simplifyPath(string path) {
        vector<string> st;  // simulate a stack

        path += "/";  // to make sure end != string::npos
        size_t start = path.find_first_not_of("/");

        while (start != string::npos) {
            size_t end = path.find_first_of("/", start+1);
            string tmp = path.substr(start, end-start);
            if (tmp == "..") {
                if (!st.empty()) st.pop_back();
            } else if (tmp != ".") {
                st.push_back(tmp);
            }
            start = path.find_first_not_of("/", end+1);
        }

        string result;
        for (auto str : st) {
            result += "/" + str;
        }
        return result.empty() ? "/" : result;
    }
};

Range Sum Query 2D - Immutable (medium)

// Runtime: 24ms, beat 49.76%
class NumMatrix {
private:
    vector<vector<long long>> sum;
public:
    NumMatrix(vector<vector<int>> &matrix) {
        if (!matrix.empty()) {
            int n = matrix.size(), m = matrix[0].size();
            sum.resize(n);
            for (int row = 0; row < n; row++) {
                sum[row].resize(m);
                for (int col = 0; col < m; col++) {
                    sum[row][col] = matrix[row][col];
                    if (row > 0) sum[row][col] += sum[row-1][col];
                    if (col > 0) sum[row][col] += sum[row][col-1];
                    if (row > 0 && col > 0) sum[row][col] -= sum[row-1][col-1];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int result = sum[row2][col2];
        if (row1 > 0) result -= sum[row1-1][col2];
        if (col1 > 0) result -= sum[row2][col1-1];
        if (row1 > 0 && col1 > 0) result += sum[row1-1][col1-1];
        return result;
    }
};


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

Validate Binary Search Tree (medium)

Notes

• Be careful about the overflow/underflow problem!!!!!!
• Don’t forget return.

// Runtime: 16ms, beat 14.08%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    bool isValidBSTHelper(TreeNode* root, int lb, int ub) {
        // assume root != NULL
        bool res = root->val >= lb && root->val <= ub;
        if (root->left != NULL) {
            res &= root->val > lb && isValidBSTHelper(root->left, lb, root->val - 1);
        }
        if (root->right != NULL) {
            res &= root->val < ub && isValidBSTHelper(root->right, root->val + 1, ub);
        }
        return res;
    }
public:
    bool isValidBST(TreeNode* root) {
        return root == NULL || isValidBSTHelper(root, INT_MIN, INT_MAX);
    }
};

Largest Number (medium)

First implementation, O(1) extra space.

// Runtime: 20ms, beat 28.94%
class Solution {
private:
    static bool cmp(int a, int b) {
        string s1 = to_string(a), s2 = to_string(b);
        return s1 + s2 > s2 + s1;
    }

public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string result;
        for (auto value : nums) {
            if (result == "" && value == 0) continue;
            result += to_string(value);
        }
        if (result == "") result = "0";
        return result;
    }
};

Second implementation, O(n) extra spaces, faster.

// Runtime: 8ms, beat 59.61%
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> str(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            str[i] = to_string(nums[i]);
        }
        sort(str.begin(), str.end(),
            [] (const string &a, const string &b) -> bool {
                return a + b > b + a;
            });
        string result;
        for (auto s : str) {
            if (result == "" && s == "0") continue;
            result += s;
        }
        if (result == "") result = "0";
        return result;
    }
};

Climbing Stairs (easy)

// Runtime: 0ms
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int prepre = 0;
        int pre = 1;    // n == 1
        int crt = 2;  // n == 2 (1+1, 2)
        for (int i = 3; i <= n; i++) {
            prepre = pre;
            pre = crt;
            crt = pre + prepre;
        }
        return crt;
    }
};

July 21, 2016

Single Number III (medium)

Learned from the discussion board.
Notes

• Get all_xor, xor of all values. At least one bit of all_xor is one.
• Find some bit in all_xor is one.

Separate numbers into two groups according to that bit.
Each group contains one result.

• Remember to initialize all variables!!!!!!!

// Runtime: 16ms, beat 87.74%
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int all_xor = 0;
        for (auto value : nums) {
            all_xor ^= value;
        }
        int flag_bit = 1;
        while ((all_xor & flag_bit) == 0) {
            flag_bit <<= 1;
        }
        int res1 = 0, res2 = 0;
        for (auto value : nums){
            if ((value & flag_bit) == 0) {
                res1 ^= value;
            } else {
                res2 ^= value;
            }
        }
        vector<int> result;
        result.push_back(res1);
        result.push_back(res2);
        return result;
    }
};

Counting Bits

// Runtime: 80ms, beat 97.66%
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> result(num + 1, 0);
        for (int i = 1; i <= num; i++) {
            result[i] = result[i>>1] + (i&1);
        }
        return result;
    }
};

Single Number (medium)

// Runtime: 20ms, beat 28.40%
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int all_xor = 0;
        for (auto value : nums) {
            all_xor ^= value;
        }
        return all_xor;
    }
};

Top K Frequent Elements (medium)

Notes

• By default, priority_queue is a MAXHEAP!!!!

// Runtime: 36ms, beat 75.54%
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // O(n log (n-k)) computation of frequencies
        unordered_map<int,int> freq;
        for (auto value : nums) {
            freq[value]++;
        }

        // find top-k O(n log k)
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;  // freq, value
        for (auto value_freq : freq) {
            if (pq.size() < k) {
                pq.emplace(value_freq.second, value_freq.first);
            } else if (value_freq.second > pq.top().first) {
                pq.pop();
                pq.emplace(value_freq.second, value_freq.first);
            }
        }

        // get results
        vector<int> result(k, 0);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pq.top().second;
            pq.pop();
        }
        return result;
    }
};

Product of Array Except Self (medium)

// Runtime: 60ms, beat 54.88%
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result(nums.size(), 1);
        int left = 1;
        for (int i = 0; i < nums.size(); i++) {
            result[i] *= left;
            left *= nums[i];
        }
        int right = 1;
        for (int i = nums.size() - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }
        return result;
    }
};

Integer Break (medium)

Notes:

• Be careful about the corner cases!
• pow returns double!

// Runtime: 0ms
class Solution {
public:
    int integerBreak(int n) {
        // special cases
        if (n == 2) return 1;
        if (n == 3) return 2;
        // normal cases
        double result = 0;
        for (int num_two = 0, n_remaining = n; num_two <= n / 2; num_two++, n_remaining -= 2) {
            if (n_remaining % 3 != 0) continue;
            int num_three = n_remaining / 3;
            result = max(result, pow(2, num_two) * pow(3, num_three));
        }
        return result;
    }
};

Missing Number (medium)

Naive method

// Runtime: 32ms, beat 91.71%
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        long long n = nums.size();
        long long sum = n * (n + 1) / 2;
        for (auto value : nums) sum -= value;
        return sum;
    }
};

Don’t think too much…..

// Runtime: 36ms, beat 30.08%
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int all_xor = 0;
        for (int i = 0; i < nums.size(); i++) {
            all_xor ^= nums[i] ^ i;
        }
        return all_xor ^ nums.size();
    }
};

Bit manipulation

Binary Tree Preorder Traversal (medium)

// Runtime: 4ms, beat 0.60%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;

        if (root != NULL) s.push(root);
        while (!s.empty()) {
            TreeNode *crt = s.top();
            s.pop();
            result.push_back(crt->val);
            if (crt->right != NULL) s.push(crt->right);
            if (crt->left != NULL) s.push(crt->left);
        }

        return result;
    }
};

Maximum Product of Word Lengths (medium)

For each word, construct a “sketch” indicating appearances of characters.
Then, we can compare any two words fast.

// Runtime: 112ms, beat 88.66%
class Solution {
public:
    int maxProduct(vector<string>& words) {
        // sort words according to their lengths
        sort(words.begin(), words.end(),
            [](const string &a, const string &b) -> bool {
                return a.length() > b.length();
            });

        // construct sketches of words (for quick comparison)
        vector<int> sketch(words.size(), 0);
        for (int i = 0; i < words.size(); i++) {
            for (auto ch : words[i]) {
                sketch[i] |= (1 << (ch-'a'));
            }
        }
        // compute the result
        int result = 0;
        for (int i = 0; i < (int)words.size() - 1; i++) {
            for (int j = i + 1; j < words.size(); j++) {
                if ((sketch[i] & sketch[j]) == 0) {
                    int tmp = words[i].length() * words[j].length();
                    result = max(result, tmp);
                    break;
                }
            }
        }
        return result;
    }
};

Integer to Roman (medium)

// Runtime: 32ms, beat 66.30%
class Solution {
public:
    string intToRoman(int num) {
        string result;
        static char ones[] = {'M', 'C', 'X', 'I'};
        static char fives[] = {'?', 'D', 'L', 'V'};
        for (int i = 0, mask = 1000; i <= 3; i++, mask /= 10) {
            int d = num / mask;
            if (d == 0) continue;
            if (d <= 3) {
                result.append(d, ones[i]);
            } else if (d == 4) {
                result.append(1, ones[i]);
                result.append(1, fives[i]);  // e.g., IV
            } else if (d <= 8) {
                result.append(1, fives[i]);
                result.append(d-5, ones[i]);
            } else if (d == 9) {
                result.append(1, ones[i]);
                result.append(1, ones[i-1]);  // e.g., IX
            }
            num -= d * mask;
        }
        return result;
    }
};

Odd Even Linked List (medium)

Don’t forget to set tail_even->next = NULL!!!!!!!!!!!!!!!!!!!!!!!!!!.

// Runtime: 20ms, beat 20.18%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode *head_odd = new ListNode(0), *tail_odd = head_odd;
        ListNode *head_even = new ListNode(0), *tail_even = head_even;

        bool odd = true;
        while (head != NULL) {
            if (odd) {
                tail_odd->next = head;
                tail_odd = tail_odd->next;
            } else {
                tail_even->next = head;
                tail_even = tail_even->next;
            }
            head = head->next;
            odd = !odd;
        }

        tail_even->next = NULL;
        tail_odd->next = head_even->next;
        return head_odd->next;
    }
};

Kth Smallest Element in a BST (medium)

// Runtime: 20ms, beat 72.56%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    // the returned value is what we want iff tree_size >= k
    // tree_size may be less than the real tree-size, if it is larger than k.
    int kthSmallestHelper(TreeNode* root, int k, int &tree_size) {
        // corner case
        tree_size = 0;
        if (root == NULL) return 0;

        int left_size = 0, right_size = 0, result = 0;
        // search root->left
        result = kthSmallestHelper(root->left, k, left_size);
        tree_size = left_size + 1;
        if (left_size >= k) return result;
        // check root
        if (left_size == k - 1) return root->val;
        // search root->right
        result = kthSmallestHelper(root->right, k - left_size - 1, right_size);
        tree_size += right_size;
        return result;
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        int tree_size = 0;
        return kthSmallestHelper(root, k, tree_size);
    }
};

Generate Parentheses (medium)

Notes:

• Don’t forget <char> in stack<char>….

// Runtime: 0ms, beat 41.55%
class Solution {
private:
    void generateParenthesisHelper(int nl, int nr, int pos, string &str,
                                    stack<char> &par_stack, vector<string> &result) {
        if (nl == 0 && nr == 0) {
            result.push_back(str);
            return;
        }

        // try (
        if (nl > 0) {
            str[pos] = '(';
            par_stack.push('(');
            generateParenthesisHelper(nl-1, nr, pos+1, str, par_stack, result);
            par_stack.pop();  // recover
        }

        // try )
        if (nr > 0 && !par_stack.empty() && par_stack.top() == '(') {
            par_stack.pop();
            str[pos] = ')';
            generateParenthesisHelper(nl, nr-1, pos+1, str, par_stack, result);
            par_stack.push('(');  // recover
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string str(n * 2, ' ');
        stack<char> par_stack;

        generateParenthesisHelper(n, n, 0, str, par_stack, result);

        return result;
    }
};

Single Number II (medium)

Let result be the result. For each bit of result,
it is 1 if and only if the number of occurrences of 1 in that position is 1+3x.

// Runtime: 12ms, beat 74.96%
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for (auto value : nums) {
            int zero = ~(one|two);
            int new_one = (one&~value) | (zero&value);
            int new_two = (two&~value) | (one&value);
            one = new_one;
            two = new_two;
        }
        return one;
    }
};

Convert Sorted Array to Binary Search Tree (medium)

How to proof?

// Runtime: 16ms, beat 74.11%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    TreeNode* sortedArrayToBSTHelper(vector<int> &nums, int left, int right) {
        if (left > right) return NULL;
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = sortedArrayToBSTHelper(nums, left, mid - 1);
        root->right = sortedArrayToBSTHelper(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBSTHelper(nums, 0, -1 + nums.size());
    }
};

Unique Binary Search Trees (medium)

The inner loop could be further speedup…

class Solution {
public:
    int numTrees(int n) {
        // dynamic programming
        // f[n] : answer for n
        // f[n] = sum(f[left]*f[n-1-left]), left in [1, n-1]
        vector<int> f(n + 1, 0);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int left = 0; left <= i - 1; left++) {
                f[i] += f[left] * f[i-1-left];
            }
        }
        return f[n];
    }
};

Search Insert Position (medium)

Binary search.

// Runtime: 8ms, beat 15.00%
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

Combination Sum III (medium)

Simple DFS.

// Runtime: 0ms
class Solution {
private:
    void combinationSum3DFS(int k, int goal, int i,
                            vector<int> &crt, vector<vector<int>> &results) {
        if (i == k) {
            if (goal == 0) {
                results.push_back(crt);
            }
            return;
        }
        // set crt[i]
        int value_begin = i == 0 ? 1 : crt[i-1] + 1;
        int value_end = min(10 - (k - i), goal);
        for (int value = value_begin; value <= value_end; value++) {
            crt[i] = value;
            combinationSum3DFS(k, goal - value, i+1, crt, results);
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> results;
        vector<int> crt(k, 0);
        combinationSum3DFS(k, n, 0, crt, results);
        return results;
    }
};

Rectangle Area (easy)

// Runtime: 32ms, beat 58.47%
class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        long long area_sum = (C-A)*(D-B) + (G-E)*(H-F);
        long long  x1 = max(A, E), x2 = min(C, G);
        long long  y1 = max(F, B), y2 = min(D, H);
        return area_sum - max(x2 - x1, 0LL) * max(y2 - y1, 0LL);
    }
};

July 15, 2016

3Sum Closest (medium)

First implementation O(n^2).

// Runtime: 28ms, beat 15.06%
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int best_sum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n - 2; i++) {
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (abs(best_sum - target) > abs(sum - target)) {
                    best_sum = sum;
                }
                if (sum < target) j++;
                else k--;
            }
        }
        return best_sum;
    }
};

July 14, 2016

N-Queens II :hard:

// Runtime: 0ms, beat 90.19%
class Solution {
private:
    void totalNQueensDFS(int i, int n, int pos[], bool col[], bool diag1[], bool diag2[], int &result) {
        if (i == n) {
            result++;
        } else {
            // find position of the queue for the current row
            for (int j = 0; j < n; j++) {
                if (col[j] || diag1[i-j+(n-1)] || diag2[i+j]) continue;
                col[j] = diag1[i-j+(n-1)] = diag2[i+j] = true;
                pos[i] = j;
                totalNQueensDFS(i+1, n, pos, col, diag1, diag2, result);
                col[j] = diag1[i-j+(n-1)] = diag2[i+j] = false;
            }
        }
    }
public:
    int totalNQueens(int n) {
        bool col[n] = {}, diag1[2*n] = {}, diag2[2*n] = {};
        int pos[n];  // position of the queue in the i-th row
        int result = 0;
        totalNQueensDFS(0, n, pos, col, diag1, diag2, result);
        return result;
    }
};

N-Queens :hard:

// Runtime: 0ms, beat 91.88%
class Solution {
private:
    void solveNQueensDFS(int i, int n, int pos[], bool col[], bool diag1[], bool diag2[],
            vector<vector<string>> &result) {
        if (i == n) {
            result.push_back(vector<string>(n, string(n, '.')));
            for (int j = 0; j < n; j++) {
                result.back()[j][pos[j]] = 'Q';
            }
        } else {
            // find position of the queue for the current row
            for (int j = 0; j < n; j++) {
                if (col[j] || diag1[i-j+(n-1)] || diag2[i+j]) continue;
                col[j] = diag1[i-j+(n-1)] = diag2[i+j] = true;
                pos[i] = j;
                solveNQueensDFS(i+1, n, pos, col, diag1, diag2, result);
                col[j] = diag1[i-j+(n-1)] = diag2[i+j] = false;
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        bool col[n] = {}, diag1[2*n] = {}, diag2[2*n] = {};
        int pos[n];  // position of the queue in the i-th row
        vector<vector<string>> result;
        solveNQueensDFS(0, n, pos, col, diag1, diag2, result);
        return result;
    }
};

Swap Nodes in Pairs (easy)

// Runtime: 4ms, beat 3.56%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *super_head = new ListNode(0);
        ListNode *tail = super_head;
        while (head != NULL) {
            if (head->next != NULL) {
                ListNode *tmp = head->next->next;
                tail->next = head->next;
                tail->next->next = head;
                tail = tail->next->next;
                head = tmp;
            } else {
                ListNode *tmp = head->next;
                tail->next = head;
                tail = tail->next;
                head = head->next;
                head = tmp;
            }
            tail->next = NULL;
        }
        return super_head->next;
    }
};

Reverse Nodes in k-Group :hard:

Iterative implementation

// Runtime: 24ms, beat 54.68%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // init
        ListNode *new_head = new ListNode(0);
        ListNode *new_tail = new_head;

        while (head != NULL) {
            ListNode *nxt_seg = head;
            int cnt = 0;
            for (; cnt < k && nxt_seg != NULL; cnt++) {
                nxt_seg = nxt_seg->next;
            }
            if (cnt < k) {
                new_tail->next = head;
            } else {
                ListNode *old_tail = new_tail, *crt = head;
                new_tail = head;
                for (int i = 0; i < k; i++) {
                    ListNode *nxt = crt->next;
                    crt->next = old_tail->next;
                    old_tail->next = crt;
                    crt = nxt;
                }
            }
            head = nxt_seg;
        }

        return new_head->next;
    }
};

Recursive implementation

// Runtime: 28ms, beat 12.09%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // check the number of elements
        ListNode *nxt_seg = head;
        int cnt = 0;
        for (; cnt < k && nxt_seg != NULL; cnt++) nxt_seg = nxt_seg->next;
        if (cnt < k) return head;

        // init
        ListNode *new_head = new ListNode(0);
        ListNode *new_tail = head;
        ListNode *crt = head;
        for (int i = 0; i < k; i++) {
            ListNode *nxt = crt->next;
            crt->next = new_head->next;
            new_head->next = crt;
            crt = nxt;
        }
        new_tail->next = reverseKGroup(nxt_seg, k);
        return new_head->next;
    }
};

Regular Expression Matching :hard:

Search with logged results

// Runtime: 12ms, beat 73.25%
class Solution {
private:
    bool isMatchHelper(string s, string p, int slen, int plen, int si, int pi,
                    vector<vector<int>> &log) {
        if (si == slen && pi == plen) return true;
        if (si > slen || pi > plen) return false;
        if (log[si][pi] != -1) return log[si][pi];
        log[si][pi] = 0;  // false
        if (p[pi] == '*') {
            log[si][pi] = isMatchHelper(s, p, slen, plen, si, pi + 1, log);
        } else if (pi + 1 < plen && p[pi + 1] == '*') {
            int next_pi = pi + 1;
            while (next_pi < plen && p[next_pi] == '*') next_pi++;
            log[si][pi] |= isMatchHelper(s, p, slen, plen, si, next_pi, log);
            for (int last_si = si;
                  last_si < slen && (p[pi] == '.' || s[last_si] == p[pi]);
                  last_si++) {
                log[si][pi] |=
                    isMatchHelper(s, p, slen, plen, last_si + 1, next_pi, log);
            }
        } else {
            log[si][pi] |= (p[pi] == '.' || s[si] == p[pi]) &&
                            isMatchHelper(s, p, slen, plen, si + 1, pi + 1, log);
        }
        return log[si][pi];
    }

public:
    bool isMatch(string s, string p) {
        vector<vector<int>> log(s.length() + 1, vector<int>(p.length() + 1, -1));
        return isMatchHelper(s, p, s.length(), p.length(), 0, 0, log);
    }
};

Wildcard Matching :hard:

First (slow) implementation

// Runtime: 1272ms, beat 34.60%
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<bool> match(s.length() + 1, false);
        match[0] = true;
        for (char ch : p) {
            if (ch == '*') {
                for (int i = 1; i <= s.length(); i++) {
                    match[i] = match[i] || match[i-1];
                }
            } else if (ch == '?') {
                for (int i = s.length(); i >= 1; i--) {
                    match[i] = match[i-1];
                }
                match[0] = false;
            } else {
                for (int i = s.length(); i >= 1; i--) {
                    match[i] = match[i-1] && (s[i-1] == ch);
                }
                match[0] = false;
            }
        }
        return match.back();
    }
};

The second (faster) implementation (dynamic programming)

// Runtime: 477ms, beat 42.93%
class Solution {
public:
    bool isMatch(string s, string p) {
        // prepare
        int slen = s.length(), plen = p.length();
        vector<int> match_pos(1, 0);
        vector<int> new_match_pos;
        match_pos.reserve(slen + 1);
        new_match_pos.reserve(slen + 1);
        // dynamic programming
        for (int p_idx = 0; p_idx < plen; p_idx++) {
            char ch = p[p_idx];
            if (ch == '*') {
                if (p_idx > 0 && p[p_idx - 1] == '*') continue;
                for (int i = match_pos.front(); i <= slen; i++)
                    new_match_pos.push_back(i);
            } else if (ch == '?') {
                for (auto &e : match_pos)
                    if (e + 1 <= slen) new_match_pos.push_back(e + 1);
            } else {
                for (auto &e : match_pos)
                    if (e + 1 <= slen && s[e] == ch) new_match_pos.push_back(e + 1);
            }
            match_pos.swap(new_match_pos);
            new_match_pos.clear();
            if (match_pos.empty()) return false;
        }
        return match_pos.back() == slen;
    }

};

A a trick.

// Runtime: 36ms, beat 53.63%
class Solution {
public:
    bool isMatch(string s, string p) {
        // trick
        int slen = s.length(), plen = p.length();
        if (plen - count(p.begin(), p.end(), '*') > slen) return false;
        // prepare
        vector<int> match_pos(1, 0);
        vector<int> new_match_pos;
        match_pos.reserve(slen + 1);
        new_match_pos.reserve(slen + 1);
        // dynamic programming
        for (int p_idx = 0; p_idx < plen; p_idx++) {
            char ch = p[p_idx];
            if (ch == '*') {
                if (p_idx > 0 && p[p_idx - 1] == '*') continue;
                for (int i = match_pos.front(); i <= slen; i++)
                    new_match_pos.push_back(i);
            } else if (ch == '?') {
                for (auto &e : match_pos)
                    if (e + 1 <= slen) new_match_pos.push_back(e + 1);
            } else {
                for (auto &e : match_pos)
                    if (e + 1 <= slen && s[e] == ch) new_match_pos.push_back(e + 1);
            }
            match_pos.swap(new_match_pos);
            new_match_pos.clear();
            if (match_pos.empty()) return false;
        }
        return match_pos.back() == slen;
    }

};

Text Justification :hard:

// Runtime: 0ms
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> results;
        int cnt = 0;
        for (int i = 0; i < words.size(); ) {
            int line_width = 0, j = i;
            for (; j < words.size(); j++) {
                line_width += words[j].length();
                if (line_width + (j-i) > maxWidth) {
                    line_width -= words[j].length();
                    break;
                };
            }
            string tmp;
            if (j == words.size() || j - i == 1) {
                for (int k = i; k < j; k++) {
                    if (k > i) tmp.append(1, ' ');
                    tmp += words[k];
                }
                tmp.append(maxWidth - tmp.length(), ' ');
            } else {
                int num_spaces = (maxWidth - line_width) / (j - i - 1);
                int num_extra_spaces = (maxWidth - line_width) % (j - i - 1);
                for (int k = i; k < j; k++) {
                    if (k > i) {
                        if (k - i <= num_extra_spaces) tmp.append(num_spaces + 1, ' ');
                        else tmp.append(num_spaces, ' ');
                    }
                    tmp += words[k];
                }
            }
            results.push_back(tmp);
            i = j;
        }
        return results;
    }
};

July 13, 2016

String to Integer (atoi) (easy)

Max Points on a Line :hard:

Choose a node as one point of the line and check other points. O(n^2)

// Runtime: 8ms, beat 99.44%
/**
  * Definition for a point.
  * struct Point {
  *     int x;
  *     int y;
  *     Point() : x(0), y(0) {}
  *     Point(int a, int b) : x(a), y(b) {}
  * };
  */
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        int result = 0;
        vector<double> slopes(points.size());
        for (int i = 0; i < points.size(); i++) {
            int cnt_same_x = 1, cnt_same = 1;  // including itself
            int k = 0;  // number of nodes not in the same vertical line
            for (int j = i + 1; j < points.size(); j++) {
                int dx = points[i].x - points[j].x, dy = points[i].y - points[j].y;
                if (dx == 0) {cnt_same_x++; cnt_same+=(dy==0); continue;}
                slopes[k++] = 1.0*dy/dx;
            }
            result = max(result, cnt_same_x);
            sort(slopes.begin(), slopes.begin() + k);
            for (int j1 = 0, j2 = 0; j1 < k; j1 = j2) {
                while (j2 < k && fabs(slopes[j1]-slopes[j2]) < 1e-5) j2++;
                result = max(result, j2 - j1 + cnt_same);
            }
        }
        return result;
    }
};

July 11, 2016

Binary Tree Level Order Traversal (easy)

// Runtime: 8ms, beat 11.75%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<pair<TreeNode*, int>> q;
        if (root) q.emplace(root, 0);
        while (!q.empty()) {
            TreeNode* ptr = q.front().first;
            int level = q.front().second;
            q.pop();
            if (level + 1> result.size())
                result.push_back(vector<int>(1, ptr->val));
            else
                result.back().push_back(ptr->val);
            if (ptr->left) q.emplace(ptr->left, level+1);
            if (ptr->right) q.emplace(ptr->right, level+1);
        }
        return result;
    }
};

Word Ladder II :hard:

Fast implementation from the discussion… (My first implementation takes 500ms…)

Ideas

• Double-ended BFS. Visited words are remove from the dictionary.
• Recover the paths

// Runtime: 85ms, beat 86.38%
class Solution {
    public:
    vector<vector<string>> findLadders(string beginWord, string endWord,
                                        unordered_set<string> &dict) {
        int dis = INT_MAX;
        unordered_map<string, vector<string>> nexts;
        if (beginWord != endWord) {
            unordered_set<string> words1, words2;
            words1.insert(beginWord);
            words2.insert(endWord);
            dis = findLaddersHelper(words1, words2, dict, nexts, true, 1);
        }
        vector<vector<string>> result;
        if (dis == INT_MAX) return result;
        vector<string> ladder(dis + 1);
        getPath(0, beginWord, endWord, nexts, ladder, result);
        return result;
    }

    private:
    // return distance
    int findLaddersHelper(unordered_set<string> &words1,
                          unordered_set<string> &words2,
                          unordered_set<string> &dict,
                          unordered_map<string, vector<string>> &nexts,
                          bool fwd, int dis) {
        if (words1.empty()) return INT_MAX;
        if (words1.size() > words2.size())
            return findLaddersHelper(words2, words1, dict, nexts, !fwd, dis);
        for (auto word : words1) dict.erase(word);
        for (auto word : words2) dict.erase(word);
        unordered_set<string> words3;
        bool reach = false;
        for (auto prv_word : words1) {
            string word = prv_word;
            for (auto &ch : word) {
                char ch_bak = ch;
                for (ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == ch_bak) continue;
                    if (words2.find(word) != words2.end()) {
                        reach = true;
                        fwd ? nexts[prv_word].push_back(word)
                            : nexts[word].push_back(prv_word);
                    } else if (!reach && dict.find(word) != dict.end()) {
                        words3.insert(word);
                        fwd ? nexts[prv_word].push_back(word)
                            : nexts[word].push_back(prv_word);
                    }
                }
                ch = ch_bak;
            }
        }
        return reach ? dis : findLaddersHelper(words2, words3, dict, nexts,
                                                !fwd, dis + 1);
    }
    void getPath(int dis, string beginWord, string &endWord,
                  unordered_map<string, vector<string>> &nexts,
                  vector<string> &ladder, vector<vector<string>> &result) {
        ladder[dis] = beginWord;
        if (beginWord == endWord) {
            result.push_back(ladder);
        } else {
            for (auto nxt_word : nexts[beginWord]) {
                getPath(dis + 1, nxt_word, endWord, nexts, ladder, result);
            }
        }
    }
};

July 10, 2016

Path Sum II (medium)

// Runtime: 16ms, beat 47.89%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int) x : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    void pathSumHelper(TreeNode *root, int sum, int level, vector<vector<int>> &result) {
        if (root == NULL) return;
        if (root->left || root->right) {
            int old_size = result.size();
            pathSumHelper(root->left, sum-root->val, level+1, result);
            pathSumHelper(root->right, sum-root->val, level+1, result);
            for (int i = old_size; i < result.size(); i++) {
                result[i][level] = root->val;
            }
        } else if (root->val == sum) {
            result.emplace_back(level + 1, root->val);
        }
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> result;
        pathSumHelper(root, sum, 0, result);
        return result;
    }
};

Binary Tree Paths (easy)

// Runtime: 4ms, beat 22.11%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> all;
        if (root == NULL) return all;
        string prefix = to_string(root->val) + "->";
        for (string str : binaryTreePaths(root->left)) {
            all.push_back(prefix + str);
        }
        for (string str : binaryTreePaths(root->right)) {
            all.push_back(prefix + str);
        }
        if (all.empty()) {
            all.push_back(to_string(root->val));
        }
        return all;
    }
};

Reverse Vowels of a String (easy)

// Runtime: 12ms, beat 75.90%
class Solution {
public:
    string reverseVowels(string s) {
        size_t i = s.find_first_of("aeiouAEIOU");
        size_t j = s.find_last_of("aeiouAEIOU");
        while (i!=std::string::npos && j!=std::string::npos && i<j) {
            char ch = s[i];
            s[i] = s[j];
            s[j] = ch;
            i = s.find_first_of("aeiouAEIOU", i+1);
            j = s.find_last_of("aeiouAEIOU", j-1);
        }
        return s;
    }
};

July 9, 2016

Binary Tree Right Side View (medium)

First implementation, traverse level by level.

// Runtime: 8ms, beats 3.36%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if (root == NULL) return result;
        vector<TreeNode*> crt, nxt;
        nxt.push_back(root);
        // traverse the tree level by level
        while (!nxt.empty()) {
            crt.swap(nxt);
            result.push_back(crt.back()->val);
            nxt.clear();
            for (auto ptr : crt) {
                if (ptr->left) nxt.push_back(ptr->left);
                if (ptr->right) nxt.push_back(ptr->right);
            }
        }
        return result;
    }
};

A better implementation

// Runtime: 4ms, beats 27.47%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    void visit(TreeNode* root, int level, vector<int> &result) {
        if (root == NULL) return;
        if (result.size() < level+1) result.resize(level+1);
        result[level] = root->val;
        visit(root->left, level+1, result);
        visit(root->right, level+1, result);
    }
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        visit(root, 0, result);
        return result;
    }
};

Number of Islands (medium)

// Runtime: 8ms, beats 53.68%
class Solution {
private:
    void flood(vector<vector<char>>& grid, int x, int y, int n, int m) {
        static int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
        grid[x][y] = '0';
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k], yy = y + dy[k];
            if (xx>=0 && xx<n && yy>=0 && yy<m && grid[xx][yy]=='1') {
                flood(grid, xx, yy, n, m);
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int n = grid.size(), m = grid.front().size();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '0') continue;
                count++;
                flood(grid, i, j, n, m);
            }
        }
        return count;
    }
};

No recursion, 12ms

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int n = grid.size(), m = grid.front().size();
        int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
        int count = 0;
        queue<pair<int,int>> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '0') continue;
                count++;
                q.emplace(i, j);
                grid[i][j]='0';
                while (!q.empty()) {
                    int x = q.front().first, y = q.front().second;
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int xx = x + dx[k], yy = y + dy[k];
                        if (xx>=0 && xx<n && yy>=0 && yy<m && grid[xx][yy]=='1') {
                            q.emplace(xx,yy);
                            grid[xx][yy]='0';
                        }
                    }
                }  // while
            }
        }
        return count;
    }
};

Minimum Size Subarray Sum (medium)

First implementation: O(n), two pointers.

// Runtime: 4ms
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT_MAX;
        vector<int> sum(nums.size() + 1, 0);
        for (int l = 1, r = 1; r <= nums.size(); r++) {
            sum[r] = sum[r-1] + nums[r - 1];
            while (sum[r] - sum[l-1] >= s) {
                result = min(result, r - l + 1);
                l++;
            }
        }
        return result == INT_MAX ? 0 : result;
    }
};

Second implementation, O(n log n), binary search.

// Runtime: 8ms
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT_MAX;
        vector<int> sum(nums.size() + 1, 0);
        for (int i = 1; i <= nums.size(); i++) {
            sum[i] = sum[i-1] + nums[i-1];
            // find largest j so that sum[i]-sum[j-1]>=s
            int l = 1, r = i;
            while (l <= r) {
                int mid = l + (r - l)/2;
                if (sum[i]-sum[mid-1] >= s) l = mid + 1;
                else r = mid - 1;
            }
            l--;
            if (sum[i] - sum[l-1] >= s)
                result = min(result, i-l+1);
        }
        return result == INT_MAX ? 0 : result;
    }
};

Third implementation: O(n log n), binary search.

// Runtime: 12ms
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT_MAX;
        vector<int> sum(nums.size() + 1, 0);
        for (int i = 1; i <= nums.size(); i++) {
            sum[i] = sum[i-1] + nums[i-1];
            if (sum[i] >= s) {
                auto ub = upper_bound(sum.begin(), sum.begin()+i, sum[i]-s);
                int start = ub - sum.begin();
                result = min(result, i - start + 1);
            }
        }
        return result == INT_MAX ? 0 : result;
    }
};

Count Primes (easy)

First implementation

// Runtime: 376ms, 20.85%
class Solution {
public:
    int countPrimes(int n) {
        vector<bool> f(n, true);
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (f[i]) {
                count++;
                for (int j = i + i; j < n; j += i) f[j]=false;
            }
        }
        return count;
    }
};

Second implementation

// Runtime: 56ms, 80.83%
class Solution {
public:
    int countPrimes(int n) {
        bool f[n];
        fill(f, f+n, true);
        for (int i = 2; i * i< n; i++) {
            if (!f[i]) continue;
            for (int j = i * i; j < n; j += i) f[j] = false;
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            count += f[i];
        }
        return count;
    }
};

Search in Rotated Sorted Array :hard:

Ideas:

• Find the index of the minimum element in the array.
• Normal binary search in the proper range of the vector>

// Runtime: 4ms
class Solution {
private:
    int binSearch(vector<int>& nums, int target, int l, int r) {
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) r = mid - 1;
            else l = mid + 1;
        }
        return -1;
    }
public:
    int search(vector<int>& nums, int target) {
        // special cases
        if (nums.empty()) return -1;
        if (nums.front() <= nums.back())
            return binSearch(nums, target, 0, nums.size() - 1);
        // find the index of the minimum element
        int l = 0, r = nums.size() - 1;
        while (l + 1 < r) {
            int mid = ((long long)l + r) >> 1;
            if (nums[mid] > nums[l]) l = mid;
            else r = mid;
        }
        if (target < nums[r]) {
            return -1;
        } if (target <= nums.back())
            return binSearch(nums, target, r, nums.size() - 1);
        else
            return binSearch(nums, target, 0, r-1);
    }
};

Find Minimum in Rotated Sorted Array II :hard:

The worst case is something like this [1,1,1,1,0,1,1,1,1,1].
I think we have to scan over the complete vector so to figure whether there is anything smaller than 1.
The solution is a variation of the binary search.

// Runtime: 8ms, 23.35%
class Solution {
public:
    int findMin(vector<int>& nums) {
        // special cases
        if (nums.empty()) return 0;
        if (nums.front() < nums.back()) return nums.front();
        // normal cases
        int l = 0, r = nums.size() - 1;
        while (l + 1 < r) {
            if (nums[l] == nums[l+1]) l++;
            else if (nums[r] == nums[r-1]) r--;
            else {
                int mid = l + (r - l)/2;
                if (nums[mid] >= nums[l]) l = mid;
                else r = mid;
            }
        }
        return min(nums[l], nums[r]);
    }
};

Find Minimum in Rotated Sorted Array (medium)

// Runtime: 4ms, beats 23.06%
class Solution {
public:
    int findMin(vector<int>& nums) {
        // special cases
        if (nums.empty()) return 0;
        if (nums.front() <= nums.back()) return nums.front(); // not rotated
        // normal cases
        int l = 0, r = nums.size() - 1;
        while (l + 1 < r) {
            int mid = l + (r - l)/2;
            if (nums[mid] > nums[l]) l = mid;
            else r = mid;
        }
        return min(nums[l], nums[r]);
    }
};

Min Stack (easy)

An implementation using vector. I don’t know whether I should use vectors, LOL.

// Runtime: 56ms, beats 25.33%
class MinStack {
    vector<int> vec;
    vector<int> min_element;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        vec.push_back(x);
        if (min_element.empty()) {
            min_element.push_back(x);
        } else {
            min_element.push_back(min(min_element.back(), x));
        }
    }

    void pop() {
        vec.pop_back();
        min_element.pop_back();
    }

    int top() {
        return vec.back();
    }

    int getMin() {
        return min_element.back();
    }
};

/**
  * Your MinStack object will be instantiated and called as such:
  * MinStack obj = new MinStack();
  * obj.push(x);
  * obj.pop();
  * int param_3 = obj.top();
  * int param_4 = obj.getMin();
  */

House Robber III (medium)

// Runtime: 12ms, beats 76.88%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
private:
    void robHelper(TreeNode* root, int &rob, int &dont_rob) {
        if (root == NULL) {
            rob = 0;
            dont_rob = 0;
            return;
        }
        int rob1, dont_rob1, rob2, dont_rob2;
        robHelper(root->left, rob1, dont_rob1);
        robHelper(root->right, rob2, dont_rob2);
        rob = root->val + dont_rob1 + dont_rob2;
        dont_rob = max(rob1, dont_rob1) + max(rob2, dont_rob2);
    }
public:
    int rob(TreeNode* root) {
        int rob, dont_rob;
        robHelper(root, rob, dont_rob);
        return max(rob, dont_rob);
    }
};

House Robber II (medium)

We need to decide whether we rob the first house.
The code could be shorter, I know I don’t have to use the vector money.

// Runtime: 0ms
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        vector<int> money(nums.size() + 1, 0);
        // don't rob the first house
        for (int i = 2; i <= nums.size(); i++) {
            money[i] = max(money[i-1], money[i-2] + nums[i-1]);
        }
        int result = money.back();
        // rob the first house
        money[1] = nums[0];
        for (int i = 2; i < nums.size(); i++) {
            money[i] = max(money[i-1], money[i-2] + nums[i-1]);
        }
        return max(result, money[nums.size()-1]);
    }
};

House Robber (easy)

Dynamic programming

// Runtime: 0ms
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> money(nums.size() + 1, 0);
        money[1] = nums[0];
        for (int i = 2; i <= nums.size(); i++) {
            money[i] = max(money[i-1], money[i-2] + nums[i-1]);
        }
        return money.back();
    }
};

Another implementation with O(1) extra space.

// Runtime: 0ms
class Solution {
public:
    int rob(vector<int>& nums) {
        int dont_rob = 0, rob = 0;
        for (int i = 0; i < nums.size(); i++) {
            int new_rob = max(rob, dont_rob + nums[i]);
            dont_rob = rob;  // rob the previous house, maybe
            rob = new_rob;
        }
        return max(rob, dont_rob);
    }
};

First Bad Version (easy)

Oh, maybe I should always let “left, right, and middle” be long long…

// Runtime: 0ms
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l <= r) {
            int mid = l + (r - l)/2;
            if (isBadVersion(mid)) r = mid - 1;
            else l = mid + 1;
        }
        return ++r >= n ? n : r;
    }
};

H-Index II (medium)

// Runtime: 12ms, beat 38.31%
class Solution {
public:
    // hidx: the largest i so that (i == 0 || citations[n-i] >= i)
    int hIndex(vector<int>& citations) {
        if (citations.empty()) return 0;
        int n = citations.size();
        int l = 0, r = min(citations.back(), n);  // search range of hidx
        while (l <= r) {
            int mid = l + (r - l)/2;
            if (mid == 0 || citations[n-mid] >= mid) l = mid + 1;
            else r = mid - 1;
        }
        return max(0, l - 1);
    }
};

H-Index (medium)

// Runtime: 4ms, beat 21.37%
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int hidx = 0, n = citations.size();
        for (int i = 0; i < n; i++) {
            hidx = max(hidx, min(citations[i], n - i));
        }
        return hidx;
    }
};

July 8, 2016

Reverse Words in a String (medium)

Ideas

• First, remove the complete string
• Then, reverse each word and remove duplicated spaces.

// Runtime: 8ms, beat 45.83%
class Solution {
private:
    void reverseRange(string &s, int i, int j) {
        while (i < j) {
            char ch = s[i];
            s[i++] = s[j];
            s[j--] = ch;
        }
    }
public:
    void reverseWords(string &s) {
        int len = s.length();
        // reverse s
        reverseRange(s, 0, len - 1);
        // reverse words & remove duplicated nodes
        int new_len = 0;
        for (int i = 0, j = 0; i < len; i = j + 1) {
            // find the first ch of the word
            size_t found1 = s.find_first_not_of(" ", i);
            if (found1 == string::npos) break;
            i = found1;
            // find the last ch of the word
            size_t found2 = s.find_first_of(" ", i + 1);
            j = (found2 == string::npos) ? len - 1 : found2 - 1;
            // reverse word
            reverseRange(s, i, j);
            // remove space
            if (new_len>0) s[new_len++] = ' ';
            while (i <= j) {
                s[new_len++] = s[i++];
            }
        }
        s.resize(new_len);
    }
};

Surrounded Regions (medium)

First implementation

• Fill all surrounded regions with X, fill all non-surrounded regions with @
• @ -> X

// Runtime: 20ms, beat 32.19%
class Solution {
private:
    void flood(int i, int j, vector<vector<char>>& board, vector<pair<int,int>> &visit) {
        static int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
        // initialization
        bool hit_wall = false;
        int head = 0, tail = 0, n = board.size(), m = board.front().size();
        // search
        visit[tail++] = make_pair(i, j);
        board[i][j] = 'X';
        while (head < tail) {
            int x = visit[head].first;
            int y = visit[head++].second;
            for (int dir = 0; dir < 4; dir++) {
                int xx = x + dx[dir], yy = y + dy[dir];
                if (xx<0 || yy<0 || xx==n || yy==m) {
                    hit_wall = true;
                } else if (board[xx][yy]=='O') {
                    board[xx][yy]='X';
                    visit[tail++] = make_pair(xx, yy);
                }
            }
        }
        // recover
        if (hit_wall) {
            for (int i = 0; i < tail; i++) {
                board[visit[i].first][visit[i].second] = '@';
            }
        }
    }
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board.front().empty()) return;

        int n = board.size(), m = board.front().size();
        vector<pair<int,int>> visit(n*m);  // pre-assigned space

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O') flood(i, j, board, visit);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '@') board[i][j]='O';
            }
        }
    }
};

Second implementation

• Copy board as visited
• From four boundaries of visited, fill non-surrounded ‘O’ by ‘V’.
• Fill surrounded regions of board.

// Runtime: 20ms, beat 32.19%
class Solution {
private:
    void flood(vector<vector<char>>& visited, int x, int y, int n, int m) {
        static int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
        queue<pair<int,int>> q;
        q.emplace(x, y);
        visited[x][y] = 'V';
        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i], yy = y + dy[i];
                if (xx>=0 && xx<n && yy>=0 && yy<m && visited[xx][yy]=='O') {
                    q.emplace(xx, yy);
                    visited[xx][yy] = 'V';
                }
            }
        }
    }
public:
    void solve(vector<vector<char>>& board) {
        // corner test
        if (board.empty() || board.front().empty()) return;

        int n = board.size(), m = board.front().size();
        auto visited(board);

        // left, right
        for (int i = 0; i < n; i++) {
            if (visited[i][0] == 'O') flood(visited, i, 0, n, m);
            if (visited[i][m-1] == 'O') flood(visited, i, m-1, n, m);
        }
        // top, down
        for (int j = 1; j < m - 1; j++) {
            if (visited[0][j] == 'O') flood(visited, 0, j, n, m);
            if (visited[n-1][j] == 'O') flood(visited, n-1, j, n, m);
        }
        // O -> X
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O' && visited[i][j]!='V') board[i][j]='X';
            }
        }
    }
};

Find K Pairs with Smallest Sums (medium)

// Runtime: 20ms, beat ?(too new)%
class Solution {
public:
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int,int>> result;
        if (nums1.empty() || nums2.empty()) return result;  // [[!!!]]

        priority_queue<pair<int, pair<int,int>>> pq;
        pq.emplace(-nums1[0]-nums2[0], make_pair(0,0));

        while (!pq.empty() && k--) {
            int i = pq.top().second.first;
            int j = pq.top().second.second;
            pq.pop();
            result.emplace_back(nums1[i], nums2[j]);
            if (j==0 && i+1<nums1.size())
                pq.emplace(-nums1[i+1]-nums2[j], make_pair(i+1, j));
            if (j+1<nums2.size())
                pq.emplace(-nums1[i]-nums2[j+1], make_pair(i, j+1));
        }

        return result;
    }
};

Excel Sheet Column Number (easy)

class Solution {
public:
    int titleToNumber(string s) {
        long long result = 0;
        for (auto ch : s) result = result * 26 + (ch-'A'+1);
        return result;
    }
};

Excel Sheet Column Title (easy)

Recursion

// Runtime: 0ms
class Solution {
public:
    string convertToTitle(int n) {
        return n==0 ? "" : convertToTitle((n-1)/26).append(1, 'A'+((n-1)%26));
    }
};

Iteration

// Runtime: 0ms
class Solution {
public:
    string convertToTitle(int n) {
        string result;
        while (--n>=0) {
            result = string(1, 'A'+n%26) + result;
            n/=26;
        }
        return result;
    }
};

Merge Intervals :hard:

Sort and merge.

// Runtime: 26.79, beat %
/**
  * Definition for an interval.
  * struct Interval {
  *     int start;
  *     int end;
  *     Interval() : start(0), end(0) {}
  *     Interval(int s, int e) : start(s), end(e) {}
  * };
  */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> result;
        if (intervals.empty()) return result;
        // sort intervals
        sort(intervals.begin(), intervals.end(),
            [](const Interval &a, const Interval &b) -> bool
            {return a.start < b.start || (a.start == b.start && a.end < b.end);});
        // merge intervals
        result.push_back(intervals.front());
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start <= result.back().end) {
                result.back().end = max(result.back().end, intervals[i].end);  // merge
            } else {
                result.push_back(intervals[i]);  // new
            }
        }
        return result;
    }
};

July 7, 2016

Super Pow (medium)

Key observation: ab mod c == (a mod c)(b mod c) mod c

// Runtime: 12ms, beat ?%
class Solution {
private:
    int powMod(int x, int y) {
        int result{1};
        while (y > 0) {
            if (y & 1) result = (result * x) % 1337;
            y >>= 1;
            x = (x * x) % 1337;
        }
        return result;
    }
public:
    int superPow(int a, vector<int>& b) {
        int result = 1;
        a %= 1337;
        for (int i = 0; i < b.size(); i++) {
            result = (powMod(result, 10) * powMod(a, b[i])) % 1337;
        }
        return result;
    }
};

Intersection of Two Arrays II (easy)

First implementation.

// Runtime: 12ms, beat 37.52%
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        auto itr1 = nums1.begin();
        auto itr2 = nums2.begin();

        vector<int> result;
        while (itr1 != nums1.end() && itr2 != nums2.end()) {
            if (*itr1 < *itr2) itr1++;
            else if (*itr2 < *itr1) itr2++;
            else {
                result.push_back(*(itr1++));
                itr2++;
            }
        }

        return result;
    }
};

Second implementation. It is faster than the first implementation.
I guess this is because one of the vector is small compared to the other.

// Runtime: 8ms, beat 82.75%
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        auto itr1 = nums1.begin();
        auto itr2 = nums2.begin();

        vector<int> result;
        while (itr1 != nums1.end() && itr2 != nums2.end()) {
            if (*itr1 < *itr2) itr1 = lower_bound(itr1+1, nums1.end(), *itr2);
            else if (*itr2 < *itr1) itr2 = lower_bound(itr2+1, nums2.end(), *itr1);
            else {
                result.push_back(*(itr1++));
                itr2++;
            }
        }

        return result;
    }
};

Intersection of Two Arrays (easy)

// Runtime: 12ms, beat 42.47%
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        auto itr1 = nums1.begin();
        auto itr2 = nums2.begin();

        vector<int> result;
        while (itr1 != nums1.end() && itr2 != nums2.end()) {
            if (*itr1 < *itr2) itr1++;
            else if (*itr2 < *itr1) itr2++;
            else {
                result.push_back(*itr1);
                while (itr1 != nums1.end() && *itr1 == result.back()) itr1++;
                while (itr2 != nums2.end() && *itr2 == result.back()) itr2++;
            }
        }

        return result;
    }
};

Max Sum of Rectangle No Larger Than K :hard:

To illustrate, suppose the number of rows n is less than m.

• Suppose the first row is r1, the last row is r2, and the last column is col (O(n*n*m) choices).
• We check whether we can remove the first few columns so that the sum is no larger than k (binary search, O(log m)).
• The complexity is O(n*n*m*logm).

If n>m, the solution is similar, but with complexity O(m*m*n*log n).

// Runtime: 976ms, beat 96.52%
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size(), m = matrix.front().size();  // #row, #col
        int min_nm = min(n, m), max_nm = max(n, m);

        // initialization
        vector<vector<int>> s(n+1, vector<int>(m+1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + matrix[i-1][j-1];
            }
        }
        int result = INT_MIN;

        // dp
        for (int idx1 = 1; idx1 <= min_nm; idx1++) {
            for (int idx2 = idx1; idx2 <= min_nm; idx2++) {
                set<int> rect_sum({0});
                for (int idx3 = 1; idx3 <= max_nm; idx3++) {
                    int crt_sum = (n <= m) ? (s[idx2][idx3] - s[idx1-1][idx3])
                                    : (s[idx3][idx2] - s[idx3][idx1-1]);
                    auto itlow = rect_sum.lower_bound(crt_sum-k);
                    if (itlow != rect_sum.end())
                        result = max(result, crt_sum - *itlow);
                    rect_sum.insert(crt_sum);
                }
            }
        }
        return result;
    }
};

Valid Perfect Square (medium)

Binary search.

// Runtime: 0ms
class Solution {
public:
    bool isPerfectSquare(int num) {
        int l = 1, r = num;
        while (l <= r) {
            int mid = l + (r - l)/2;
            long long tmp = (long long)mid * mid;
            if (tmp == num) return true;
            else if (tmp > num) r = mid - 1;
            else l = mid + 1;
        }
        return false;
    }
};

Sum of Two Integers (easy)

// Runtime: 0ms
class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b;
            a = a ^ b;  // ignore the carry
            b = carry << 1;  // add back the carry in the next iteration
        }
        return a;
    }
};

CLOSED: [2016-07-07 Thu 11:02]</span>

Flatten Nested List Iterator (medium)

We use a stack to keep track of the status.
When hasNext() is called, we make sure that the top element of the stack points to the next integer.

// Runtime: 32ms, beat 64.43%
class NestedIterator {
    stack<pair<vector<NestedInteger>::const_iterator,
                vector<NestedInteger>::const_iterator>> st;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        st.emplace(nestedList.begin(), nestedList.end());
    }

    int next() {
        return (st.top().first++)->getInteger();
    }

    bool hasNext() {
        while (!st.empty()) {
            if (st.top().first == st.top().second) {
                st.pop();
            } else {
                if (st.top().first->isInteger()) return true;
                auto &tmp = (st.top().first++)->getList();
                st.emplace(tmp.begin(), tmp.end());
            }
        }
        return false;
    }
};

June 25, 2016

Word Pattern (easy)

BIJECTION!

// Runtime: 0ms
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        istringstream iss(str);
        vector<string> pattern_map(26, "");
        set<string> pattern_word;
        int i = -1;
        string substr;
        while (++i < pattern.size() && iss >> substr) {
            if (pattern_map[pattern[i] - 'a'] == "")  {
                if (pattern_word.count(substr) != 0) return false;
                pattern_map[pattern[i] - 'a'] = substr;
                pattern_word.insert(substr);
            }
            else if (pattern_map[pattern[i] - 'a'] != substr) return false;
        }
        return i == pattern.size() && iss.eof();
    }
};

June 24, 2016

Perfect Squares (medium)

I learned this cute idea of using a static vector in the discussion board.
The running time decreased from around 400ms to 50ms.

// Runtime: 52ms, beat 83.71%
class Solution {
public:
    int numSquares(int n) {
        static vector<int> f({0});
        int i = f.size();
        while (i <= n) {
            f.push_back(INT_MAX);
            for (int j = 1; j <= sqrt(i); j++) {
                f.back() = min(f.back(), f[i - j * j] + 1);
            }
            i++;
        }
        return f[n];
    }
};

Water and Jug Problem (medium)

I have the problem description….
CLOSED: [2016-06-24 Fri 11:16]</span>

// Runtime: 2ms
class Solution {
private:
    int gcd(int x, int y) {
        return y==0 ? x: gcd(y, x%y);
    }
public:
    bool canMeasureWater(int x, int y, int z) {
        if (z == 0) return true;
        return z <= x+y && z % gcd(x, y) == 0;
    }
};

Minimum Depth of Binary Tree (easy)

Got WA for two times…..

// Runtime: 12ms, beat 15.10%
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL) return minDepth(root->right) + 1;
        if (root->right == NULL) return minDepth(root->left) + 1;
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

Course Schedule II (medium)

Pretty much same as the previous solution.

// Runtime: 24ms, beat 85.63%
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        // Initialize the graph
        vector<int> out_deg(numCourses, 0);
        vector<vector<int>> in_edges(numCourses, vector<int>());
        for (auto e: prerequisites) {
            in_edges[e.second].push_back(e.first);
            out_deg[e.first]++;
        }
        // Initialize the queue
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (out_deg[i] == 0) {
                q.push(i);
                out_deg[i] = -1; // visited;
            }
        }
        // Find the order
        vector<int> order;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);
            out_deg[u] = -1;  //visited
            for (auto v : in_edges[u]) if ((--out_deg[v]) == 0) q.push(v);
        }
        // Return
        if (order.size() != numCourses) order.clear();
        return order;
    }
};

Course Schedule (medium)

Return true if and only if there is no cycle in the graph.

// Runtime: 20ms, beat 86.54%
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        // Initialize the graph
        vector<int> out_deg(numCourses, 0);
        vector<vector<int>> in_edges(numCourses, vector<int>());
        for (auto e: prerequisites) {
            in_edges[e.second].push_back(e.first);
            out_deg[e.first]++;
        }
        // Initialize the queue
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (out_deg[i] == 0) {
                q.push(i);
                out_deg[i] = -1; // visited;
            }
        }
        // Find the order
        int cnt = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cnt++;
            out_deg[u] = -1;  //visited
            for (auto v : in_edges[u]) if ((--out_deg[v]) == 0) q.push(v);
        }
        // Return
        return cnt == numCourses;
    }
};

Construct Binary Tree from Inorder and Postorder Traversal (medium)

Pretty much same as the previous problem.

// Runtime: 24ms, beat 71.64%
class Solution {
private:
    TreeNode* buildTreeHelper(const vector<int>& postorder, int post_l, int post_r,
                                const vector<int>& inorder, int in_l, int in_r,
                                const map<int,int> &val_to_pos) {
        if (post_l > post_r) return NULL;
        TreeNode* root = new TreeNode(postorder[post_r]);
        int in_root = val_to_pos.at(root->val);
        root->left = buildTreeHelper(postorder, post_l, post_l + in_root - in_l - 1,
                                    inorder, in_l, in_root - 1, val_to_pos);
        root->right = buildTreeHelper(postorder, post_l + in_root - in_l, post_r - 1,
                                    inorder, in_root + 1, in_r, val_to_pos);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // Construct a map from values to positions in "inorder"
        map<int, int> val_to_pos;
        for (int i = 0; i < inorder.size(); i++) val_to_pos[inorder[i]] = i;
        // Construct the tree
        return buildTreeHelper(postorder, 0, -1 + postorder.size(),
                                inorder, 0, -1 + inorder.size(), val_to_pos);
    }
};

Construct Binary Tree from Preorder and Inorder Traversal (medium)

Use a map to record the position of each value in the “inorder”.

// Runtime: 24ms, beat 79.85%
class Solution {
private:
    TreeNode* buildTreeHelper(const vector<int>& preorder, int pre_l, int pre_r,
                                const vector<int>& inorder, int in_l, int in_r,
                                const map<int,int> &val_to_pos) {
        if (pre_l > pre_r) return NULL;
        TreeNode* root = new TreeNode(preorder[pre_l]);
        int in_root = val_to_pos.at(root->val);
        root->left = buildTreeHelper(preorder, pre_l + 1, pre_l + in_root - in_l,
                                    inorder, in_l, in_root - 1, val_to_pos);
        root->right = buildTreeHelper(preorder, pre_l + in_root - in_l + 1, pre_r,
                                    inorder, in_root + 1, in_r, val_to_pos);
        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // Construct a map from values to positions in "inorder"
        map<int, int> val_to_pos;
        for (int i = 0; i < inorder.size(); i++) val_to_pos[inorder[i]] = i;
        // Construct the tree
        return buildTreeHelper(preorder, 0, -1 + preorder.size(),
                                inorder, 0, -1 + inorder.size(), val_to_pos);
    }
};

June 23, 2016

Binary Tree Inorder Traversal (medium)

// Runtime: 0ms
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        while (root != NULL) {s.push(root); root = root->left;}
        while (!s.empty()) {
            result.push_back(s.top()->val);
            TreeNode* crt = s.top()->right;
            s.pop();
            while (crt != NULL) {s.push(crt); crt = crt->left;}
        }
        return result;
    }
};

May 6, 2016

Range Sum Query - Mutable (medium)

Use a binary interval tree.

// Runtime: 64ms, beat 100.0%
class NumArray {
private:
    int n_;
    vector<int> sum_;

    int left(int idx) {return (idx<<1)+1;}
    int right(int idx) {return (idx<<1)+2;}

    int init(const vector<int> &nums, int idx, int l, int r) {
        if (l == r) return (sum_[idx] = nums[l]);
        int mid = l + (r - l)/2;
        return (sum_[idx] = init(nums, left(idx), l, mid)
                          + init(nums, right(idx), mid+1, r));
    }

    int update(int idx, int l, int r, int i, int val) {
        if (l == r) return (sum_[idx] = val);
        int mid = l + (r - l)/2;
        if (i <= mid)
            return (sum_[idx] = update(left(idx), l, mid, i, val) + sum_[right(idx)]);
        else
            return (sum_[idx] = sum_[left(idx)] + update(right(idx), mid + 1, r, i, val));
    }


    int sumRange(int idx, int l, int r, int i, int j) {
        if (l==i && r==j) return sum_[idx];
        int mid = l + (r - l)/2;
        int result = 0;
        if (i <= mid) result += sumRange(left(idx), l, mid, i, min(j, mid));
        if (j >= mid + 1) result += sumRange(right(idx), mid+1, r, max(i, mid+1), j);
        return result;
    }

public:
    NumArray(vector<int> &nums) : n_(nums.size()) {
        sum_.resize(n_ * 3);
        if (n_ > 0) init(nums, 0, 0, n_-1);
    }

    void update(int i, int val) {
        update(0, 0, n_ - 1, i, val);
    }

    int sumRange(int i, int j) {
        return sumRange(0, 0, n_-1, i, j);
    }
};

Range Sum Query - Immutable (easy)

Simple (tricky) dynamic programming…

// Runtime: 28ms, beat 100.0%
class NumArray {
private:
    vector<int> f;
public:
    NumArray(vector<int> &nums) {
        f.resize(nums.size());
        if (!nums.empty()) f.front() = nums.front();
        for (int i = 1; i < nums.size(); i++) {
            f[i] = f[i-1] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return f[j] - (i==0 ? 0 : f[i-1]);
    }
};

Isomorphic Strings (easy)

Oh, I should have read the problem description more carefully…

// Runtime: 8ms
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> map_st(256, -1), map_ts(256, -1);
        for (int i = 0; i < s.length(); i++) {
            if (map_st[s[i]] == -1) {
                if (map_ts[t[i]] != -1) return false;
                map_st[s[i]] = t[i];
                map_ts[t[i]] = s[i];
            }
            else if (map_st[s[i]] != t[i]) return false;
        }
        return true;
    }
};

Count Complete Tree Nodes (medium)

A recurive implementation. The key idea is to check whether the left tree is perfect.

// Runtime: 196ms, beat 43.99%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    int height(TreeNode* root) {
        return root == NULL ? 0 : 1 + height(root->left);
    }
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;
        int height_left = height(root->left);
        int height_right = height(root->right);
        if (height_left == height_right) {
            return (1 << height_left) + countNodes(root->right);
        } else {
            return countNodes(root->left) + (1 << height_right);
        }
    }
};

A faster implementation, calculate height (ane check whether the left subtree is perfect) iteratively.

// Runtime: 84ms, beat 91.5%
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;
        TreeNode* left = root->left, *right = root->right;
        int num = 1;
        while (right != NULL) {
            left = left->left;
            right = right->left;
            num <<= 1;
        }
        return num + (left == NULL ? countNodes(root->right) : countNodes(root->left));
    }
};

Palindrome Number (easy)

Remarks

• Negative integers are not palindrome numbers.
• Non-zero multiples of 10 are not palindrome numbers.

// Runtime: 72ms, beat 81.26%
class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0 || (x!=0 && x%10==0)) return false;
        int half = 0;
        while (x > half) {
            half = half * 10 + x % 10;
            x /= 10;
        }
        return (x==half || x==half/10);
    }
};

Reverse Linked List (easy)

Iteratively:

// Runtime: 8ms
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prv = NULL;
        while (head != NULL) {
            ListNode* nxt = head->next;
            head->next = prv;
            prv = head;
            head = next;
        }
        return prv;
    }
};

Recursively

// Runtime: 8ms
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *new_head = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return new_head;
    }
};

Palindrome Linked List (easy)linked_list:

First, use two pointers to fine the first node of the second half of the list. For example:

• 1 2 3 4(this one) 5 6
• 1 2 3 2(this one) 1

Then, reverse the second half of the list.
Finally, compare the first half and the reversed second half.

// Runtime: 28ms
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast != NULL) {
            slow = slow->next;
            fast = fast -> next;
            if (fast != NULL) fast = fast -> next;
        }
        // slow points to the first node of the second segment
        // reverse slow--->tail
        ListNode *prv = NULL;
        while (slow != NULL) {
            ListNode *nxt = slow->next;
            slow->next = prv;
            prv = slow;
            slow = nxt;
        }
        // prv points to the head of the reverse segment
        while (prv != NULL) {
            if (head->val != prv->val) return false;
            head = head->next;
            prv = prv->next;
        }
        return true;
    }
};

Create Maximum Number :hard:

High level ideas:

• Enumerate all valid length pair (k1, k2) so that k1+k2==k
• For each (k1, k2)
  • From nums1, find the maximum substring sub1 with length k1
  • From nums2, find the maximum substring sub2 with length k2
  • Concatenate sub1 and sub2 and get a solution.

How to find the maximum substring of nums with length k?

• Maintain a stack sub (initially empty)
• Scan nums, suppose we are now at nums[i]
  • Pop the top of sub, if
    • the remaining part of nums contains enough digits to fill sub
    • nums[i] is larger than the “top” element of sub
  • Push nums[i] into sub

// Runtime: 60ms, beat 75.2%
class Solution {
private:
    void maxNumber(const vector<int> &nums, int k, vector<int> &sub) {
        int n = nums.size();
        for (int i = 0, len = 0; i < n; i++) {
            while (len && len + n - i > k && nums[i] > sub[len - 1]) len--;
            if (len < k) sub[len++] = nums[i];
        }
    }
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> result(k, 0), tmp(k, 0);
        vector<int> sub1(k, 0), sub2(k, 0);
        for (int k1 = 0, k2 = k; k1 <= k; k1++, k2--) {
            if (k1 > nums1.size() || k2 > nums2.size()) continue;
            maxNumber(nums1, k1, sub1);
            maxNumber(nums2, k2, sub2);
            int flag = 0;  // 1 : tmp > result, 0 : tmp == result, -1: tmp < result
            for (int j = 0, i1 = 0, i2 = 0; j < k; j++) {
                tmp[j] = lexicographical_compare(sub2.begin() + i2, sub2.begin() + k2,
                    sub1.begin() + i1, sub1.begin() + k1) ? sub1[i1++] : sub2[i2++];
                if (flag == 0) {
                    if (tmp[j] < result[j]) {flag = -1; break;}
                    if (tmp[j] > result[j]) flag = 1;
                }
            }
            if (flag > 0) result.swap(tmp);
        }
        return result;
    }
};

Bulb Switcher (medium)

Let’s first see two examples.

• 9 = 1 * 9 = 3 * 3
• 60 = 1 * 60 = 2 * 30 = 3 * 20 = 4 * 15 = 5 * 12 = 6 * 10

One could verify that

• Bulb with a square number id: on
• Bulb with non-square number id: off

Solution: Given n, return the number of square numbers between 1 and n.

// Runtime: 0ms
class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

April 27, 2016

Add Digits (easy)

A straightforward solution.

// Runtime: 12ms
class Solution {
public:
    int addDigits(int num) {
        int result = 0;
        while (num) {
            result += num % 10;
            if (result >= 10)
                result = result / 10 + result - 10;
            num /= 10;
        }
        return result;
    }
};

A smarter solution learned from the discussion board.

// Runtime: 8ms
class Solution {
public:
    int addDigits(int num) {
        return 1 + (num - 1) % 9;
    }
};

April 25, 2016

Number of Digit One :hard:math:

Ideas:

• Let’s write n as n=[n1][x][n2] (e.g., 12345 = [12][3][45]).
• We want to now how many non-negative integers less than or equal to n looks like [len(n1)][x][len(n2)].

Here, the length of the first part equals to the length of n1.
Here, the length of the last part equals to the length of n2.

• How many?
  • Suppose the first part is in [0, n1-1], there are n1*pow(10, len(n2)) such integers.
  • Suppose the second part is n1.
    • If x==1, there are n2 such integers.
    • If x>1, there are pow(10, len(n2)) such integers.
    • If x==0, there is no such integers.

// Runtime: 0ms
class Solution {
public:
    int countDigitOne(int n) {
        int n1 = n / 10, x = n % 10, n2 = 0;  // n = [n1][x][n2];
        long long count = 0, mask = 1;
        while (mask <= n) {
            // Update count
            count += n1 * mask;
            if (x > 1) count += mask;
            else if (x == 1) count += n2 + 1;
            // Update [n1][x][n2]
            n2 += x * mask; // mask = [0][1][0..(n2)..0]
            x = n1 % 10;
            n1 = n1 / 10;
            mask *= 10;
        }
        return count;
    }
};

Reverse String (easy)

A super easy problem before dinner…

class Solution {
public:
    string reverseString(string s) {
        return string(s.rbegin(), s.rend());
    }
};

Word Ladder (medium)

Solution: BFS

// Runtime: 268ms, beat 72.66%
class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        // Special cases
        if (wordList.find(endWord) == wordList.end()) return 0;
        if (beginWord == endWord) return 1;
        // Prepare
        unordered_set<string> dict(wordList);
        queue<string> bfs;
        bfs.emplace(beginWord);
        dict.erase(beginWord);
        int len = beginWord.length();
        int dist = 0;
        // BFS
        while (!bfs.empty()) {
            int bfs_size = bfs.size();
            dist++;
            // expand a level
            while ((bfs_size--) > 0) {
                string crt_str = bfs.front();
                bfs.pop();
                for (int i = 0; i < len; i++) {
                    char bak = crt_str[i];
                    for (char new_ch = 'a'; new_ch <= 'z'; new_ch++) {
                        if (new_ch == bak) continue;
                        crt_str[i] = new_ch;
                        auto itr = dict.find(crt_str);
                        if (itr != dict.end()) {
                            if (crt_str == endWord) return dist + 1;
                            dict.erase(itr);
                            bfs.emplace(crt_str);
                        }
                    }
                    crt_str[i] = bak;
                }
            }
        }
        return 0;
    }
};

Word Search (medium)

Solution

• DFS
• Use board to do the backtrack.

// Runtime: 28ms, beat 71.06%
class Solution {
private:
    bool dfs(vector<vector<char>> &board, const string &word,
        int x, int y, int len) {

        // Directions
        static int delta_x[4] = {-1,0,0,1};
        static int delta_y[4] = {0,-1,1,0};
        // Check
        if (len == word.length() - 1) {
            return true;
        }
        char tmp_board = board[x][y];
        board[x][y] = ' ';
        // Search
        for (int i = 0; i < 4; i++) {
            int xx = x + delta_x[i];
            if (xx < 0 || xx >= board.size()) continue;
            int yy = y + delta_y[i];
            if (yy < 0 || yy >= board.front().size()) continue;
            if (board[xx][yy] == word[len + 1] && dfs(board, word, xx, yy, len + 1)) {
                board[x][y] = tmp_board;  // recover board
                return true;
            }
        }
        board[x][y] = tmp_board;
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.front().size(); j++) {
                if (board[i][j] == word[0] && dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
};

Word Search II :hard:trie:

Solution:

• Build a Trie tree, and use DFS to search the board.
• Codes without the deconstruction of Trie can pass all the test cases. But I don’t think that’s good.

// Without deconstruction: 61, beat 81.16%
// With deconstruction: 124ms
class Solution {
private:
    class TrieNode {
    public:
        TrieNode* next[26];
        int word_idx{-1};
        // Initialize your data structure here.
        TrieNode() {memset(next, 0, sizeof(next));}
    };
public:
    void dfs(const vector<vector<char>>& board, const vector<string>& words,
        vector<vector<TrieNode*>> &flag_trie, int x, int y,
        vector<string> &board_words) {
        // Directions
        static int delta_x[4] = {-1,0,0,1};
        static int delta_y[4] = {0,-1,1,0};
        // Check the current word
        TrieNode* crt_trie = flag_trie[x][y];
        if (crt_trie->word_idx != -1) {
            board_words.push_back(words[crt_trie->word_idx]);
            crt_trie->word_idx = -1;  // remove the word, avoid duplicates in board_words
        }
        // Search
        for (int i = 0; i < 4; i++) {
            int xx = x + delta_x[i];
            if (xx < 0 || xx >= board.size()) continue;
            int yy = y + delta_y[i];
            if (yy < 0 || yy >= board.front().size()) continue;
            if (!flag_trie[xx][yy]) {
                flag_trie[xx][yy] = crt_trie->next[board[xx][yy]-'a'];
                if (flag_trie[xx][yy] != NULL) {
                    dfs(board, words, flag_trie, xx, yy, board_words);
                    flag_trie[xx][yy] = NULL;
                }
            }
        }
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        // Construct a Trie tree
        TrieNode* trie_root = new TrieNode();
        for (int i = 0; i < words.size(); i++) {
            TrieNode* crt = trie_root;
            for (char ch: words[i]) {
                if (crt->next[ch-'a'] == NULL) crt->next[ch-'a'] = new TrieNode();
                crt = crt->next[ch-'a'];
            }
            crt->word_idx = i;
        }
        // Prepare for the DFS
        vector<vector<TrieNode*>> flag_trie(board.size(),
            vector<TrieNode*>(board.front().size(), NULL));
        vector<string> board_words;
        // DFS
        for (int x = 0; x < board.size(); x++) {
            for (int y = 0; y < board.front().size(); y++) {
                TrieNode* trie_crt = trie_root->next[board[x][y]-'a'];
                if (trie_crt != NULL) {
                    flag_trie[x][y] = trie_crt;
                    dfs(board, words, flag_trie, x, y, board_words);
                    flag_trie[x][y] = NULL;
                }
            }
        }
        // Destroy the Trie tree
        queue<TrieNode*> q;
        q.push(trie_root);
        while (!q.empty()) {
            for (int j = 0; j < 26; j++) {
                if (q.front()->next[j] != NULL) {
                    q.push(q.front()->next[j]);
                }
            }
            delete q.front();
            q.pop();
        }
        // Return
        return board_words;
    }
};

Add and Search Word - Data structure design (medium)trie:

Solution: Build a Trie tree to store words, and use DFS to search the work.

// Runtime: 80ms, beat 79.16%
class WordDictionary {
private:
    struct TrieNode {
    public:
        TrieNode* next[26];
        int count{0};
        // Initialize your data structure here.
        TrieNode() {
            memset(next, 0, sizeof(next));
        }
    };
    TrieNode* root = new TrieNode();

    bool search_dfs(TrieNode* crt, const string &word, int idx) {
        if (crt == NULL) return false;
        if (idx == word.length()) return crt->count > 0;
        if (word[idx] == '.') {
            for (int i = 0; i < 26; i++) {
                if (search_dfs(crt->next[i], word, idx + 1)) return true;
            }
            return false;
        } else {
            return search_dfs(crt->next[word[idx]-'a'], word, idx + 1);
        }
    }
public:
    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode* crt = root;
        for (char ch: word) {
            if (crt->next[ch-'a'] == NULL) {
                crt->next[ch-'a'] = new TrieNode();
            }
            crt = crt->next[ch-'a'];
        }
        crt->count++;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return search_dfs(root, word, 0);
    }
};

Implement Trie (Prefix Tree) (medium)trie:

Notes:

• Using TrieNode* next[26] is faster than vector<TrieNode*> next.
• Codes without the deconstruction of Trie can pass all the test cases. But I don’t think that’s good.

// Without deconstruction: 56ms, beat 75.89%
// With deconstruction: 112ms
class TrieNode {
public:
    TrieNode* next[26];
    int count{0};
    // Initialize your data structure here.
    TrieNode() {
        memset(next, 0, sizeof(next));
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    ~Trie() {
        queue<TrieNode*> q;
        q.push(root);
        while (!q.empty()) {
            for (int j = 0; j < 26; j++) {
                if (q.front()->next[j] != NULL) {
                    q.push(q.front()->next[j]);
                }
            }
            delete q.front();
            q.pop();
        }
    }
    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode* crt = root;
        for (char ch: word) {
            if (crt->next[ch-'a'] == NULL) {
                crt->next[ch-'a'] = new TrieNode();
            }
            crt = crt->next[ch-'a'];
        }
        crt->count++;
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode* crt = root;
        for (char ch: word) {
            if ((crt = crt->next[ch-'a']) == NULL) return false;
        }
        return crt->count > 0;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* crt = root;
        for (char ch: prefix) {
            if ((crt = crt->next[ch-'a']) == NULL) return false;
        }
        return true;
    }

private:
    TrieNode* root;
};

April 23, 2016

Letter Combinations of a Phone Number (medium)dfs:

// Runtime: 0ms
class Solution {
  public:
    void dfs(int pos, const string &digits, string &crt_str, vector<string> &results) {
        static vector<string> map{" ", "?", "abc", "def", "ghi", "jkl", "mno",
                                  "pqrs", "tuv", "wxyz"};
        for (char ch:map[digits[pos]-'0']) {
            crt_str[pos] = ch;
            if (pos + 1 == digits.length()) results.push_back(crt_str);
            else dfs(pos+1, digits, crt_str, results);
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return vector<string>();
        vector<string> results;
        string crt_str(digits);
        dfs(0, digits, crt_str, results);
        return results;
    }
};

Candy :hard:greedy:

Greedy

• Initially, every kid has 1 candy.
• Scan the ratings from left to right, if rantings[i]>ratings[i-1], make sure candy[i]>candy[i-1].
• Scan the ratings from the right to left, if rantings[i]>ratings[i+1], make sure candy[i]>candy[i+1].

// Runtime: 40ms, beat 22.09%
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candy(n, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1] && candy[i] <= candy[i-1])
                candy[i] = candy[i-1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1])
                candy[i] = candy[i+1] + 1;
        }
        return accumulate(candy.begin(), candy.end(), 0);
    }
};

April 22, 2016

Remove Duplicates from Sorted Array II (medium)

// Runtime: 16ms, beat 62.74%
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int last = 1;
        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] != nums[last-1]) nums[++last] = nums[i];
        }
        return min((int)nums.size(), last + 1);
    }
};

Remove Duplicates from Sorted Array (easy)

// Runtime: 32ms, beat 31.5%
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int last = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[last]) nums[++last] = nums[i];
        }
        return min((int)nums.size(), last + 1);
    }
};

Longest Valid Parentheses :hard:stack:

Solution

1. First scan
   • Use a stack to store indices of parentheses.
   • If the current char is ")" and the char corresponds to the stack top is "(", pop the stack.
2. Second scan
   • Between two “unmatched” parentheses, there is a valid parentheses substring.

// Runtime: 12ms, beat 15.07%
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> idx;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')' && !idx.empty() && s[idx.top()] == '(') idx.pop();
            else idx.push(i);
        }
        int result = 0, last_stack_top = s.length();
        while (!idx.empty()) {
            result = max(result, last_stack_top - idx.top() - 1);
            last_stack_top = idx.top();
            idx.pop();
        }
        return max(result, last_stack_top);
    }
};

Valid Palindrome (easy)string:

Easy one.

// Runtime: 12ms, beat 40.64%
class Solution {
public:
    bool isPalindrome(string s) {
        int i = -1, j = s.length();
        while ((++i) <= (--j)) {
            while (i < s.length() && !isalnum(s[i])) i++;
            while (j >= 0 && !isalnum(s[j])) j--;
            if (i<=j && ::tolower(s[i])!=::tolower(s[j])) return false;
        }
        return true;
    }
};

Best Time to Buy and Sell Stock with Cooldown

DP

• buy[i]: at the end of time i, we have bought stock
• sell[i]: at the end of time i, we have sold our stock
• Space: O(1) instead of O(n)

// Runtime: 8ms, beat 13.36%
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy[3] = {-INT_MAX, -INT_MAX, -INT_MAX};
        int sell[3] = {0,0,0};
        // compute (dp)
        int crt = 2, pre = 1, prepre = 0;
        for (int i = 0; i < prices.size(); i++) {
            crt = (crt + 1) % 3;
            pre = (pre + 1) % 3;
            prepre = (prepre + 1) % 3;
            buy[crt] = max(buy[pre], sell[prepre] - prices[i]);
            sell[crt] = max(sell[pre], buy[pre] + prices[i]);
        }
        return sell[crt];
    }
};

Best Time to Buy and Sell Stock III :hard:dp:

One solution is to use the codes for “Best Time to Buy and Sell Stock IV”. But the codes could be shorter.

// Runtime: 8ms, beat 66.62%
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit1 = 0, max_profit2 = 0;
        int lowest_buy_price1 = INT_MAX, lowest_buy_price2 = INT_MAX;

        for (auto p:prices){
            max_profit2 = max(max_profit2, p - lowest_buy_price2);
            lowest_buy_price2 = min(lowest_buy_price2, p - max_profit1);
            max_profit1 = max(max_profit1, p - lowest_buy_price1);
            lowest_buy_price1 = min(lowest_buy_price1, p);
        }

        return max_profit2;
    }
};

Best Time to Buy and Sell Stock IV :hard:dp:

Notes

• DP: O(2k) space, O(nk) time.
• For the special case where k>=prices.size()/2, we should use greedy. Because DP is too slow. (TLE for many times…)

// Runtime: 12ms, beat 21.44%
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // special case (greedy)
        if (k >= prices.size() / 2) {
            int result = 0;
            for (int i = 0; i < (int)prices.size() - 1; i++) {
                if (prices[i+1] > prices[i]) result += prices[i+1] - prices[i];
            }
            return result;
        }
        // init corner (dp)
        vector<vector<int>> buy(2, vector<int>(k+1, numeric_limits<int>::lowest()));
        vector<vector<int>> sell(2, vector<int>(k+1, 0));
        // compute (dp)
        for (int i = 0, crt = 0; i < prices.size(); i++, crt = 1 - crt) {
            int pre = 1 - crt;
            for (int kk = 1; kk <= k; kk++) {
                buy[crt][kk] = max(buy[pre][kk], sell[pre][kk-1] - prices[i]);
                sell[crt][kk] = max(sell[pre][kk], buy[pre][kk] + prices[i]);
            }
        }
        return sell[(prices.size() - 1) % 2][k];
    }
};

Best Time to Buy and Sell Stock II (medium)greedy:

Greedy solution, buy at lower prices and sell at higher prices.
It is “okay” to first sell and immediately buy at a time slot.
Because it is equivalent to doing nothing at that time slot.

// Runtime: 8ms, beat 17%
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 0; i < (int)prices.size() - 1; i++) {
            if (prices[i+1] > prices[i]) result += prices[i+1] - prices[i];
        }
        return result;
    }
};

Best Time to Buy and Sell Stock (easy)dp:

Idea: keep the lowest price seen so far.
If we sell at time i, we buy with the lowest price before time i.

// Runtime: 8ms, beat 20%
  class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int result = 0;
        int lowest_prices = prices.front();
        for (int i = 1; i < prices.size(); i++) {
            result = max(result, prices[i] - lowest_prices);
            lowest_prices = min(lowest_prices, prices[i]);
        }
        return result;
    }
};

April 21, 2016

Ugly Number (easy)

Super easy.. Before dinner..

// Runtime: 8ms
class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0) return false;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
};

Longest Substring Without Repeating Characters (medium)

Keep two pointers. One points to the start of the substring, one points to the end of it.
Move the first pointer if there are repeating characters.

// Runtime: 16ms, beat 67.72%
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last_appear(256, -1);
        int result = 0;
        for (int i = 0, j = 0; j < s.length();) {
            if (last_appear[s[j]] >= i) {
                i = last_appear[s[j]] + 1;
            }
            last_appear[s[j]] = j;
            j++;
            result = max(result, j - i);
        }
        return result;
    }
};

Multiply Strings (easy)

A straightforward implementation.

// Runtime: 28ms, beat 17.99%
class Solution {
public:
    string multiply(string num1, string num2) {
        string result(num1.length() + num2.length() + 1, '0');
        // for every digit of num2
        for (auto itr2 = num2.rbegin(); itr2 != num2.rend(); ++itr2) {
            auto itr_result = result.rbegin() + (itr2 - num2.rbegin());
            auto itr1 = num1.rbegin();
            int digit = *itr2 - '0', carry = 0;
            // result += num1 * digit
            while (carry || itr1 != num1.rend()) {
                if (itr1 != num1.rend()) carry += (*(itr1++) - '0') * digit;
                carry += *itr_result - '0';
                *(itr_result++) = (carry % 10) + '0';
                carry /= 10;
            }
        }
        // remove leading zeros
        auto start = result.find_first_not_of("0");
        return (start != std::string::npos) ? result.substr(start) : "0";
    }
};

Improvement (no speedup, don’t understand)

Ideas

• Initialize result with 0 instead of ‘0’
• Use tmp-carry*10 instead of tmp%10. (Discussion board: % is slower than subtraction and multiply)

// Runtime: 32ms
class Solution {
public:
    string multiply(string num1, string num2) {
        // init with 0
        string result(num1.length() + num2.length(), 0);

        // for every digit of num2
        for (auto itr2 = num2.rbegin(); itr2 != num2.rend(); ++itr2) {
            auto itr_result = result.rbegin() + (itr2 - num2.rbegin());
            auto itr1 = num1.rbegin();
            int digit = *itr2 - '0', carry = 0;
            // result += num1 * digit
            while (carry || itr1 != num1.rend()) {
                int tmp = *itr_result + carry;
                if (itr1 != num1.rend()) tmp += (*(itr1++)-'0') * digit;
                carry = tmp / 10;
                *(itr_result++) = tmp - carry * 10;
            }
        }

        // remove leading zeros
        auto start = result.find_first_not_of('\0');
        if (start != std::string::npos) {
            for(int i = start; i < result.size(); i++) result[i]+='0';
            return result.substr(start);
        }
        return "0";
    }
};

Add Binary (easy)math:string:

// Runtime: 4ms, beat 21.14%
class Solution {
public:
    string addBinary(string a, string b) {
        string c(max(a.length(), b.length()) + 1, '0');
        auto itra = a.rbegin(), itrb = b.rbegin(), itrc = c.rbegin();
        int carry = 0;
        while (carry || itra != a.rend() || itrb != b.rend()) {
            if (itra != a.rend()) carry += *(itra++) - '0';
            if (itrb != b.rend()) carry += *(itrb++) - '0';
            *(itrc++) = (carry % 2) + '0';
            carry /= 2;
        }
        if (c.front() == '0') return c.substr(1);
        return c;
    }
};

Add Two Numbers (medium)

I learned this implementation from the discussion board.
It seems like using a preHead makes things easier.
It’s basically a dummy head.
For example, I don’t have to check whether head==NULL or not.

// Runtime: 36ms, beat 63.7%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode preHead(0), *p = &preHead;
        int carry = 0;
        while (l1 || l2 || carry) {
            if (l1) carry += l1->val, l1 = l1->next;
            if (l2) carry += l2->val, l2 = l2->next;
            p->next = new ListNode(carry % 10);
            carry /= 10;
            p = p->next;
        }
        return preHead.next;
    }
};

Bitwise AND of Numbers Range (medium)

Try and set every bit of n to zero. If it the new value is no smaller than m, AND it with the current result.

// Runtime: 68ms, beat 56.73%
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int result = m;
        for (int x = 0, xx = 1; x <= 31; x++, xx<<=1){
            int tmp = n & ~xx;
            if (tmp >= m) result &= ~xx;
        }
        return result;
    }
};

Find this solution from the discussion board…. Awesome!

An explanation from the discussion board.

• If n>m, the final bit of the result will be zero.

Thus we shift both numbers down to the right one slot,
and recursively consider if those final digits match.

• When we finally find a non-zero match (n==m==1),

it must have occurred on the slot in the position shifted left,
as many times as we have shifted right. Thus the way the program works.

// Runtime: 72ms
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        return (n > m) ? (rangeBitwiseAnd(m >> 1, n >> 1) << 1) : m;
    }
};

Sqrt (medium)

Use binary search to find the square root of an integer.
Some notes

1. Be careful about the overflow problem…
2. Check the stopping criteria…

// Runtime: 8ms, beat 39.64%
class Solution {
public:
    int mySqrt(int x) {
        int left = 0, right = x;
        while (left <= right) {
            int mid = left + (right - left) >> 1;
            long long midmid = (long long)mid * mid;
            if (midmid == x) return mid;
            if (midmid < x) {
                left = mid + 1;
                if ((long long)left * left > x) return mid;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

April 20, 2016

Inverse Binary Tree (easy)

A super easy one…

// Runtime: 0ms
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return NULL;
        TreeNode *new_left = invertTree(root->right);
        TreeNode *new_right = invertTree(root->left);
        root->left = new_left;
        root->right = new_right;
        return root;
    }
};

Two Sum (easy)

A simple but slow solution using unordered_map.
P.S. Use unordered_map instead of map, if possible.

// Runtime: 16ms, beat 55.48%
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> result(2);
        for (int i = 0; i < nums.size(); i++) {
            m[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); i++) {
            auto itr = m.find(target - nums[i]);
            if (itr != m.end() && itr->second != i) {
                result[0] = i;
                result[1] = itr->second;
                break;
            }
        }
        return result;
    }
};

Improvement: Insert numbers into map lazily (no speedup).

// Runtime: 16ms, beat 55.48%
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            auto itr = m.find(target - nums[i]);
            if (itr != m.end()) {
                return vector<int>{i, itr->second};
            }
            m[nums[i]] = i;  // lazy
        }
        return vector<int>{0, 0};
    }
};

April 19, 2016

Plus One (easy)

//Runtime: 4ms, beat 3.4% (almost every one has this runtime)
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 1;
        auto itr = digits.end();
        do {
            *(--itr) += carry;
            if (*itr >= 10) {
                carry = 1;
                *itr -= 10;
            }
            else return digits;
        } while (itr != digits.begin());
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

Sbusets II (medium)

Ideas: Sort the numbers first.
If a number equals to its previous one, we only expand subsets generated in the previous iteration.
Otherwise, we expand all subsets we have generated.

//Runtime: 12 ms, beat 18.57%
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> results(1);  // empty set
        size_t last_start_pos = 0;  // first subset constructed in the last iter
        for (size_t nums_idx = 0; nums_idx < nums.size(); nums_idx++) {
            int n = nums[nums_idx];
            size_t i = (nums_idx == 0 || n != nums[nums_idx - 1]) ? 0 : last_start_pos;
            size_t crt_start_pos = results.size();
            for (; i < crt_start_pos; i++) {
                results.push_back(results[i]);
                results.back().push_back(n);
            }
            last_start_pos = crt_start_pos;
        }
        return results;
    }
};

Speedup: Resize results instead of pushing back.
Note: << has lower precedence than -.

// Runtime: 8 ms, beat 71.92%
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> results(1);  // empty set
        size_t last_start_pos = 0;  // first subset constructed in the last iter
        for (size_t nums_idx = 0; nums_idx < nums.size(); nums_idx++) {
            int n = nums[nums_idx];
            size_t old_results_size = results.size();
            size_t i = (nums_idx == 0 || n != nums[nums_idx - 1]) ? 0 : last_start_pos;
            results.resize((old_results_size<<1) - i);  // old_size + expand_size
            for (size_t j = old_results_size; i < old_results_size; i++, j++) {
                results[j] = results[i];
                results[j].push_back(n);
            }
            last_start_pos = old_results_size;
        }
        return results;
    }
};

Subsets (medium)

I think this is an easy problem… (Don’t forget the empty set.)

// Runtime: 4 ms, beat 83.38%
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> results(1);
        for (auto n:nums) {
            size_t crt_result_size = results.size();
            for (size_t i=0; i<crt_result_size; i++) {
                results.push_back(results[i]);
                results.back().push_back(n);
            }
        }
        return results;
    }
};

Insertion Sort List (medium)

I think this is an easy problem…

// Runtime: 24 ms, beat 87.82%
/**
  * 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;
        ListNode* sorted_head = head;
        ListNode* sorted_tail = head;
        ListNode* crt;
        while ((crt = sorted_tail->next) != NULL){
            if (crt->val >= sorted_tail->val) {
                // no need to sort
                sorted_tail = crt;
            } else {
                sorted_tail->next = crt->next;
                if (crt->val <= head->val) {
                    // new head
                    crt->next = head;
                    head = crt;
                } else {
                    ListNode* insert_after = head;
                    while (crt->val > insert_after->next->val) {
                        insert_after = insert_after->next;
                    }
                    crt->next = insert_after->next;
                    insert_after->next = crt;
                }
            }
        }
        return head;
    }
};

Remove Linked List Elements (easy)

// Runtime: 36 ms, beat 8.25%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != NULL && head->val == val) {
            head = head->next;
        }
        ListNode* ptr = head;
        while (ptr != NULL && ptr->next != NULL) {
            if (ptr->next->val == val) {
                ptr->next = ptr->next->next;
            } else {
                ptr = ptr->next;
            }
        }
        return head;
    }
};

The recursive version:

// Runtime: 36 ms, beat 8.25%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == NULL) return NULL;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

Merge Two Sorted Lists (easy)

// Runtime: 408 ms, beat 82.07%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

Merge k Sorted Lists :hard:

// Runtime: 424 ms, beat 37.5%
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode* head = NULL;
    ListNode* tail = NULL;
    auto comp = [] (ListNode** a, ListNode** b) -> bool { return (*a)->val > (*b)->val; };
    std::priority_queue<ListNode**, std::vector<ListNode**>, decltype(comp) > pq (comp);
    for (auto &ptr : lists) {
        if (ptr!=NULL) pq.push(&ptr);
    }
    while (!pq.empty()) {
      ListNode** top = pq.top();
      pq.pop();
      if (head == NULL) {
        head = tail = *top;
      } else {
        tail->next = *top;
        tail = tail->next;
      }
      (*top) = (*top)->next;
      if ((*top) != NULL) {
        pq.push(top);
      }
    }
    return head;
  }
};

Second solution, I learned this recursive implementation from the discussion board.

// Runtime: 408 ms, beat 82.07%
/**
/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        else if (l2 == NULL) return l1;
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    ListNode *mergeKLists(vector<ListNode*> &lists) {
        if (lists.empty()) return NULL;
        for (int step = 1; step < lists.size(); step<<=1) {
            int two_steps = step << 1;
            for (int i = 0; i < lists.size() - step; i += two_steps) {
                lists[i] = mergeTwoLists(lists[i], lists[i + step]);
            }
        }
        return lists.front();
    }
};

April 16, 2016

Rotate Array (easy)

// Runtime: 24 ms
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        // reverse all
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            swap(nums[i], nums[j]);
        }
        // reverse 0 ~ k-1
        for (int i = 0, j = k - 1; i < j; i++, j--) {
            swap(nums[i], nums[j]);
        }
        // reverse k ~ n-1
        for (int i = k, j = n - 1; i < j; i++, j--) {
            swap(nums[i], nums[j]);
        }
    }
};

November 2015

Happy Number (easy)

Don’t know how to write faster codes. Using set instead of unordered_set
also runs in 4ms.

// Runtime: 4 ms
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> appeared;
        while(1) {
            int old_n = n;
            n = 0;
            while (old_n > 0) {
                n += (old_n%10)*(old_n%10);
                old_n /= 10;
            }
            if (n == 1) {
                return true;
            }
            if (appeared.find(n) != appeared.end()) {
                return false;
            }
            appeared.insert(n);
        }
        return false;
    }
};

Maximum Depth of Binary Tree (easy)

// Runtime: 8ms
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root == NULL ? 0 : (max(maxDepth(root->left),maxDepth(root->right)) + 1);
    }
};

The following codes also run in 8ms.

/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;

        int res = 0;
        queue<pair<TreeNode*,int>> q;
        q.emplace(root, 1);

        while (!q.empty()) {
            TreeNode* ptr = q.front().first;
            int d = q.front().second;
            q.pop();
            res = max(res, d);
            if (ptr->left) q.emplace(ptr->left, d+1);
            if (ptr->right) q.emplace(ptr->right, d+1);
        }

        return res;
    }
};

Remove Nth Node From End of List (easy)

/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *ptr1 = head, *ptr2 = head;
        while (n--) prtr = ptr2->next;
        if (ptr2 == NULL) {
            return head -> next; // remove the head
        }
        while (ptr2->next != NULL) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        // ptr1->next is the nth node from the end
        ptr1->next = (ptr1->next)->next;
        return head;
    }
};

Search for a Range

A lazy version using STL.

// Runtime 12ms, beats 9.55%
  class Solution {                //
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          // first value that >= target
          auto lb = std::lower_bound (nums.begin(), nums.end(), target);
          if (*lb != target) {
              return vector<int>{-1,-1};
          }

          // first value that > target
          auto lb2 = std::lower_bound (lb, nums.end(), target + 1);
          return vector<int>{lb - nums.begin(), lb2 - nums.begin() - 1};
      }
  };

Write lower bound function.

// Runtime 12ms, beats 9.55%
class Solution {
public:
    int lowerbound(const vector<int> &nums, int target) {
        int l = 0, r = nums.size() -1;
        while (l < r - 1) {
            int mid = l + (r - l)/2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] >= target) return l;
        if (nums[r] >= target) return r;
        return nums.size();
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        // first value that >= target
        int l = lowerbound(nums, target);
        if (l == nums.size() || nums[l] != target) {
            return vector<int>{-1,-1};
        }

        // first value that > target
        int r = lowerbound(nums, target + 1);
        return vector<int>{l, r - 1};
    }
};

Palindrome Partitioning II :hard:

Use is_pal[i][j] to denote whether s[i..j] is a palindrome. Then use dynamic
programming to find the minimum cut.

class Solution {
public:
    int minCut(string s) {
        int slen = s.length();

        // is_pal[i][j]:= s[i..j] is a palindrome
        bool is_pal[slen][slen];
        for (int i = 0; i < slen; i++) {
            is_pal[i][i] = true;
            if (i+1 < slen) is_pal[i][i+1] = (s[i] == s[i+1]);
        }
        for (int k = 2; k < slen; k++) {
            for (int i = 0; i < slen - k; i++) {
                is_pal[i][i+k] = (s[i] == s[i+k]) && is_pal[i+1][i+k-1];
            }
        }

        int min_cut[slen];  // min_cut[i] = min cut of s[0..i]
        min_cut[0] = 0;
        for (int i = 1; i < slen; i++) {
            if (is_pal[0][i]) {
                min_cut[i] = 0;
                continue;
            }
            min_cut[i] = i;
            for (int j = 1; j <= i; j++) {
                if (is_pal[j][i]) {
                    min_cut[i] = min(min_cut[i], min_cut[j-1] + 1);
                }
            }
        }

        return min_cut[slen - 1];
    }
};