Merge Two Sorted Interval Lists

• Lintcode : 839 / Leetcode :
• Level : Easy

Problem

Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.

Example
Example1

Input: list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)]
Output: [(1,4),(5,6)]
Explanation:
(1,2),(2,3),(3,4) --> (1,4)
(5,6) --> (5,6)
Example2

Input: list1 = [(1,2),(3,4)] and list2 = [(4,5),(6,7)]
Output: [(1,2),(3,5),(6,7)]
Explanation:
(1,2) --> (1,2)
(3,4),(4,5) --> (3,5)
(6,7) --> (6,7)
Notice
The intervals in the given list do not overlap.
The intervals in different lists may overlap.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(1)

Answer

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
public:
    vector<Interval> mergeTwoInterval(vector<Interval> &list1, vector<Interval> &list2) {
        vector<Interval> ans;
        int i = 0, j = 0;
        int len1 = list1.size(), len2 = list2.size();
        while (i < len1 && j < len2) {
            while (i < len1 && j < len2 && list1[i].start <= list2[j].start) {
                if (ans.size() > 0 && list1[i].start <= ans[ans.size() - 1].end) {
                    ans[ans.size() - 1].end = max(list1[i].end, ans[ans.size() - 1].end);
                }else {
                    ans.push_back(list1[i]);
                }
                i++;
            }
            while (i < len1 && j < len2 && list1[i].start > list2[j].start) {
                if (ans.size() > 0 && list2[j].start <= ans[ans.size() - 1].end) {
                    ans[ans.size() - 1].end = max(list2[j].end, ans[ans.size() - 1].end);
                }else {
                    ans.push_back(list2[j]);
                }
                j++;
            }
        }
        while (i < len1) {
            if (ans.size() > 0 && list1[i].start <= ans[ans.size() - 1].end) {
                ans[ans.size() - 1].end = max(list1[i].end, ans[ans.size() - 1].end);
            }else {
                ans.push_back(list1[i]);
            }
            i++;
        }
        while (j < len2) {
            if (ans.size() > 0 && list2[j].start <= ans[ans.size() - 1].end) {
                ans[ans.size() - 1].end = max(list2[j].end, ans[ans.size() - 1].end);
            }else {
                ans.push_back(list2[j]);
            }
            j++;
        }
        return ans;
    }
};

tags: 2pointers

​

Merge Sorted Array

• Lintcode : 64 / Leetcode : 88
• Level : Easy

Problem

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Example
Example 1:

Input：[1, 2, 3] 3  [4,5]  2
Output：[1,2,3,4,5]
Explanation:
After merge, A will be filled as [1, 2, 3, 4, 5]
Example 2:

Input：[1,2,5] 3 [3,4] 2
Output：[1,2,3,4,5]
Explanation:
After merge, A will be filled as [1, 2, 3, 4, 5]
Notice
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n + m)
space: O(1)

Answer

class Solution {
public:

    void mergeSortedArray(int A[], int m, int B[], int n) {
        int len = n + m - 1;
        int indA = m - 1, indB = n - 1;
        while (indA >= 0 && indB >= 0) {
            while (indA >= 0 && indB >= 0 && A[indA] >= B[indB]) {
                A[len--] = A[indA --];
            }
            while (indA >= 0 && indB >= 0 && A[indA] < B[indB]) {
                A[len--] = B[indB--];
            }
        }
        while (indB >= 0) {
            A[len--] = B[indB--];
        }
    }
};

tags: 2pointers

​

Is Subsequence

• Lintcode : 1263 / Leetcode : 392
• Level : Easy

Problem

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (length <= 100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example
Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:

Input: s = `"axc"`, t = `"ahbgdc"`
Output: false
Challenge
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Concept & Algorithm

1. 計算每一個字元出現的次數，儲存在unordered_map<char, int> count
2. 宣告int length 儲存長度 
3. 宣告bool hasOdd 紀錄是否有出現奇數的字元
3. iterate count，假設遍歷到的字元是偶數個 length 就直接加總
4. 若是奇數個就加上該數目減去1，且將hasOdd變成true
5. 最後假設hasOdd為false，直接return length / 若為true，return length + 1

Time Complexity & Space Complexity

time : O(n)
space: O(1)

Answer

class Solution {
public:
    /**
     * @param s: the given string s
     * @param t: the given string t
     * @return: check if s is subsequence of t
     */
    bool isSubsequence(string &s, string &t) {
        if (s.size() == 0) return true;
        if (t.size() == 0) return false;
        int indS = 0, indT = 0;
        int sizeS = s.size(), sizeT = t.size();
        while (indS < sizeS && indT < sizeT) {
            if (s[indS] == t[indT]) {
                indS++;
            }
            indT++;
        }
        if (indS < sizeS) return false;
        return true;
    }
};

tags: 2pointers

​

Subarray Product Less than K

• Lintcode : 1075 / Leetcode : 713
• Level : Medium

Problem

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example
Example 1:
    Input:  nums = [10, 5, 2, 6], k = 100
    Output:  8

    Explanation:
    The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
    Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.


Example 2:
    Input: nums = [5,10,2], k = 10
    Output:  2

    Explanation:
    Only [5] and [2].
Notice
0 < nums.length <= 50000.
0 < nums[i] < 1000.
0 <= k < 10^6.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(1)

Answer

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int> &nums, int k) {
        int n = nums.size();
        if (k <= 1 || n == 0) return 0;
        int count = 0, left = 0, product = 1;
        for (int i = 0;i < n; i++) {
            product = product * nums[i];
            while (product >= k)
                product /= nums[left++];
            count += i - left + 1;
        }
        return count;
    }
};

tags: 2pointers

​