Single Element in a Sorted Array -- LeetCode 540

[Question]
Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

[Solution]
//--- C++ ---
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l=0, r=nums.size();
        int mid = 0;
        while (l+1<r) {
            mid = (l+r)>>1;
            if (nums[mid]==nums[mid^0x01])
                l = mid+1;
            else
                r = mid;
        }
        return nums[l];
    }
};

//--- Python ---
class Solution(object):
    def singleNonDuplicate(self, nums):
        lo, hi=0, len(nums)-1
        while lo<hi:
            m = (lo+hi)/2
            if nums[m]==nums[m^1]:
                lo = m+1
            else:
                hi = m
        return nums[lo]
         

Reverse Pairs -- LeetCode 493

[Question]

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.

[Analysis]
This is a typical problem for Binary Index Tree (BIT). Another solution is to use a BST with a smaller counter in each node -- but this solution will make time complexity O(N*N) for sorted input array. BIT is still a better solution.

[Solution]
class BIT {
    vector<int> nodes;
    int lowbit(int x) { return -x & x; }
public:
    BIT(int n) : nodes(n+1,0) {};
 
    void add(int pos, int val) {
        while (pos<nodes.size()) {
            nodes[pos]+=val;
            pos += lowbit( pos );
        }
    }
 
    int count(int pos) {
        int res =0;
        while (pos>0) {
            res += nodes[pos];
            pos -= lowbit( pos );
        }
        return res;
    }
};

typedef long long LL;

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<pair<LL,int> > sorted;
        for (int i=0; i<nums.size(); i++) {
            sorted.push_back({(LL)nums[i],i+1});
            sorted.push_back({(LL)nums[i]<<1, -i-1});
        }
        sort(sorted.begin(), sorted.end(), [](pair<LL,int>& a, pair<LL,int>& b) {
            return a.first< b.first || a.first==b.first && a.second>b.second;
        });
     
        unordered_map<LL,int> map;
        for (int i=0; i<sorted.size(); i++)
            map[sorted[i].second] = i;
     
     
        BIT tree(sorted.size());
        int res=0;
        for (int i=nums.size()-1; i>=0; i--) {
            res += tree.count(map[i+1]);
            tree.add(map[-i-1]+1,1);
        }
        return res;
    }
};

Evaluate Division -- LeetCode 399

[Question]

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

[Analysis]
Consider each equation as an edge in a directed graph, each string is a vertex, then the problem becomes to find a path for each pair of strings in the queries array.

Inspired by Floyd-Warshall algorithm, using a 2-D matrix to represent vertex A to vertex path (if exists), A[i][j] = A[i][k]*A[k][j], for k=0,...|v|-1.

[Solution]
class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        set<string> nodes;
        unordered_map<string, int> inv;
     
        for (auto& e:equations) {
            nodes.insert(e.first);
            nodes.insert(e.second);
        }
        int i=0;
        for (auto it= nodes.begin(); it!=nodes.end(); it++, i++)
            inv[*it] = i;
     
        vector<vector<double>> equ(nodes.size(), vector<double>(nodes.size(),-1.0));
        for (int i=0; i< nodes.size(); i++)
            equ[i][i]= 1.0;
         
        for (int i=0; i< equations.size(); i++) {
            int x = inv[equations[i].first];
            int y = inv[equations[i].second];
            equ[x][y] = values[i];
            equ[y][x] = 1.0 / values[i];
        }
     
        for (int k=0; k<nodes.size(); k++) {
            for (int i=0; i<nodes.size(); i++) {
                for (int j=i+1; j<nodes.size(); j++) {
                    if (equ[i][k]!=-1.0 && equ[k][j]!=-1.0) {
                        equ[i][j] = equ[i][k] * equ[k][j];
                        equ[j][i] = 1.0/ equ[i][j];
                    }
                }
            }
        }
     
        vector<double> res;
        for (auto& q: queries) {
            if (nodes.count(q.first) && nodes.count(q.second)) {
                int x= inv[q.first], y= inv[q.second];
                res.push_back( equ[x][y] );
            }
            else res.push_back(-1.0);
        }
        return res;
    }

};

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

};