# Array
###### tags: `Study_aboard`
## Two sums
1. One space hash table
```cpp
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
map <int, int> hashMap;
map <int, int>::iterator iter; // can find things in map
for (int i=0; i<nums.size(); i++){
iter = hashMap.find(target-nums[i]);
if(iter != hashMap.end()){
ans.push_back(iter->second);// iter->first is key; iter-> second is value
ans.push_back(i);
return ans;
}
else{
hashMap.insert(pair<int,int>(nums[i],i));
}
}
return ans;
}
};
```
## Three sums
1. fix one number to change three sums to two sums
2. cannot use one space hash table because their may be repeat answers
3. sort the array first
4. to avoid repeat number, the next front and end index cannot be the same as the answer before
```cpp
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > res;
std::sort(num.begin(), num.end());
for (int i = 0; i < num.size(); i++) {
int target = -num[i];
int front = i + 1;
int back = num.size() - 1;
while (front < back) {
int sum = num[front] + num[back];
// Finding answer which start from number num[i]
if (sum < target)
front++;
else if (sum > target)
back--;
else {
vector<int> triplet = {num[i], num[front], num[back]};
res.push_back(triplet);
// Processing duplicates of Number 2
// Rolling the front pointer to the next different number forwards
while (front < back && num[front] == triplet[1]) front++;
// Processing duplicates of Number 3
// Rolling the back pointer to the next different number backwards
while (front < back && num[back] == triplet[2]) back--;
}
}
// Processing duplicates of Number 1
while (i + 1 < num.size() && num[i + 1] == num[i])
i++;
}
return res;
}
};
```
## Longest common prefix (google)
very easy
```cpp
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res = "";
for(int i=0;i<=200;i++){
char cur = strs[0][i];
for(int j=0;j<strs.size();j++){
if(strs[j].size()<=i | strs[j][i]!=cur){
return res;
}
}
res += cur;
}
return res;
}
};
```
## Wiggle sort I (Google)
Initial: sort the array first, then choose the largest and put it in the even position
Problem: slow
Sol1: sort the array first, and swap i=1 with 2, 3 with 4 and so on
```cpp
class Solution {
public:
void wiggleSort(vector<int>& nums) {
sort(nums.begin(), nums.end());
if (nums.size() <= 2) return;
for (int i = 2; i < nums.size(); i += 2) {
swap(nums[i], nums[i - 1]);
}
}
};
```
time complexity: O(nlgn)
Sol2:
```cpp
class Solution {
public:
void wiggleSort(vector<int>& nums) {
if (nums.size() <= 1) return;
for (int i = 1; i < nums.size(); ++i) {
if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) {
swap(nums[i], nums[i - 1]);
}
}
}
};
```
time complexity O(n)
## Wiggle Sort II
Initial: = is a big problem, my solution is similar to the initial sol in wiggle sort I
```cpp
// O(n) space
class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> tmp = nums;
int n = nums.size(), k = (n + 1) / 2, j = n;
sort(tmp.begin(), tmp.end());
for (int i = 0; i < n; ++i) {
nums[i] = i & 1 ? tmp[--j] : tmp[--k];
}
// always had a valid answer , this is the best situation
}
};
```
time complexity: O(nlgn)
space complexity O(n) for tmp
## Maximum Number of Weeks for Which You Can Work
Contest problem (solved by myself)
```cpp
class Solution {
public:
long long numberOfWeeks(vector<int>& milestones) {
vector<int>::const_iterator it;
it = max_element(milestones.begin(), milestones.end());
long long int sum=0;
for(auto m: milestones){
sum+=m;
}
if(sum - *it >= *it-1){
return sum;
}
else{
return 2*(sum - *it) + 1;
}
}
};
```
## Median of Two sorted array (Hard)
1. m = a1.size()
2. n = a2.size()
3. m+n = merge_array.size()
4. 找出a1,a2分別貢獻了幾個藍色部分的merge array
5. 須滿足 L1<=R2 && L2<=R1
```python
class Solution(object):
def median(self,A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m # make sure that len(A)<len(B), to reduce the time complexity
if n == 0:
raise ValueError
imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2 # i 代表A提供了幾個數字給藍色部分
j = half_len - i # j 代表B提供了幾個數字給藍色部分
if i < m and B[j-1] > A[i]:
# i is too small, must increase it (不滿足第五點之二)
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i is too big, must decrease it (不滿足第五點之一)
imax = i - 1
else:
# i is perfect
# 看第圖二
if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])
return (max_of_left + min_of_right) / 2.0
def findMedianSortedArrays(self, nums1, nums2):
return self.median(nums1,nums2)
```
## Container with the most water
easy
wall volume can be ignored
```cpp
class Solution {
public:
int maxArea(vector<int>& height) {
int res = 0, i = 0, j = height.size() - 1;
while (i < j) {
res = max(res, min(height[i], height[j]) * (j - i));
height[i] < height[j] ? ++i : --j;
}
return res;
}
};
```
## Trapping the rain water
### Method 1
1. set two pointer pointing at the first number that is not zero on the left side and right side
2. move the pointer which has a smaller number (表示此指針必定會遇到一個>=他的牆 -> 也代表其中的水一定會留住)
3. if the next position is smaller than the pointer, add the difference to the water_sum
4. else change the pointer to the next position
```cpp
class Solution {
public:
int trap(int A[], int n) {
int left=0; int right=n-1;
int res=0;
int maxleft=0, maxright=0;
while(left<=right){
if(A[left]<=A[right]){
if(A[left]>=maxleft) maxleft=A[left];
else res+=maxleft-A[left];
left++;
}
else{
if(A[right]>=maxright) maxright= A[right];
else res+=maxright-A[right];
right--;
}
}
return res;
}
};
```
## Remove duplicates from sorted array ii
==hard to me==
```cpp
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int p = 0;
// p 指向需要被改變的位置
// p-2 代表被改變的前三位，可能造成重複
for (int num : nums) {
if (p < 2 || num != nums[p - 2]) {
nums[p] = num;
p++;
}
}
return p;
}
};
```
## H-index
當i>=citations[i]時，已知i-1<citations[0~i-1]。因此，有i個文章被引用至少i次
```cpp
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end(), greater<int>());
for (int i = 0; i < citations.size(); ++i) {
if (i >= citations[i]) return i;
}
return citations.size();
}
};
```
## Meeting Room II (FB)
### Method 1
具體的解法，就是假設時間點都是排序的，那麽從左到右掃描，如果遇到一個會議的開始，會議室的個數就加一個，如果遇到一個會議的結束，會議室的個數就減一個（相當於釋放了一個會議室出來）, 然後取這個過程中的最大值就好了
i = start time -> \[i,1\]
j = end time -> \[j,-1\]
```java
class Solution:
def minMeetingRooms(self, intervals):
if not intervals:
return 0
tmp = sorted(x for i, j in intervals for x in [[i, 1], [j, -1]])
res, n = 0, 0
for i, v in tmp:
n += v
res = max(res, n)
return res
```
## Merge Interval
==Merge condition : A.end >= B.start==
Thus, if A[1] >= B[0], change A into {A[0], max(A[1],B[1])} (if A[0] >= B[0] )
See details : https://www.geeksforgeeks.org/merging-intervals/
```cpp
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector <vector<int>> res;
sort(intervals.begin(), intervals.end());
for(int i=0;i<intervals.size();i++){
if (res.size()==0){
res.push_back(intervals[i]);
continue;
}
if( res[res.size()-1][1] >= intervals[i][0]){ // front end is smaller than back front
res[res.size()-1][1] = max(res[res.size()-1][1], intervals[i][1]);
}
else{
res.push_back(intervals[i]);
}
}
return res;
}
};
```
## Insert Intervals
重疊要小心大於or小於
```cpp
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
for(int i=0;i<intervals.size();i++){
if(intervals[i][0]<=newInterval[0]){
if(intervals[i][1] < newInterval[0] ){ // cannot merge
res.push_back(intervals[i]);
continue;
}
}
else{
if(newInterval[1] < intervals[i][0] ){ // cannot merge
res.push_back(newInterval); // push in new Intervals and update it
for (int j=i;j<intervals.size();j++){
res.push_back(intervals[j]);
}
return res;
}
}
// can merge
newInterval[0] = min(intervals[i][0], newInterval[0]);
newInterval[1] = max(intervals[i][1], newInterval[1]);
}
res.push_back(newInterval);
return res;
}
};
```
## String to integer
A lot of details
```cpp
class Solution {
public:
int myAtoi(string s) {
int res = 0, neg_or_pos=1;
int split_pos=0, split_length=0;
// split the first part (whitespace)
if(s.find_first_not_of(' ')==string::npos) return 0;
s = s.substr(s.find_first_not_of(' '));
// split the second part (+,-)
if(s[0]=='+'){
neg_or_pos = 1;
s = s.substr(1);
}
else if(s[0]=='-'){
neg_or_pos = -1;
s = s.substr(1);
}
// split the third part (non digits)
for(int i=0;i<s.size();i++){
if(isdigit(s[i])) split_length++;
else break;
}
s = s.substr(split_pos, split_length);
if(s.size()==0) return 0;
// add the string into int
for(int i=s.size()-1;i>=0;i--){
if((res + (s[i]-'0')* pow(10, s.size()-i-1))>INT_MAX){
if(neg_or_pos==1){
return INT_MAX;
}
else{
return INT_MIN;
}
}
else res+=(s[i]-'0')* pow(10, s.size()-i-1);
}
return res*neg_or_pos;
}
};
```
## Jump Game
### My solution
dp[i] = 1 -> 表可以到達最後一個位置
dp[i] = 0 -> 表無法到達最後一個位置
```
class Solution {
public:
bool canJump(vector<int>& nums) {
int dp[100000]={0};
dp[nums.size()-1]=1;
for(int i=nums.size()-2;i>=0;i--){
int step = nums[i];
int sum = 0;
while(step>0){
if(step >= nums.size()-i){
sum++;
break;
}
else
sum+=dp[i+step];
step--;
}
if(sum){
dp[i] = 1;
}
}
return dp[0];
}
};
```
### Second solution
dp[i] 表示位置i的跳力(最遠可達距離)
若在過程中dp值小於0，代表無法跳向其它格，回傳false
dp[i] = max(上次dp跳力-1 or 新的跳力-1)
```cpp
class Solution {
public:
bool canJump(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
for (int i = 1; i < nums.size(); ++i) {
dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
if (dp[i] < 0) return false;
}
return true;
}
};
```
### Greedy solution
不使用dp，而是使用reach，表示當前可以移動到的最大位置
```cpp
class Solution {
public:
bool canJump(vector<int>& nums) {
int reach = 0; // max reach position
for(int i=0;i<nums.size();i++){
if(reach>= nums.size()-1 || i>reach)
break;
reach = max(reach, i+nums[i]);
}
return reach>=nums.size()-1;
}
};
```
## Jump Game II
```cpp
class Solution {
public:
int jump(vector<int>& nums) {
int res=0, cur=0, pre=0, i=0;
while(i<nums.size()){
if(i+nums[i]>=nums.size()-1){
if(i==nums.size()-1){
return res;
}
else{
res++;
return res;
}
}
int max_dis = 0, new_i=i;
for(int j=1;j<=nums[i];j++){
if(max_dis<i+j+nums[i+j]){
max_dis = i+j+nums[i+j];
new_i = i+j;
}
}
i = new_i;
res++;
}
return res;
}
};
```
Solution-2
pre : 上一個loop所能到達的最大位置
cur : 此loop所能到達的最大位置
i : 檢查過最大位置的點
```cpp
class Solution {
public:
int jump(vector<int>& nums) {
int res=0, cur=0, pre=0, i=0;
while(cur<nums.size()-1){
res++;
pre = cur;
for( ;i<=pre;i++){
cur = max(cur, nums[i]+i);
}
}
return res;
}
};
```
## Maximum XOR with an element from array ==Hard==
initial: brute force (sort the array first)
problem: slow
sol:
How to find the maximum of xor -> use prefix tree called trie
### ==Trie==
1. Build tries with every elements in the num
2. select one query number
3. go through the complement of the query number if trie node is not nullptr
4. XOR the final answer
Code is a little hard to understand, look at the comment carefully
```cpp
class Solution {
class TreeNode {
public:
TreeNode* next[2];
TreeNode () {next[0] = nullptr; next[1] = nullptr;};
};
TreeNode* buildTree(vector<int>& nums) {
// build the prefix tree
TreeNode* root = new TreeNode(), *cur;
int n = nums.size();
for (int i = 0; i < n; i++) {
int num = nums[i];
cur = root;
for (int j = 31; j >= 0; j--) {
int index = ((num >> j) & 1);
// (nums >> j) right shift j , &1 bitwise and
// index is the ith number of num in binary representation
// 注意tier的上層代表著nums位置低的地方
if (cur->next[index] == nullptr)
cur->next[index] = new TreeNode();
cur = cur->next[index];
}
}
return root;
}
int dfs(TreeNode* root, int x, int limit, int value, int height) {
// dfs to iterate through the trie
// value is the number that are going to XOR with = nums[j]
// height = current height of dfs (from 31-0) = the right shift amount
if (value > limit) return -1;
// nums[j] need to be smaller than mi
if (height == -1) return x^value;
// all level done
int bit_x = (x >> height) & 1;
if (root->next[1-bit_x] != nullptr) {
int v = dfs(root->next[1-bit_x], x, limit, (value | ((1-bit_x) << height)), height-1);
// (value | ((1-bit_x) << height)) : bitwise or with the original value
if (v >= 0) return v;
}
if (root->next[bit_x] != nullptr) {
int v = dfs(root->next[bit_x], x, limit, (value | (bit_x << height)), height-1);
if (v >= 0) return v;
}
return -1;
}
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> ans;
TreeNode* root = buildTree(nums);
for (const vector<int>& query : queries) {
int tmp = dfs(root, query[0], query[1], 0, 31);
ans.push_back(tmp);
}
return ans;
}
};
```
## Find K Closest Elements
Intuition
First of all, what is the biggest index the left bound could be? If there needs to be k elements, then the left bound's upper limit is arr.length - k, because if it were any further to the right, you would run out of elements to include in the final answer.
**Binary search is typically used to find if an element exists or where an element belongs in a sorted array.**
Let's consider two indices at each binary search operation, the usual mid, and some index mid + k. The relationship between these indices is significant because only one of them could possibly be in a final answer. For example, if mid = 2, and k = 3, then arr[2] and arr[5] could not possibly both be in the answer, since that would require taking 4 elements [arr[2], arr[3], arr[4], arr[5]].
This leads us to the question: how do we move our pointers left and right? If the element at arr[mid] is closer to x than arr[mid + k], then that means arr[mid + k], as well as every element to the right of it can never be in the answer. This means we should move our right pointer to avoid considering them. The logic is the same vice-versa - if arr[mid + k] is closer to x, then move the left pointer.
```cpp
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0, right = arr.size() - k;
while (left < right) {
int mid = left + (right - left) / 2;
if (x - arr[mid] > arr[mid + k] - x) left = mid + 1;
else right = mid;
}
return vector<int>(arr.begin() + left, arr.begin() + left + k);
}
};
```
## Maximum size subarray sum equals k ==Facebook==
A good problem for hash table + enumeration
```Initial``` Use an array to record the sum from 0~i, for example in example 1, the array = 1,0,5,3,6, and then we can do minus array i with j to represent i~j's sum. For example, i=3, then we will check if i, i-1,i-2 = k, but the complexity is O(n^2)
```Problem``` slow
```Hint``` Hash table, enumeration
```Sol```
- Use a hash table to replace the array so that we can directly search the hash table by k-sums to get the array that we have to minus
- If we already got sum in the hash table, we do not refresh a new value since the first one is the smallest length to minus -> which makes it maximum
```cpp
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
int sum = 0, res = 0;
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (sum == k) res = i + 1;
else if (m.count(sum - k)) res = max(res, i - m[sum - k]);
if (!m.count(sum)) m[sum] = i;
}
return res;
}
};
```
## K Empty Slots ==Hard==
Initial:
brute force -> 紀錄開花結果，並判斷是否為true
brute force revise -> 紀錄要達成的開花位置
ex [1,3,2], k=1, 第一天會紀錄 3, 第二天會紀 1 & (5)
若有花已經開在此位置，則判斷兩者中間是否都沒有花開
reference by http://zxi.mytechroad.com/blog/simulation/leetcode-683-k-empty-slots/
```cpp
// Author: Huahua
// Runtime: 192 ms (better than 97.85%)
class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
int n = flowers.size();
if (n == 0 || k >= n) return -1;
std::unique_ptr<char[]> f(new char[n+1]);
memset(f.get(), 0, (n + 1)*sizeof(char));
for (int i = 0; i < n; ++i)
if (IsValid(flowers[i], k, n, f.get()))
return i + 1;
return -1;
}
private:
bool IsValid(int x, int k, int n, char* f) {
f[x] = 1;
if (x + k + 1 <= n && f[x + k + 1]) {
bool valid = true;
for (int i = 1; i <= k; ++i)
if (f[x + i]) {
valid = false;
break;
}
if (valid) return true;
}
if (x - k - 1 > 0 && f[x - k - 1]) {
for (int i = 1; i <= k; ++i)
if (f[x - i]) return false;
return true;
}
return false;
}
};
```
Sol1
brute force在查找是否有k個空花的加速，使用BST。將開的花位置加入BST中，在若右方為x+k，則表其中間都沒有其它花開，左方同理。
```cpp
// Author: Huahua
class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
int n = flowers.size();
if (n == 0 || k >= n) return -1;
set<int> xs;
for (int i = 0; i < n; ++i) {
int x = flowers[i];
auto r = xs.insert(x).first;
auto l = r;
if (++r != xs.end() && *r == x + k + 1) return i + 1;
if (l != xs.begin() && *(--l) == x - k - 1) return i + 1;
}
return -1;
}
};
```
time compleixty O(nlgn)
space complexity O(n)
Sol2
1. bucket size k+1， thus there cannot exist answer in one bucket (need at least k+2 size for the answer)
2. bucket size k+1， thus the answer can only be with the adjacent bucket 1->k+2, k+1->2k+2
3. if(x is not min and not max) -> means there are flowers that are bloomed in distance smaller than k, thus it cannot be the answer
4. The only possible solution is the max or min in a bucket
```cpp
// Author: Huahua
// Runtime: 196 ms (better than 94%)
class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
int n = flowers.size();
if (n == 0 || k >= n) return -1;
++k;
int bs = (n + k - 1) / k;
vector<int> lows(bs, INT_MAX);
vector<int> highs(bs, INT_MIN);
for (int i = 0; i < n; ++i) {
int x = flowers[i];
int p = x / k;
if (x < lows[p]) {
lows[p] = x;
if (p > 0 && highs[p - 1] == x - k) return i + 1;
}
if (x > highs[p]) {
highs[p] = x;
if (p < bs - 1 && lows[p + 1] == x + k) return i + 1;
}
}
return -1;
}
};
```
Sign in with Wallet
Connect another wallet