LIKE CODING: July 2015

Monday, July 27, 2015

LeetCode [241] Different Ways to Add Parentheses

=================

Ref
[1] https://leetcode.com/problems/different-ways-to-add-parentheses/
OJ

Wednesday, July 22, 2015

LeetCode [240] Search a 2D Matrix II

240. Search a 2D Matrix II

Medium

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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if(m==0) return 0;
        int n = matrix[0].size();
        if(n==0) return 0;
        int i = 0, j = n-1;
        while(i<m && j>=0){
            if(target==matrix[i][j]) return true;
            if(target<matrix[i][j]) j--;
            else i++;
        }
        return false;
    }
};

Friday, July 17, 2015

LeetCode [239] Sliding Window Maximum

239. Sliding Window Maximum

Hard

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. Return the max sliding window.

Follow up:
Could you solve it in linear time?

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

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

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        deque<int> dq;//index. the corresponding numbers are decreasing from front to back
        int n = nums.size();
        for(int i=0; i<n; ++i)
        {
            while(!dq.empty() && dq.front()<i-k+1) dq.pop_front();
            while(!dq.empty() && nums[dq.back()]<=nums[i]) dq.pop_back();
            dq.push_back(i);
            if(i>=k-1)
                ret.push_back(nums[dq.front()]);
        }
        return ret;
    }
};

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        int n = nums.length;
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=0; i<n; ++i){
            if(!dq.isEmpty() && dq.getFirst()<i+1-k) dq.removeFirst();
            while(!dq.isEmpty() && nums[dq.peekLast()]<=nums[i]){
                dq.pollLast();
            }
            dq.addLast(i);
            if(i>=k-1) list.add(nums[dq.peekFirst()]);
        }
        return list.stream().mapToInt(i->i).toArray();
    }
}

Wednesday, July 15, 2015

LeetCode [238] Product of Array Except Self

238. Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int prod = 1, n = nums.size(), tmp = 1;
        vector<int> output(n,1);
        for(int i=1; i<n; ++i)
        {
            output[i] = tmp * nums[i-1];
            tmp = output[i];
        }
        
        tmp = 1;
        for(int i=n-2; i>=0; --i)
        {
            output[i] *= (tmp*nums[i+1]);
            tmp *= nums[i+1];
        }
        
        return output;
    }
};

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] output = new int[n];
        
        for(int i=0; i<n; ++i){
            if(i==0) output[i] = 1;
            else output[i] = output[i-1]*nums[i-1];
        }
        
        int p = nums[n-1];
        for(int i=n-2; i>=0; --i){
            if(i==0) output[i] = p;
            else output[i] = output[i]*p;
            p *= nums[i];
        }
        
        return output;
    }
}

LeetCode [237] Delete Node in a Linked List

===============
Ref
[1] https://leetcode.com/problems/delete-node-in-a-linked-list/
OJ

Sunday, July 12, 2015

LeetCode [236] Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

Medium

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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the tree.

/**
 * 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) return root;
        if(root==p || root==q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;
        if(left) return left;
        return right;
    }
};

Saturday, July 11, 2015

LeetCode [57] Insert Interval

57. Insert Interval

Hard

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

========

* use upper_bound to find the the range of merged interval

* the sort in the last step can be optimized by delicate insertions.

========

class Solution
{
  public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        vector<vector<int>> ret;
        int lb, ub;

        //find lower bound of merged new interval
        // |--prev(lv)--|     |--lv--|
        //          |--newIntv--|
        //lv is the first interval pass newInterval[0]. 
        //INT_MAX makes upper_bound return a vector with strickly greater first value
        auto lv = upper_bound(intervals.begin(), intervals.end(), vector<int>{newInterval[0], INT_MAX});
        if (lv == intervals.begin())
        {
            lb = newInterval[0];
        }
        else
        {
            lv = prev(lv);
            if ((*lv)[1] >= newInterval[0])
                lb = (*lv)[0];
            else
                lb = newInterval[0];
        }

        //find upper bound of the merged interval
        // |--prev(uv)--|             |--uv--|
        //          |--newIntv--|
        //lv is the first interval pass newInterval[1]. 
        auto uv = upper_bound(intervals.begin(), intervals.end(), vector<int>{newInterval[1], INT_MAX});
        if (uv == intervals.begin())
        {
            ub = newInterval[1];
        }
        else
        {
            uv = prev(uv);
            ub = max(newInterval[1], (*uv)[1]);
        }

        for(auto i:intervals)
        {
            if(i[1]<lb || i[1]>ub) ret.push_back(i);
        }
        ret.push_back(vector<int>{lb, ub});
        sort(ret.begin(), ret.end());

        return ret;
    }
};

======== legend ========

//C++: method1 596ms
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool compare(const Interval &a, const Interval &b){
  return a.start<b.start;
}
  
class Solution {
public:
    vector<interval> merge(vector<interval>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        vector<interval> res;
        int n = intervals.size();
        int i = 0;
        while(i<n){
            int j = i+1;
            while(j<n && intervals[i].end>=intervals[j].start){
                intervals[i].end = max(intervals[i].end, intervals[j].end);
                j++;
            }
            res.push_back(intervals[i]);
            i = j;
        }
        return res;
    }
    vector<interval> insert(vector<interval>& intervals, Interval newInterval) {
        intervals.push_back(newInterval);
        return merge(intervals);
    }
};

/**
 * 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:
    vector<interval> insert(vector<interval>& intervals, Interval newInterval) {
        vector<interval> res;
        int n = intervals.size();
        int i=0;

        while(i<n && intervals[i].end<newInterval.start){
            res.push_back(intervals[i++]);
        }

        if(i==n || newInterval.end<intervals[i].start){
            res.push_back(newInterval);
        }else{
            int start = i++;
            while(i<n && newInterval.end>=intervals[i].start) i++;
            int end = i-1;

            newInterval.start = min(newInterval.start, intervals[start].start);
            newInterval.end = max(newInterval.end, intervals[end].end);
            res.push_back(newInterval);
        }

        while(i<n) res.push_back(intervals[i++]);
        return res;
    }
};

/**
 * 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:
    vector<interval> insert(vector<interval> &intervals, Interval newInterval) {
        vector<interval> res;
        int n = intervals.size();
        if(n==0){res.push_back(newInterval); return res;}

        int i=0;
        vector<interval>::iterator it=intervals.begin();
        //|---0--| ... |---i--|
        //                       |----newInt------|
        while(i<n && intervals[i].end<newInterval.start){
            res.push_back(intervals[i++]);
        }
        
        //newIntervals is left alone
        if(i==n){
            res.push_back(newInterval); 
            return res;
        }
        
        //                          |----i-----|
        //|-----newInt-------|
        if(newInterval.end<intervals[i].start){
            res.push_back(newInterval);
            res.insert(res.end(), it+i, it+n);
            return res;
        }

        //          |----i-----|       |----i-----|
        //|-----newInt---|        or        |-----newInt-------| 
        //a                    b       a                       b
        int a = min(intervals[i].start, newInterval.start);
        int b = max(intervals[i].end, newInterval.end);            
        for(++i;i<n;++i){
            if(b<intervals[i].start){
                Interval intv(a, b);
                res.push_back(intv);
                res.insert(res.end(), it+i, it+n);
                break;
            }else{
                b = max(intervals[i].end, b);
            }
        }
        if(i==n){
            Interval intv(a, b);
            res.push_back(intv);                            
        }

        return res;
    }
};

//Java
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        int i = 0;
        int start = newInterval[0];
        int end = newInterval[1];
        List<int[]> list = new ArrayList<>();

        while(i<n && intervals[i][1]<start){
            list.add(intervals[i]);
            i++;
        }

        while(i<n && intervals[i][0]<=end){
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        list.add(new int[]{start, end});

        while(i<n){
            list.add(intervals[i]);
            i++;
        }
        
        int[][] res = new int[list.size()][2];
        for(int k=0; k<list.size(); ++k){
            res[k] = list.get(k);
        }
        return res;
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        List<int[]> list = new ArrayList<>();
        int l = lastEndBeforeNewStart(intervals, newInterval[0]);
        int r = firstStartBeforeNewEnd(intervals, newInterval[1]);
        int i = 0;
        while(i<=l){
            list.add(intervals[i++]);
        }
        int start = newInterval[0], end = newInterval[1];
        while(i<r){
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        list.add(new int[]{start, end});
        while(i<n){
            list.add(intervals[i++]);
        }
        return list.toArray(new int[0][]);
    }

    int lastEndBeforeNewStart(int[][] intervals, int newStart){
        int n = intervals.length;
        int l = 0, r = n-1;
        while(l<=r){
            int m = (l+r)/2;
            if(intervals[m][1]<newStart && (m==r || intervals[m+1][1]>=newStart)){
                return m;
            }else if(intervals[m][1]<newStart){
                l = m+1;
            }else{
                r = m-1;
            }
        }
        return -1;
    }

    int firstStartBeforeNewEnd(int[][] intervals, int newEnd){
        int n = intervals.length;
        int l = 0, r = n-1;
        while(l<=r){
            int m = (l+r)/2;
            if(intervals[m][0]>newEnd && (m==l||intervals[m-1][0]<=newEnd)){
                return m;
            }else if(intervals[m][0]>newEnd){
                r = m-1;
            }else{
                l = m+1;
            }
        }
        return n;
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0], end = newInterval[1];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int[] i : intervals){
            int u = i[0], v = i[1];
            map.put(u, v);
        }

        //[l, r], find max l s.t. l<=start
        Map.Entry<Integer, Integer> lEntry = map.floorEntry(start);
        if(lEntry!=null && lEntry.getValue()>=start){
            start = lEntry.getKey();
        }

        //[l, r] find min l s.t. l<=end
        Map.Entry<Integer, Integer> rEntry = map.floorEntry(end);
        if(rEntry!=null && rEntry.getValue()>=end){
            end = rEntry.getValue();
        }

        Map<Integer, Integer> submap = map.subMap(start, true, end, true);
        Set<Integer> set = new HashSet<>(submap.keySet());
        map.keySet().removeAll(set);
        map.put(start, end);

        int[][] ret = new int[map.size()][2];
        int i = 0;
        for(Map.Entry<Integer, Integer> en : map.entrySet()){
            ret[i][0] = en.getKey();
            ret[i][1] = en.getValue();
            i++;
        }
        
        return ret;
    }
}