Range Sum Query - Mutable -- LeetCode 307

[Question]

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

[Analysis]
By using brute force on array itself, the update() can be achieved in O(1) and the sumRange() in O(N). It is not optimal when sumRange() to be called more often.

An alternative way is to use Segment Tree. The Segment Tree is heap like data structure. Both update() and sumRange() can be achieved in O(LogN). Extra O(N) space is used though.

Another range sum problem is "Count of Range Sum".

[Solution]
//
//-- Segment Tree --
//
class NumArray {
    vector<int> seg;
    int n;
public:
    NumArray(vector<int> &nums) {
        n = nums.size();
        seg.resize(n<<1);
        for (int i=n; i< (n<<1); i++)  seg[i] = nums[i-n];
        for(int i=n-1; i>0; i--) seg[i] = seg[i<<1] + seg[i<<1|1];
    }

    void update(int i, int val) {
        int diff = val-seg[i+n];
        for( i+=n; i>0; i>>=1 )
            seg[i] += diff;
    }

    int sumRange(int i, int j) {
        int res=0;
        for (i+=n, j+=n; i<=j; i>>=1, j>>=1) {
            if (i&1) res+=seg[i++];
            if (!(j&1)) res+=seg[j--];
        }
        return res;
    }
};

Word Break -- LeetCode 139

[Quesion]
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

[Analysis]
Dynamic Programming: using one array A[n] to store whether first n letters of string s form a word sequence in dictionary, and A[0]= true,  A[i+1] will be true if A[j] == true and substr(j, i-j+1) is also a word in dictionary (0<=j<=i). The time complexity is O(N^2), space complexity is O(N).

DFS: try each prefix in dictionary recursively. Use a status memo to trim recursion branches.

Suppose Trie is built upon the word dictionary, Trie can help to get A[] initialized faster.

[Solution]
// -- Dynamic Programming --
class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        vector<bool> res(s.size()+1, false);
        res[0]=true;
        for (int i=0; i<s.size(); i++)
            for (int j=i; j>=0; j--)     //-- faster than moving forward --
                if (res[j] && wordDict.count(s.substr(j,i-j+1)) ) {
                    res[i+1] = true;
                    break;
                }
        return res.back();
    }
};

// -- DFS --
class Solution {
    unordered_set<string> seen; // -- to record failed branches
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if (wordDict.count(s)) return true;
        for (int i=0; i<s.size(); i++) {
            if (wordDict.count(s.substr(0,i+1)) ) {
                string ss = s.substr(i+1);
                if (seen.count(ss) ) continue;
                if (wordBreak(ss, wordDict))
                    return true;
                else seen.insert(ss);
            }
        }
        return false;
    }
};

House Robber ||| -- LeetCode 337

[Question]

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

[Analysis]
This is different from previous questions in this "House Robber" series. Assume S(n) is the max amount of money the robber can get at House[n],
       S(n) = max( S(n->left)+ S(n->right),
                H[n] + S(n->left->left) + S(n->left->right) + S(n->right->left) + S(n->right->right) )

So we can use DFS to accomplish this.

[Solution]
/**
 * 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 {
    int helper(TreeNode* root, int &lsum, int &rsum) {
        if (root==NULL) return 0;
     
        int ll=0, lr=0, rl=0, rr=0;
        lsum = helper(root->left, ll, lr);
        rsum = helper(root->right, rl, rr);
        return max( lsum+rsum, root->val+ll+lr+rl+rr );
    }
public:
    int rob(TreeNode* root) {
        int lsum=0, rsum=0;
        return helper(root, lsum, rsum);
    }

};

House Robber II -- LeetCode 213

[Question]

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

[Analysis]
Assume S(0, n) is the largest amount the thief can get from circle houses H[0,..n], and R(x,y) is the largest amount from linear houses H[x, x+1,...y], then
    S(0,n) = max( R(0,n-1), R(1, n-2) + H[n]).

Since R(x,y) can be calculated using the solution in House Robber, S(0,n) is resolved.

[Solution]
//--- Solution #1 ---
class Solution {
    int robber(vector<int>& n, int lf, int rt) {
        int a=0, b=0, c=0;
        for (int i=lf; i<rt; i++) {
            c = max(b, a+n[i]);
            a=b, b=c;
        }
        return c;
    }
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n= nums.size();
        return max( robber(nums, 0, n-1), robber(nums, 1, n-2)+ nums.back());
    }
};

//--- Solution #2 ---
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size()==1) return nums[0];
     
        int a=0, b=nums[0], c=0;
        int x=0, y=0, z=0;
        int res;
        for (int i=1; i<nums.size(); i++) {
            c = max(b, a+nums[i]);  //R0(i)->c, b->R0(i-1)
            z = max(y, x+nums[i]);  //R1(i)->z, x->R1(i-2)

            res = max( x + nums[i], b);

            a=b, b=c;
            x=y, y=z;
        }
        return res;
    }

};

House Robber -- LeetCode 198

[Question]

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

[Analysis]
Assume the S(n) is the largest amount the robber can get from H[0,1,...n],
        S(n) = max(  S(n-1), S(n-2) + H[n] )
       
Further, we can assume there are two additional house before H[0], with zero assets. Use dynamic programming from the beginning of the Houses, we can S(0),... S(n). S(n) is the answer.

[Solution]
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;

        int a=0, b=0, c=0;
        for (int i=0; i<nums.size(); i++) {
            c = max(b, a+nums[i]);
            a=b, b=c;
        }          
        return c;
    }

};

Longest Repeating Character Replacement -- LeetCode 424

[Question]

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

[Analysis]
Use a sliding window [j,i] on the string. When the length of the window (i-j+1 - count of most repeating letters) <= k, move ending point i forward and the sub strings in the window are candidates. When the length - count of most repeating letters > k, move starting point j forward until the sub string in window contains the candidate.

Similar to the "Minimum Window Sub-String" problem.

[Solution]
class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> counters(26,0);
        int j=0, max_cnt=0;
        int res = 0;
        for (int i=0; i<s.size(); i++) {
            counters[s[i]-'A']++;
            max_cnt = max(max_cnt, counters[s[i]-'A']);
            while (i-j+1 -max_cnt > k) {
                counters[s[j]-'A']--, j++;
                max_cnt = *max_element(counters.begin(), counters.end());
            }
            res = max(res, i-j+1);
        }

        return res;
    }
};

Single Number III -- LeetCode

[Question]

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

[Analysis]
By XOR all the elements, we can get the XOR result of the two single elements {A,B}. Since A!=B, there must one bit different between A and B. Therefore, divide all elements into two sets based on the bit value. XOR each set will give the two elements separately.

[Solution]
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sum = accumulate (nums.begin(), nums.end(), 0, bit_xor<int>());
        int diff = sum & (-sum);
       
        vector<int> res = {0,0};
        for (auto n: nums) {
            if (n & diff) res[0]^=n;
            else res[1]^=n;
        }
        return res;
    }

};

Longest Increasing Path in a Matrix -- LeetCode

[Question]

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

[Analysis]
Using DFS from each position of the matrix, travel on each possible paths, and get the maximum length that the position can reach. The length of path in each position can be reused. Therefore, an additional matrix is used to record the length information of each position. The time complexity and space complexity are both O(MxN), the size of matrix.

[Solution]
class Solution {
    vector<pair<int,int>> dd={{-1,0},{1,0},{0,1},{0,-1}};
 
    int searchPath(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& lens) {
        if (lens[i][j]!=0) return lens[i][j];
     
        int len=0;
        int temp = matrix[i][j];
        matrix[i][j] = INT_MIN;
        for (auto&d : dd) {
            int x = i+d.first, y=j+d.second;
            if (x>=0 && x<matrix.size() && y>=0 && y<matrix[0].size() && matrix[x][y]>temp) {
                len = max(len, searchPath(matrix, x, y, lens));
            }
        }
        matrix[i][j] = temp;
        lens[i][j] = 1 + len;
        return 1+len;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        vector<vector<int>> lens(matrix.size(), vector<int>(matrix[0].size(), 0));
     
        int res=1;
        for (int i=0; i<matrix.size(); i++) {
            for (int j=0; j< matrix[0].size(); j++) {
                res = max(res, searchPath(matrix, i, j, lens) );
            }
        }
        return res;
    }

};