Median of two Sorted Arrays

• Lintcode : 65 / Leetcode : 4
• Level : Hard

Problem

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example
Example 1

Input:
A = [1,2,3,4,5,6]
B = [2,3,4,5]
Output: 3.5
Example 2

Input:
A = [1,2,3]
B = [4,5]
Output: 3
Challenge
The overall run time complexity should be O(log (m+n)).

Clarification
The definition of the median:

The median here is equivalent to the median in the mathematical definition.

The median is the middle of the sorted array.

If there are n numbers in the array and n is an odd number, the median is A[(n-1)/2]A[(n−1)/2].

If there are n numbers in the array and n is even, the median is (A[n / 2] + A[n / 2 + 1]) / 2.

For example, the median of the array A=[1,2,3] is 2, and the median of the array A=[1,19] is 10.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(log(A.size() + B.size())
space: O(1)

Answer

class Solution {
public:
    double findMedianSortedArrays(vector<int> &A, vector<int> &B) {
        int len = A.size() + B.size();
        if (len == 0) return 0;
        double ret = 0;
        if (len & 1) {
            ret = finKth(A, B, 0, 0, len / 2 + 1);
        }else {
            ret = (finKth(A, B, 0, 0, len / 2) + finKth(A, B, 0, 0, len / 2 + 1)) / 2.0;
        }
        return ret;
    }
    int finKth (vector<int> &A, vector<int> &B, int a, int b, int k) {
        if (a >= A.size()) return B[b + k - 1];
        if (b >= B.size()) return A[a + k - 1];
        if (k == 1) return min(A[a], B[b]);
        int keyA = a + k / 2 - 1 >= A.size() ? INT_MAX : A[a + k / 2 - 1];
        int keyB = b + k / 2 - 1 >= B.size() ? INT_MAX : B[b + k / 2 - 1];
        if (keyA < keyB) {
            return finKth(A, B, a + k / 2, b, k - k / 2);
        }else {
            return finKth(A, B, a, b + k / 2, k - k / 2);
        }
    }
};

tags: other

​

Subarray Sum Equals K

• Lintcode : 838
• Level : Easy

Problem

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example
Example1

Input: nums = [1,1,1] and k = 2
Output: 2
Explanation:
subarray [0,1] and [1,2]
Example2

Input: nums = [2,1,-1,1,2] and k = 3
Output: 4
Explanation:
subarray [0,1], [1,4], [0,3] and [3,4]

Concept & Algorithm

筆記

Time Complexity & Space Complexity

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

Answer

/*
// TLE
class Solution {
public:
    int subarraySumEqualsK(vector<int> &nums, int k) {
        if (nums.size() == 0) return 0;
        vector<int> prefix;
        int sum = 0;
        prefix.push_back(sum);
        for (auto i : nums) {
            sum += i;
            prefix.push_back(sum);
        }
        int count = 0;
        for (int i = 1; i < prefix.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (prefix[i] - prefix[j] == k) count++;
            }
        }
        return count;
    }
};
*/

class Solution {
public:
    int subarraySumEqualsK(vector<int> &nums, int k) {
        for (int i = 1; i < nums.size(); i++) {
            nums[i] += nums[i - 1];
        }
        map<int, int> map;
        int count = 0;
        map[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            count += map[nums[i] - k];
            map[nums[i]]++;
        }
        return count;
    }
};

tags: other

​

Sparse Matrix Multiplication

• Lintcode : 654
• Level : Medium

Problem

Given two Sparse Matrix A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example
Example1

Input: 
[[1,0,0],[-1,0,3]]
[[7,0,0],[0,0,0],[0,0,1]]
Output:
[[7,0,0],[-7,0,3]]
Explanation:
A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |
Example2

Input:
[[1,0],[0,1]]
[[0,1],[1,0]]
Output:
[[0,1],[1,0]]

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(max(r c))
space: O(rA cB)

Answer

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>> &A, vector<vector<int>> &B) {
        vector<pair<int, int>> locationA, locationB;
        // corner cases
        if (A.empty() || A.size() == 0 || A[0].size() == 0) return {};
        if (B.empty() || B.size() == 0 || B[0].size() == 0) return {};
        int rA = A.size(), cA = A[0].size();
        int rB = B.size(), cB = B[0].size();
        for (int i = 0; i < rA; i++) {
            for (int j = 0; j < cA; j++) {
                if (A[i][j]) locationA.push_back({i, j});
            }
        }
        for (int i = 0; i < rB; i++) {
            for (int j = 0; j < cB; j++) {
                if (B[i][j]) locationB.push_back({i, j});
            }
        }
        vector<vector<int>> ans(rA, vector<int>(cB));
        for (int i = 0; i < locationA.size(); i++) {
            pair<int, int> a = locationA[i];
            for (int j = 0; j < locationB.size(); j++) {
                pair<int, int> b = locationB[j];
                if (a.second == b.first) ans[a.first][b.second] += A[a.first][a.second] * B[b.first][b.second];
            }
        }
        return ans;
    }
};

tags: other

​

Subarray Sum

• Lintcode : 138 / Leetcode :
• Level : Easy

Problem

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Example
Example 1:

Input:  [-3, 1, 2, -3, 4]
Output: [0, 2] or [1, 3].
Explanation: return anyone that the sum is 0.
Example 2:

Input:  [-3, 1, -4, 2, -3, 4]
Output: [1,5]    
Notice
There is at least one subarray that it's sum equals to zero.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

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

Answer

class Solution {
public:
    vector<int> subarraySum(vector<int> &nums) {
        vector<int> prefix;
        int sum = 0;
        prefix.push_back(sum);
        for (auto i : nums) {
            sum += i;
            prefix.push_back(sum);
        }

        unordered_map<int, int> hash;
        for (int i = 0; i < prefix.size(); i++) {
            if (hash.find(prefix[i]) != hash.end()) 
                return {hash[prefix[i]], i - 1};
            hash[prefix[i]] = i;
        }
    }
};

tags: other

​

Group Anagrams

• Lintcode : 772 / Leetcode : 49
• Level : Medium

Problem

Given an array of strings, group anagrams together.

Example
Example 1:

Input:
["eat","tea","tan","ate","nat","bat"]
Output:
[["ate","eat","tea"],
 ["bat"],
 ["nat","tan"]]
Example 2:

Input:
["eat","nowhere"]
Output:
[["eat"],
 ["nowhere"]]
Notice
All inputs will be in lower-case.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

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

Answer

class Solution {
public:
    /**
     * @param strs: the given array of strings
     * @return: The anagrams which have been divided into groups
     */
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> hash;
        for (auto i : strs) {
            string s = i;
            sort(s.begin(), s.end());
            hash[s].push_back(i);
        }
        vector<vector<string>> ans;
        for (auto it = hash.begin(); it != hash.end(); it++) {
            ans.push_back(it -> second);
        }
        return ans;
    }
};

tags: other

​