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

};