Walls and Gates -- LeetCode 286

[Question]

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

[Analysis]
DFS starting from each gate,  each visited room store the minimum distance. It is also possible to use BFS.

[Solution]
void walls_and_gates (vector<vector<int>>& grid) {
    for (int i=0; i<grid.size(); i++)
        for(int j=0; j<grid[0].size(); j++)
            if (grid[i][j]==0) dfs(grid, i, j, 0);
    return;
}

void dfs (vector<vector<int>>& grid, int i, int j, int dist) {
    if (i>=grid.size() || i<0 || j<0 || j>=grid[0].size() || grid[i][j]<dist) return;
    grid[i][j] = dist;
    dfs(grid, i+1, j, dist+1);
    dfs(grid, i, j+1, dist+1);
    dfs(grid, i-1, j, dist+1);
    dfs(grid, i, j-1, dist+1);
}

Verify Preorder Serialization of a Binary Tree -- LeetCode 331

[Question]

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where #represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing nullpointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

[Analysis]
There are two approaches, using stack or using recursion.

1) When scan the string backward (from the end), push "#" into stack. When non-"#" appears, there must be at least two "#" in the stack. Then pop up two "#" and push one "#" into stack -- that means one valid sub-tree is found. Then repeat the process until entire string is done. The stack should contain only one "#".

2) Scan the string forward. For each sub-tree (starting from a non-"#'), the rest string should be able to be split into two valid sub-trees (left, right).

[Solution]
//-- backward and using a stack --
class Solution {
public:
    bool isValidSerialization(string preorder) {
        reverse(preorder.begin(), preorder.end() );
        stringstream ss(preorder);
       
        string s;
        stack<string> st;
        while (getline(ss, s, ',')) {
            if (s.compare("#") == 0) st.push("#");
            else {
                if (st.size()<2) return false;
                st.pop();  // pop up 2 "#" and push 1 "#"
            }
        }
        return st.size()==1 && st.top().compare("#")==0;
    }
};

//-- recursion --
class Solution {
    bool validate( string & str ) {
        if (str.empty()) return false;
     
        int end = str.find(',');
        if (end==string::npos) return false;
     
        string s = str.substr(0, end);
        str = str.substr(end+1);
     
        if (s.compare("#") == 0) return true;
        if (!validate(str)) return false;
        if (!validate(str)) return false;
        return true;
    }
 
public:
    bool isValidSerialization(string preorder) {
        string data = preorder +",";
        return validate( data ) && data.empty();
    }
};

Next Permutation -- LeetCode 39

[Question]

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Subscribe to see which companies asked this question.

[Thoughts]
In C++ STL lib, there is a function "next_permutation()" which exactly matches the need.

To do it manually, think of the (lexicographically) largest permutation -- that must be a decreasing sequence. For any other permutations, we can come up with the following steps to get the next one:
1) Find the increasing sequence from right to left, use i to denote the position of first decreasing digit.
2) Find the fist number, from right to left,  that is larger than N[i].
3) Swap N[i] and N[j].
4) Reverse the sub-string from N[i+1] to the end.

Additional note: the "Next Greater Number III" -- LeetCode 556 is an alternative form of the same problem.

[Solution]
//
//-- Using STL --
//
void nextPermutation(vector<int>& nums) {
      next_permutation(nums.begin(), nums.end());

}

//
//-- Manually --
//
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.size()<2) return;
     
        int i= nums.size()-2;
        while(i>=0 && nums[i]>=nums[i+1]) i--;
        if (i>=0) {
            int j= nums.size()-1;
            while(i<j && nums[i]>=nums[j]) j--;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin()+i+1, nums.end());
    }
};

//
//-- Using STL again --
//
void nextPermutation(vector<int>& nums) {
    auto i = is_sorted_until(nums.rbegin(), nums.rend());
    if (i != nums.rend())
        swap(*i, *upper_bound(nums.rbegin(), i, *i));
    reverse(nums.rbegin(), i);
}

Split Array Largest Sum -- LeetCode 419

[Question]

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

[Analysis]
The largest sum S of each sub-array after a split, is within the range of [max element of the array, sum of the array]. Considering each possible S, if S is too large, the array could be split only by a number less than m; if S is too small, the array will be split by a number larger than m.  So, using binary search, the minimal S will be found.

[Solution]
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int lo=0, hi=0;
        for (auto& n: nums) {
            hi +=n;
            lo = max(lo, n);
        }
        
        auto cut_by=[&](int upper) {
            int cnt = 0, sum=0;
            for (int i=0; i< nums.size(); i++) {
                if (sum==0) cnt++;
                sum += nums[i];
                if (sum>upper)  i--, sum=0;
            }
            return cnt<=m;
        };
        
        while (lo<hi) {
            int mid = lo+(hi-lo)/2;
            if (cut_by(mid)) 
                hi = mid;
            else 
                lo = mid+1;
        }
        return lo;
    }
};

Number of Connected Components in an Undirected Graph -- LeetCode 323

[Question]

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

[Analysis]
Classic Union-find problem.

[Solution]
class UnionFind {
    vector<int> u;

public:
    UnionFind(int n) {
        u =vector<int>(n,0);
        for (int i=0; i<n; i++)
            u[i] = i;
    }

    int find(int i) {
        if (u[i]==i) return i;
        u[i] = find(u[i]);
        return u[i];
    }

    void unions(int i, int j) {
        u[find(i)] = find(j);
    }
};

int countComponents(vector<pair<int,int>>& edges, int n) {
    UnionFind uf(n);
   
    for (auto& e:edges)
        uf.unions(e.first, e.second);
   
    unordered_set<int> res;
    for(int i=0; i<n; i++)
        res.insert(uf.find(i));

    return res.size();
}

Combination Sum II, III -- LeetCode 40, 216

[Questions]
Combination Sum II:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Combination Sum III:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

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

[Thoughts]
Similar to "Combination Sum", those are just variations. The same code skeleton of backtracking on a vector can be reused. The variations are marked in the following code.

[Solution]
//-- Combination Sum II --
class Solution {
    void backtrack(vector<int>& cand, int target, int start, vector<int>& tmplist, vector<vector<int>>& res) {
        if (target<0) return;
        if (target==0) {
            res.push_back(tmplist); return;
        }

        for (int i=start; i<cand.size();i++) {

            tmplist.push_back(cand[i]);
            backtrack(cand, target-cand[i], i+1, tmplist, res);
            tmplist.pop_back();
            
            while(cand[i+1]==cand[i]) i++; //skip duplicates
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> sublist;
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, sublist, res);
        return res;
    }
};

//-- Combination Sum III --
class Solution {
    void backtrack(int len, int target, int start, vector<int>&tmplist, vector<vector<int>>& res) {
        if (target<0) return;
        if (target==0 && tmplist.size()==len) {
            res.push_back(tmplist); return;
        }
        if (tmplist.size()>len) return;  // length limit
        
        for (int i=start; i<10; i++) {
            tmplist.push_back(i);
            backtrack(len, target-i, i+1, tmplist, res);
            tmplist.pop_back();
        } 
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> tmplist;
        backtrack(k, n, 1, tmplist, res);
        return res;
    }

};

Combination Sum -- LeetCode 39

[Question]
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] 

[Thoughts]
Since the candidate array has no duplicates, a combination can be picked up by a starting position, a reduced target and a current candidate list. Therefore, the kind of combination problems can be solved by a backtracking function, which tracks the reduced target, start position, candidate sub-list, and usually a bag of current results.

[Solution]
class Solution {
    void co_sum (vector<int>& cand, int target, int start, vector<int>& sub_res, vector<vector<int>>& res){
        if (target==0) res.push_back(sub_res);

        for (int i=start; i<cand.size(); i++ ) {
         
            for (int j=1; cand[i]*j<=target; j++) {
                for (int k=0; k<j; k++) sub_res.push_back(cand[i]);
                co_sum(cand, target-cand[i]*j, i+1, sub_res, res);
                for (int k=0; k<j; k++) sub_res.pop_back();
            }

        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& cand, int target) {
        sort(cand.begin(), cand.end(), greater<int>());
        vector<vector<int>> res;
        vector<int> sub_res;
        co_sum(cand, target, 0, sub_res, res);
        return res;
    }
};

Binary Tree Postorder/Inorder/Preoder Traversal (non-recursive) -- LeetCode 145, 94

[Question]

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

[Analysis]
The state of recursive calls can be simulated by stacks. The key is to find the branch (left or right) where the stack pop() happened. The preorder/inorder,/postorder functions are placed in differnt branch (in, left, right) respectively.

[Solution]
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        stack<TreeNode*> st;
        TreeNode* p=root;
        st.push(p);
        
        vector<int> res;
        while(!st.empty()) {
            if (st.top()==p && !p->left && !p->right) { 
                //-- leave node is reached and is at the top of stack.
                res.push_back(st.top()->val);     //--shared by all orders.
                st.pop();
                continue;
            }
            if (st.top()==p) {
                //res.push_back(st.top()->val);    // -- pre-order output here.
                p=p->left;
                if (p) st.push(p);
            }
            else if (st.top()->left==p) {
                res.push_back(st.top()->val);     // -- in-order output here
                p=st.top()->right;
                if (p) st.push(p);
            }
            else if (st.top()->right==p) {
                //res.push_back(st.top()->val);   //-- post-order output here
                p=st.top();
                st.pop();
            }
        }

        return res;
    }
};

Queue Reconstruction by Height -- LeetCode

[Question]

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

[Analysis]
Be Greedy. Person (h,k) at position 0 should have k=0. So group all (h,0), the one with smallest h' is at position 0. Then look at all other persons (h,k) whose h is greater or equal to h', decrease their k by 1 (because h' contribute 1 to their k values). Repeat the previous steps and find person at position 1, .., n. The time complexity is O(N^2).

Another way to reconstruct the queue is by sorting. Suppose a person (h',k'), all persons (h,k) with greater or equal height have been in a sorted queue Q, the k' is the right position to insert (h',k') into the Q and create a Q' while maintaining all existing (h,k). Repeat the same process on Q' and remaining persons. The time complexity is O(N^2).

[Solution]
//-- using sorting --
class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        auto comp=[](pair<int,int> &a, pair<int,int> &b)
            { return a.first<b.first || a.first==b.first && a.second > b.second;};
        sort (people.begin(), people.end(), comp);
        vector<int,int> res;
        for (int i=people.size(); i>=0; i++)
            res.(res.begin()+people[i].second, people[i]);
    }
};

//--greedy --
class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        vector<pair<int, int>> rslt;
     
        vector<pair<int, int>> bak (people);
        auto comp= [](pair<int, int> a, pair<int,int> b)
            { return a.second < b.second || a.second ==b.second && a.first<b.first;};
         
        while (rslt.size()!= people.size() ) {
            auto it = min_element(bak.begin(), bak.end(), comp);
            rslt.push_back(people[it-bak.begin()] );
            it->second = INT_MAX;
            for (auto &p: bak) {
                if (p.second!=INT_MAX && p.first<=it->first) {
                    p.second --;
                }
            }
        }
        return rslt;
    }
};

Maximum Square -- LeetCode 221

[Question]

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

[Analysis]
This is similar with the Maximum Rectangle problem. While it can be done by the same approach, there is a  Dynamic Programming solution to solve this.

Define S[i,j] = the length of largest square positioned at Matrix[i,j], then
          S[i,0] = 1 if Matrix[i,0]= '1';
          S[0,j] = 1 if Matrix[0,j]= '1';
          S[i,j] = min ( S[i-1,j-1], S[i-1,j], S[i,j-1] ) + 1 if Matrix[i,j]='1', i>0, j>0;

Time complexity and space complexity are O(M x N).

[Solution]
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
       
        vector<vector<int>> s(matrix.size(), vector<int>(matrix[0].size(),0) );
        int max_len=0;
       
        for (int i=0; i< matrix.size(); i++) {
            s[i][0] = (matrix[i][0]=='1')?1:0;
            max_len |= s[i][0];
        }
           
        for (int i=0; i< matrix[0].size(); i++) {
            s[0][i] = (matrix[0][i]=='1')?1:0;
            max_len |= s[0][i];
        }
       
        for (int i=1; i< matrix.size(); i++)
            for (int j=1; j<matrix[0].size(); j++) {
                if (matrix[i][j] =='0') continue;
                s[i][j] = min(min(s[i-1][j], s[i][j-1]),s[i-1][j-1])+1;
                max_len = max(max_len, s[i][j]);
            }
               
        return max_len*max_len;
    }

};

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

};