Insert Interval -- Leetcode

[Question]
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
[Analysis]
Because all intervals are sorted and non-overlapping, for intervals A and B, if A.start < B.start, A.end < B.end.  Need to find the first and the last interval in the sequence that overlaps with the given interval.

One scan on the array of intervals can complete the replacement. Time complexity is O(N). There is no need for extra storage (shown in the 2nd code sample below). The 3rd code sample shows how binary search can help to improve time complexity of locating the overlapping range of intervals.

[Solution]
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
//---  (1) This solution use O(N) extra storage.
//---        The input intervals vector is not changed
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        if (intervals.empty())  return vector<Interval>(1, newInterval);
     
        vector<Interval> ret;
        int i,j;
        for (i=0; i<intervals.size(); i++) {
            if (intervals[i].end < newInterval.start) {
                ret.push_back(intervals[i]);
            }
            else break;
        }
     
        for (j=intervals.size()-1; j>=0; j--) {
            if (intervals[j].start <= newInterval.end)
                break;
        }          
     
        if (i<=j)  {
            newInterval.start = min (newInterval.start, intervals[i].start);
            newInterval.end = max (newInterval.end, intervals[j].end);
        }
        ret.push_back(newInterval);
     
        for (int k=j+1; k< intervals.size(); k++) {
            ret.push_back( intervals[k] );
        }
     
        return ret;
    }
};

//--- (2) This solution is in-place.
//---       The input "intervals" are modified accordingly.
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        if (intervals.empty()) {
            intervals.push_back(newInterval);
            return intervals;
        }
     
        if (intervals[0].start > newInterval.end) {
            intervals.insert (intervals.begin(), newInterval);
            return intervals;
        }
     
        if (intervals.back().end < newInterval.start) {
            intervals.push_back(newInterval);
            return intervals;
        }
     
        int iStart = 0;
        for (int i=0; i<intervals.size(); i++) {
            if (newInterval.start <= intervals[i].end) {
                iStart = i;
                break;
            }
        }

        int iEnd = 0;
        for (int i=intervals.size()-1; i>=0; i--) {
            if (newInterval.end >= intervals[i].start) {
                iEnd = i;
                break;
            }
        }
             
        newInterval.start = min(newInterval.start, intervals[iStart].start);
        newInterval.end   = max(newInterval.end, intervals[iEnd].end);
     
        intervals.erase(intervals.begin()+iStart, intervals.begin()+iEnd+1);
        intervals.insert(intervals.begin()+iStart, newInterval);
     
        return intervals;
    }
};

//--- (3) Use binary search: lower_bound() in STL.
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        if (intervals.empty()) {
            intervals.push_back(newInterval);
            return intervals;
        }
     
        if (intervals[0].start > newInterval.end) {
            intervals.insert (intervals.begin(), newInterval);
            return intervals;
        }
     
        if (intervals.back().end < newInterval.start) {
            intervals.push_back(newInterval);
            return intervals;
        }

        int iStart = lower_bound(intervals.begin(), intervals.end(), newInterval,
                [](const Interval& a, const Interval& t) { return t.start > a.end; } ) - intervals.begin();
     
        int iEnd = lower_bound(intervals.begin(), intervals.end(), newInterval,
                [](const Interval& a, const Interval& t) { return t.end >= a.start; } ) - intervals.begin()-1;
             
        newInterval.start = min(newInterval.start, intervals[iStart].start);
        newInterval.end   = max(newInterval.end, intervals[iEnd].end);
     
        intervals.erase(intervals.begin()+iStart, intervals.begin()+iEnd+1);
        intervals.insert(intervals.begin()+iStart, newInterval);
     
        return intervals;
    }
};

Merge Intervals -- Leetcode

[Question]
Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

[Analysis]

If all intervals are sorted by their start points, the overlapping between two consecutive intervals A and B is simple: A.end > B.start. If B.start> A.end, B and the following intervals have no overlapping with A. Therefore, sort the intervals first, then scan the sorted interval list and merge them one by one when possible. The time complexity is O(N x log N + N).

Without sorting, the overlapping cases among intervals are complicated. It can not be done by one pass.

[Solution]
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool intersected( const Interval& a, const Interval& b) {
        return !(a.start>b.end || b.start>a.end);
    }
 
    vector<Interval> merge(vector<Interval> &intervals) {
        if (intervals.empty()) return intervals;
       
        sort(intervals.begin(), intervals.end(),
            [](Interval a, Interval b) { return a.start < b.start; }
        );
       
        int size = intervals.size();
        Interval temp (intervals[0].start, intervals[0].end);
        for (int i=1; i<size; i++) {
            if ( intersected(intervals[i], temp) ){
                temp.start = min(intervals[i].start, temp.start);
                temp.end = max(intervals[i].end, temp.end);
            }
            else {
                intervals.push_back(temp);
                temp = intervals[i];
            }
        }
        intervals.push_back(temp);
        intervals.erase(intervals.begin(), intervals.begin()+size);
        return intervals;
    }
};

Total of Subarray

[Question]
Given an array A of numbers and a target number N, check if there is a contiguous sequence in array which sums to the target N.

[Analysis]
To match a target number, the best way is to use hash-table. The sum of contiguous sub-array Sum[i,j] = Sum[0,j] - Sum[0, i-1]. Assume all Sum[0, i] , N needs to be the difference of  Sum[0, k] and Sum[0, l]. Time complexity is O(N).

[Solution]
bool maxOfSubArray ( vector<int> vec, int target ) {
    vector<int> sum (vec.size(), vec[0]);
    for (int i=1; i<vec.size(); i++)
         sum[i] =sum[i-1]+vec[i];
 
    unordered_set<int> sum_set ( sum.begin(), sum.end() );
    for (auto s: sum_set) {
        if ( sum_set.find(s+target) != sum_set.end() )
             return true;
    }
    return false;
}

Maximum Subarray -- Leetcode 53

[Question]:
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

[Analysis]:
Assume S[i] is the maximum sub-array which ends at A[i]. Then S[i] = max (S[i-1]+A[i], A[i]), i>0; S[0] = A[0]. The maximum of all S[i] is the result.  Time complexity is O(N).

Another solution is made by simple math.
[Solution]:
//-- DP--
class Solution {
public:
    int maxSubArray(int A[], int n) {
        assert(n>0);
     
        vector<int> sum(n, A[0]);
        for (int i=1; i<n; i++) {
            sum[i] = max (sum[i-1]+A[i], A[i]);
        }
        return *max_element( sum.begin(), sum.end() );
    }
};

//-- Running sum --

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int ans=A[0],i,j,sum=0;
        for(i=0;i<n;i++){
            sum+=A[i];
            ans=max(sum,ans);
            sum=max(sum,0);
        }
        return ans;
    }
};

Word Ladder II -- Leetcode

[Question]

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

• Only one letter can be changed at a time
• Each intermediate word must exist in the dictionary

For example,

Given:
    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]

Return:
    [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]

Note:
All words have the same length.
All words contain only lowercase alphabetic characters.

[Analysis]
The problem is about to find all possible paths between two nodes in a graph. To get the paths, it is normal to use DFS (Depth First Search). The drawback to apply DFS is, unlike tree, there exist many circles in a graph. Most depth first routes will not reach the target and will be extremely time-consuming.

Meanwhile, BFS (Breadth First Search) will help to reach the target quickly (i.e. find the shortest path from start to end), like what we have seen in Word Ladder question. However, BFS visits nodes layer by layer and does not maintain the paths of nodes from start to end.

The idea is to combine the benefits of BFS and DFS together:

1. Apply BFS to reach target starting from "start" layer by layer. So that we can know by the number of steps in the shortest path from start to end. Any nodes outside the visited nodes during this procedure need no further consideration.
2. During the above BFS procedure, we construct a (directional) sub-graph where each node A in layer i+1 points to the connected nodes (where A comes from) in layer i. If A is the target ("end"), we know back-trace to the start using the path in this sub-graph. Any nodes outside this sub-graph are irrelevant to the shortest path from "start" to "end". 
3. Apply DFS starting from "end" using the sub-graph above. All shortest paths will be generated.

It is interesting to consider the data structure to use for the algorithm. For the BFS, queue is not a fit in this case because all connections between layer i and layer i+1 need to be collected. Queue-based BFS like in Word Ladder question actually will lose those information. It is recommended to use set in this case.

[Solution]

class Solution {
public:
    unordered_set<string> getChildren2(string s, unordered_set<string> &dict) {
        unordered_set<string> rslt;
        for (int i=0; i<s.size(); i++) {
            string tmp = s;
            for (char c='a'; c<='z'; c++) {
                tmp[i]=c;
                if (dict.find(tmp)!=dict.end())
                    rslt.insert(tmp);
            }
        }
        return rslt;
    }
 
    vector<vector<string>> pathsInGraph(string start, string end, unordered_map<string, unordered_set<string>> &graph, int depth) {
        vector<vector<string>> rslt;
        if (depth==0 || graph.find(end)==graph.end()) return rslt;
        if (depth==1) {
            rslt.push_back({start, end});
            return rslt;
        }
        for (auto w: graph[end]) {
            vector<vector<string>> paths = pathsInGraph(start, w, graph, depth-1);
            for (auto& v: paths) {
                v.push_back(end);
                rslt.push_back(v);
            }
        }
        return rslt;
    }
 
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        unordered_set<string> unvisited = dict;
        unvisited.erase( start );
        unvisited.insert(end);
     
        unordered_map<string, unordered_set<string>> graph;
     
        unordered_set<string> que1, que2;
        que1.insert(start);
     
        int len = 0;
        while (!unvisited.empty() && !que1.empty()) {
            for (auto w: que1) {
                unordered_set<string> children = getChildren2(w, unvisited);
                for (auto chld : children) {
                    graph[chld].insert( w ); //reverse route
                    que2.insert( chld );
                }
            }
            len ++;
            if (que2.find(end) != que2.end())    //found
                break;
         
            que1 = que2;          
            for (auto w: que2) unvisited.erase( w );
            que2.clear();  // ... must clear que2; waste hours because of missing this line.
        }
     
        if (que1.empty()) return vector<vector<string>>();
        return pathsInGraph(start, end, graph, len);
    }
};

Word Ladder -- Leetcode

[Question]

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time 
2. Each intermediate word must exist in the dictionary 

For example,

Given:

• start = "hit"
• end = "cog"
• dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence. 
• All words have the same length. 
• All words contain only lowercase alphabetic characters.

[Analysis]

The dictionary of words composed a word graph where two nodes of words are (bi-directionally, undirected) connected when there is only one character difference between two words: for example, "hot" and "dot". 

A BFS (Breadth First Search) will give the shortest path between two nodes in a graph. Please note, there is no need to construct the graph physically -- that will be time-consuming. Using Set/unordered_set can give the siblings of a node, which is sufficient to get the result.

Another catch is, how to find the sibling words of a given word. The straightforward solution is to compare the given word with every word unvisited in dictionary. The comparison will be costly when the dictionary is large (O(N), N is the number of words in dictionary). Due to the assumptions in the question, the number of possible sibling words is 25*L, where L is the length of the word -- see "getUnvisitedSiblings()" below.

[Solution]
//-- C++ --
class Solution {
    unordered_set<string> getUnvisitedSiblings( string& str, unordered_set<string>& unvisited ) {
        unordered_set<string> rslt;
        for (int i=0; i<str.size(); i++) {
            string tmp = str;
            for (char c='a'; c<='z'; c++) {
                tmp[i] = c;
                if (unvisited.count(tmp))
                    rslt.insert( tmp );
            }
        }
        return rslt;
    } 

public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
        unordered_set<string> unvisited(wordList.begin(), wordList.end());
        unvisited.erase(beginWord); //make sure no redundant steps.
    
        q.push( beginWord );
        int len = q.size();    //size of current queue.
       
        int step = 1;
        while (!q.empty() && q.front()!=endWord) {
            string cur = q.front();
            q.pop(), len--;
           
            unordered_set<string> siblings = getUnvisitedSiblings( cur, unvisited );
            for (auto s: siblings) {
                q.push(s);
                unvisited.erase(s);
            }
        
            if (len==0) { // new level of BFS is reached.
                step++;
                len = q.size();
            }
        }

        if (!q.empty() && q.front()==endWord) return step;
        return 0;       
    }
};

Search a value in a special 2D Sorted Matrix

[Question]
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

[Analysis]

Binary search will work on this question. The 2nd condition is a key to apply Binary Search on this 2D sorted matrix. One way is to treat the 2D array as 1D array and do a Binary Search. Another way is to do Binary Search on all first elements of each row; then do a binary search on the potential row. The time complexities of two approaches are the same: O(lgMN) == O(lgN+lgM).

[Solution]
class Solution {
public:
    bool searchVector( vector<int> &v, int target ) {
        if (v.size()==0) return false;
        if (v.size()==1) return (v[0]==target);
       
        int mid = v.size()/2;
        if (v[mid]==target) return true;
       
        vector<int> half;
        if (v[mid]<target) {
            half = vector<int>(v.begin()+mid, v.end());
        } else {
            half = vector<int>(v.begin(), v.begin()+mid);
        }
        return searchVector( half, target );
    }
   
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        if (matrix.size()==0) return false;
        if (matrix.size()==1) return searchVector( matrix[0], target);
       
        int mid = matrix.size()/2;
       
        if (matrix[mid][0]== target) return true;
       
        vector<vector<int>> half;
        if (matrix[mid][0]<target) {
            half = vector<vector<int>> (matrix.begin()+mid, matrix.end());
        } else {
            half = vector<vector<int>> (matrix.begin(), matrix.begin()+mid);
        }
        return searchMatrix( half, target );
    }
};

Find the Minimum in a Sorted but Rotated Array

[Question]

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element.
You may assume no duplicate exists in the array.

[Analysis]

Simple solution is to experiment linear search and the time complexity is O(N).

It is noticeable that the pivot at position i must meet the following condition: A[i-1]>A[i] and A[i]<A[i+1] (if rotation happened). For example, "0" in above array. So we can apply binary search in this case. Time complexity is O(lg N).

A follow-up question can be, find a given value in such array. The first step will be find the pivot. Then the second step is to apply binary search again for the given value. 

[Solution]

int findMin(vector<int> &num) {
    if (num.size()==0) return 0;
    if (num.size()==1 || num[0]<num.back()) return num[0];
    if (num.size()==2) return min (num[0], num[1]);

    int mid = num.size()/2;
    if (num[mid]<num[mid+1] && num[mid]<num[mid-1]) return num[mid];
 

    vector<int> split;
    if (num[mid]>num.back()) {
        split = vector<int> (num.begin()+mid, num.end());
    } else {
        split = vector<int> (num.begin(), num.begin()+mid);
    }
    

    return findMin(split);
}

Palindrome Partitioning - LeetCode 131

[Question]

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome. For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed.

[Analysis]

The minimum cut of the string S at position i is,
     MinimumCuts(i) = MinimumCuts[j-1]+1, while  S[j] ...S[i] is the longest palindrome sub-string ending at position i.  (j<i).

Use a table to calculate the palindrome sub-string at each position. C[i,j] is true when S[j,i]  is a palindrome. C[i,j] is true, when C[i-1, j+1] is true && S[i] == S[j].

Total time complex is O(N^2).

[Solution]

    int minCut(string s) {
        if (s.size()==0) return 0;
     
        int len = s.size();
     
        int dp[len+1];
        for (int i=0; i<len+1; i++)
            dp[i] = i;

        bool c[len+1][len+1];
        for (int i=0; i<=len; i++)
            for (int j=0; j<=len; j++)
            c[i][j] = false;
         
        c[0][0]=true;
        for (int i=1; i<len+1; i++)
            for (int j=i; j>0; j--) {
                if (s[i-1]==s[j-1] && (i-j<2 || c[i-1][j+1]==true)) {
                    c[i][j] = true;
                    dp[i] = min(dp[i], dp[j-1]+1);
                }
            }
     
        return dp[len]-1;
    }

Recover Two Swapped Nodes in BST

[Question]

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

[Analysis]
In-order traversal will reveal the swapped elements. If output the traversal result to an array, the space will be O(N). If using recursive calls, the space will be O(lg N). An in-place traversal will do it.

[Solution]
/////////////////
//Solution 1: Using in-place space
//
void inOrderTraversal(TreeNode* root) {
    TreeNode* pre = NULL;
    TreeNode* p = root;
    while(p! = NULL) {
            while (p->left!=NULL && p->left!=pre) {
                     TreeNode * q = p;
                     while (q->right!=NULL) q = q->right;
                     q->right = pre;
                     pre = p;
                     p = p->left;
            }
            cout<<p->val<<endl;
            pre = p;
            p = p->right;
            if (p->left == pre) {
                pre->right = NULL;
            }
    }

}


///////////////
// Solution 2: Recursive using a stack.
//
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

    void recoverTree(TreeNode *root) {

        if (!root) return;
        stack<TreeNode*> st;
        TreeNode* cur=NULL;
        TreeNode* p1=NULL, *p2=NULL;
     
        st.push(root);
     
        while (!st.empty()) {
            while (st.top()->left) {
                st.push(st.top()->left);
            }

            if (!st.empty() && cur && cur->val > st.top()->val) {
                if (!p1) { p1 = cur; p2 = st.top();}
                else p2 = st.top();
            }

            while (!st.empty()&&st.top()->right==NULL) {
                cur = st.top();
                st.pop();
                if (!st.empty() && cur && cur->val > st.top()->val) {
                    if (!p1) { p1 = cur; p2 = st.top();}
                    else p2 = st.top();
                }
            }
         
            if (!st.empty()) {
                cur = st.top();
                st.pop();
                st.push(cur->right);
            }
        }
        if (p1 && p2 ) swap( p1->val, p2->val);
    }