Logic Wallbreaker

Wednesday, July 13, 2016

[Algorithm] Sliding Window Maximum

Sliding Window Maximum

Problem statement:

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,

Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Solution: Max stack based solution.

A first glance maybe we can solve this by using a max heap ordered by the value of the element, but we have to keep in mind one thing: the order of popping elements is not by value, it's by its actual index, and if we have a tie in value, we need to keep track all possible indices it occurs and only pop out this element when its possible indices reaches zero. This is somewhat laborous to maintain such a heap.

In fact for the problem, we only need to know the maximum of this window and the order of popping element out of the window is by its index in original array. So this should be a max heap problem instead of max heap.

Here's how to maintain the window:

We keep updating elements of current window in a stack, and as we move right the window by one each time, we update the max value. To make sure pop_front and push_back are efficient we can use a deque.

The key question here is how can we keep track of the maximum inside the window? We can easily do a O(k) search every time but this will run into O(kn) time complexity. Actually we can do better by discard those which is both indexed before current maximum and has a value less then the current maximum.

By doing so we can have better average runtime complexity, best case O(n) if original array is ascending, but can be as worst as O(nk) if original array is descending. But on array it will run in O(n) with a much smaller constant factor than k.

Here's the illustration of how we keep the window:

[1 2 3 4] 5 3 2 4 1
Current window: [4]
Next window before search: [4, 5]
Next window after search: [5]

Suppose we have window size of 4 and current window covers [1 2 3 4], in our current window we only keep [4] because popping [1, 2, 3] doesn't affect the maximum element. Once we push in 5, we will update the current maximum since the new element is bigger than old top.

1 2 3 4 [5 3 2 4] 1
Current window: [5 3 2 4]
Next window before search : [3, 2, 4, 1]
Next window after search: [4, 1]

Now with the same array, suppose we are covering [5, 4, 3, 2] this time. The next element is [1] and we are going to pop [5]. Since we are removing the current top, we need to do a search again for the new top and discard whatever is before this new top. And of course our new top will be [4] and whatever is before it will be discarded and newly pushed [1] will be added to it.

Code implementation as follows:

(Note: You can use deque or vector, it's gonna be similar in performance. If you use deque, do popping when discarding elements before the top, if you use vector, clear the vector and pushing everything after the new top as well as the top)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> results;
        if (nums.empty()) return results;
        
        /* initialize window */
        vector<int> candidates;
        initCandidates(nums, candidates, 0, k-1);
        
        for (int lhs=0, rhs=k-1; rhs < nums.size(); lhs++, rhs++) {
            results.push_back(nums[candidates[0]]);
            if (rhs+1 < nums.size()) {
                if (nums[rhs+1] > nums[candidates[0]]) {
                    candidates.clear();
                    candidates.push_back(rhs+1);
                    continue;
                } else {
                    candidates.push_back(nums[rhs+1]);
                    if (lhs == candidates[0]) {
                        initCandidates(nums, candidates, lhs+1, rhs+1);
                    }
                }
            }
        }
        
        return results;
    }
    
    
    inline void initCandidates(const vector<int>& nums, vector<int>& candidates, int lhs, int rhs) {
        int max_idx = lhs;
        for (int j=lhs+1; j<=rhs; j++) {
            if (nums[j] > nums[max_idx]) {
                max_idx = j;
            }
        }
        candidates.clear();
        for (int j=max_idx; j<=rhs; j++) candidates.push_back(j);
    }
};

Tuesday, July 12, 2016

[Algorithm] Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree

Problem Statement:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Solution 1: DFS based solution

Time complexity: O(n) for one query, O(mn) for m queries

The basic idea of this approach is to search for the two nodes in a DFS fashion. The two different nodes may have different path from root to itself and at some point these two paths will overlap. One native approach will be recording the two paths and compare them to find the last common node.

A better way is to check that on the fly while we are DFS traversing the tree. Instead of keeping the record of every node in the path leading to each one of the two, we actually just need to know whether anyone of the two nodes is in the path or not.

Using the tree example in the problem statement, suppose we are to find LCA of node 6 and 4. The path leading to 4 is 3->5->2->4 and the path leading to 6 is 3->5->6. When we are traversing in DFS fashion and at node 5, we can easily find out if 6 and 4 exists in its left and right sub-tree. If they exist in left and right sub-trees respectively like at node 5, node 5 is the LCA. If for example we are at node 2, we know that 4 exists in its right sub-tree but 6 doesn't in neither of left or right, we just return back the found node to its parent node. (Not sure if it's clear enough, I will try to come up with more illustration later)

Code Implementation:

/**
 * 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) {
        return dfsHelper(root, p, q);
    }
    
    TreeNode* dfsHelper(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL || root == p || root == q) return root;
        
        TreeNode* left = dfsHelper(root->left, p, q);
        TreeNode* right = dfsHelper(root->right, p, q);
        
        if (left == NULL && right == NULL) {
            return NULL;
        } else if (left && right) {
            return root;
        }
        
        return left ? left : right;
    }
};

Solution 2: Levelization based solution

Time complexity: O(n + logn) for one query, O(n + mlogn) for m queries if tree is immutable, O(m(n + logn)) for m queries if tree is mutable.

Solution 1 is actually good enough in terms of runtime and simplicity. Actually there's another approach which was actually my first solution for this problem, however it's kind of lengthy than the solution 1, but I think it is actually also a very good one.

This approach is centered around tree levelization, namely we are going to levelize each node with a marking of level number starting from 0 at the root. One can easily do this by a BFS traversal. Besides keeping a level number we also keep the parent node for each of the node we visited (This may not be necessary, but for efficiency we better keep it).

Then the algorithm is very simple, the following describes how we find LCA:

1) First we find out the levels of each node and their parent node, keep them in a hash table.

2) Given the two nodes, we lookup their level in the hash table.

3a) If they are of same level, trace back the two node simultaneously until they merge at one parent

3b) If they are not at same level, trace back the node with larger node level until the level is the same and then do 3a) step

This algorithm runs slower than solution 1 in the testcases of LeetCode OJ because it performs worse if the tree is mutable.

If the tree is immutable each lookup is only in O(logn) order. And another upside of this approach is that the concept of levelization can be used in directed acyclic graph (DAG) to find the LCA. (This algorithm is indeed used in some of the industrial software as well)

Code implementation:

/**
 * 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 (root == NULL) return NULL;
        p_level = -1;
        q_level = -1;
        parent_info.clear();
        levelizeTree(root, p, q);
        
        if (q_level != -1 && p_level != -1) {
            if (q_level > p_level) {
                q = goLevelUp(q, (q_level - p_level));
            } else if (q_level < p_level) {
                p = goLevelUp(p, (p_level - q_level));
            }
            
            while (q != p) {
                q = parent_info[q];
                p = parent_info[p];
            }
            
            return q;
        } else {
            return NULL;
        }
    }
    
    inline void levelizeTree(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> currlvl;
        int level = 0;
        currlvl.push_back(root);
        parent_info[root] = NULL;
        
        while(!currlvl.empty()) {
            vector<TreeNode*> nextlvl;
            for (int i=0; i<currlvl.size(); i++) {
                TreeNode* node = currlvl[i];
                
                if (node->left) {
                    parent_info[node->left] = node;
                    nextlvl.push_back(node->left);
                }
                
                if (node->right) {
                    parent_info[node->right] = node;
                    nextlvl.push_back(node->right);
                }
                
                if (p == node) p_level = level;
                if (q == node) q_level = level;
            }
            
            currlvl = nextlvl;
            level++;
        }
    }
    
    inline TreeNode* goLevelUp(TreeNode* node, int level) {
        while (level > 0 && node != NULL) {
            node = parent_info[node];
            level--;
        }
        return node;
    }
    
    int p_level;
    int q_level;
    std::unordered_map<TreeNode*, TreeNode*> parent_info;
};

Monday, July 11, 2016

[Algorithm] Number of Digit One

Number of Digit One

Problem Statement:

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Solution : Count by digits.

This kind of question takes more of some math rather than brutal force. It's generally a good practice to think about how can we calculate the occurrence of digit 1's at each position. To solve this let's examine some properties at each digit position.

If we are going to examine each digit of a number we need to break them into three segments: (high) curr (low), where high and low can be any arbitrary non-negative number, for example if we have number 13231 and we are looking at the 3rd bit from right to left, then high = 13, curr = 2, low = 31. We are also going to introduce base which is which is of 10's power. The base for this case is 100 which equals 10 ^ (i - 1) if we are looking at (i)th digit.

We are going to describe the three segment with high, curr, low and base for now on.

Let's first consider simple cases, let's say 200, and we are looking at 2nd digit. The possible number 1 occurring at that position is:

We could have 20 occurrences for that. And the formula for that is (high * base). This is the most basic case where the given number happen to be N * base. So how about this case, suppose we have number 1131 and we are still interested in the 2nd digit. Now the possible occurrence of 1's are:

The total number of 1's equals (12 * base) which is (high + 1) * base. How about the number being 1111 will it still hold? The possible occurrences now become:

This occurrence of 1's equals (10 * base) + 2 which is (high * base + low + 1). How about the number being 1101, the possible occurrences now become:

0010
0011
...
0110
...
0119
0210
...
1010
...
1019

The occurrence of 1's now becomes (10 * base) which is (high * base) and this is exactly the first simple case we discuss.

We are further prove that if we divide a number by (high) curr (low) we can calculate the possible occurrence of 1 at curr's digit postion with the following equations:

occurrence = high * base, where curr == 0
             high * base + low + 1, where curr == 1
             (high + 1) * base, where curr > 1

So we can have the following implementation:

class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) return 0;
        
        int base = 1;
        int high = n;
        int low = 0;
        long long count = 0;
        
        while (high) {
            int curr = high % 10;
            high = high / 10;
            
            printf("%d\t%d\t%d\t%d\n", high, curr, low, base);
            
            if (curr == 0) {
                count += high * base;
            } else if (curr == 1) {
                count += (low+1) + high * base;
            } else {
                count += (high+1) * base;
            }
            
            low += curr * base;
            base *= 10;
        }
        
        return count;
    }
};

Friday, July 8, 2016

[Algorithm] Subsets

Subsets

Problem statement

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

Solution 1: DFS

We can DFS the given array and assemble the subsets. At each DFS depth, can pick any number. This solution is quite straight forward.

Code Implementation:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        dfs(result, nums, 0, path);
        return result;
    }
    
    void dfs(vector<vector<int>>& result, const vector<int>& nums, int pos, vector<int>& path) {
        result.push_back(path);
        
        for (int i=pos; i<nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(result, nums, i+1, path);
            path.pop_back();
        }
    }
};

Solution 2: Bit manipulation.

Let's first consider this question, given N numbers how many different subsets it can possible make up, the answer is 2^N. So the if we have 32 numbers given the result won't even hold in the std::vector.

Why we are thinking about this? Now let's look at this, suppose 3 numbers are given [x, y, z], so what is the possible subsets:

[]      -> [O, O, O] -> 000
[z]     -> [O, O, z] -> 001
[y]     -> [O, y, O] -> 010
[x]     -> [x, O, O] -> 100
[x,y,z] -> [x, y, z] -> 111
[x,y]   -> [x, y, O] -> 110
[y,z]   -> [O, y, z] -> 011
[x,z]   -> [x, O, z] -> 101

This means we can represent each subset as binary numbers, where bit 0 means skipping this number at this bit and bit 1 means number shows up at this bit.

So we just need to iterate from 0 -> 2^N-1 and set the numbers based on the binary representation of the current index.

(I used bitmap to implementation this simply because bitmap can allow me access bit with operator[]. You can certainly use int or long long)

Code implementation:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        assert(nums.size() <= 32);
        vector<vector<int> > result;
        
        int n = nums.size();
        long long m = 1 << nums.size();
        int i = 0;
        
        while (i < m) {
            std::bitset<32> mask(i);
            vector<int> path;
            result.push_back(path);
            for (int j=0; j<n; j++) {
                if (mask[j]) result.back().push_back(nums[j]);
            }
            i++;
        }
        
        return result;
    }
};