# 2023.10.11 (Two Pointers)
Host - Al
Master - Lyndon
Interviewer - Al
Candidate - Jack

## Mock Interview
[Google doc](https://docs.google.com/document/d/1pJH4ke3axq8tJtlSbwC1ziO6I2SO8YmaOw3MQa1q7mk/edit?usp=sharing)
[1768. Merge Strings Alternately](https://leetcode.com/problems/merge-strings-alternately/)
Answer: (<10Mins)

// time: O(n)
// space: O(1)
// w1 = “abc”
// w2 = “pqr”
class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string ans = “”;
        int index = 0;
        int minLen = min(word1.size(), word2.size());  
        for(; index<minLen; index++){
	ans+= word1[i] + word2[i]; 
        }
        ans += word1.size() > word2.size() ? word1.substr(index) : word2.substr(index);
       return ans;
};

---

[1498. Number of Subsequences That Satisfy the Given Sum Condition](https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/)
Answer: (40Mins)

time: O(nlogn)
space : O(1)
int numSubseq(vector<int>& nums, int target) {

      sort(nums.begin(), nums.end());
      int ans = 0, n = nums.size();
      int MOD = 1e9+7;
      for(int i=0; i<n; i++){
        ans = (ans +  nums[i]*2<=target? 1: 0 )%MOD;
      }

      for(int i=0; i<n; i++){
           int j = findMaxIndexFromTail(nums, i, target);
   
           int diff = j - i + 1;
ans = (ans + (2^(diff-3) * (diff-2) + 1)%MOD)  %MOD;
    
      }

    return ans;
    }


int findMaxIndexFromTail(vector<int>& nums,int curIdx,  int target){

      int left = curIdx;
      int right = nums.size()-1;

     while(left<=right){
             int mid = left + (right-left)/2;
 
            if(nums[mid] + nums[curIdx]== target){
                  return mid;
            }

             if(nums[mid] + nums[curIdx] <target){
                    left = mid+1;
              }else{
                    right = mid-1;
               }
      }

     return left-1;
}

---
Feedback:
- the candidate know how to list all possible range
- the candidate know how to analyze the complexity
- the candidate know how to optimize searching using binary search
- Be careful of edge case and conditions
- It would be better if the candidate be able to count the correct # of answer in each possible range

## Topic discussion
## Two Pointers
Reference
https://hackmd.io/PPkKxq3ITBu8fQlz3_gbeA?view

### Type

### 1. Two Arrays
兩個指針分別指到不同array

https://leetcode.com/problems/merge-strings-alternately/

https://leetcode.com/problems/merge-sorted-array/
從最右邊開始由大往小放

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
};

Time: $O(m + n)$
Space: $O(1)$

### 2. Left and Right
兩個指針分別從最左跟最右開始往中間前進直到相碰

#### a. String
[Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)
[Valid Palindrome II](https://leetcode.com/problems/valid-palindrome-ii/)
[Reverse String](https://leetcode.com/problems/reverse-string/)

從字串最左及最右開始比較是否相等或是交換

class Solution {
public:


    bool isPalindrome(const string& s, int l, int r)
    {
        while(l <= r)
        {
            if(s[l] != s[r])
            {
                return false;
            }
            l++;
            r--;
        }

        return true;
    }
    
    bool validPalindrome(string s) {
        if(s.size() <= 2)
        {
            return true;
        }
        int l = 0;
        int r = s.size() - 1;

        while(l <= r)
        {
            if(s[l] != s[r])
            {
                return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
            }
            else
            {
                l++;
                r--;
            }
        }

        return true;
    }
};

Time: $O(n)
Space: $O(1)

#### 3. Sum

[Two Sum ii Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)
[3Sum](https://leetcode.com/problems/3sum/)
[4Sum](https://leetcode.com/problems/4sum/)

從最左及最右開始計算sum
sum > target => 太大 右指針往左
sum < target => 太小 左指針往右

3Sum: 先sort array 再固定一位置 => two sum input array sorted
4Sum: 先sort array 再固定i j 兩個位置

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;

        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 2; i++)
        {
            if(i && nums[i - 1] == nums[i])
            {
                continue;
            }

            int l = i + 1;
            int r = nums.size() - 1;

            while(l < r)
            {
                if(r == i)
                {
                    break;
                }
                
                int sum = nums[l] + nums[r] + nums[i];

                if(sum > 0)
                {
                    r--;
                }
                else if (sum < 0)
                {
                    l++;
                }
                else
                {
                    result.push_back({nums[l], nums[r]
                        , 0 - nums[l] - nums[r]});

                    //  找到下一個不重複的點
                    while(l < nums.size() - 1 && nums[l + 1] == nums[l])
                    {
                        l++;
                    }

                    while(r >= 1 && nums[r - 1] == nums[r])
                    {
                        r--;
                    }

                    l++;
                    r--;
                }
            }
        }

        return result;
    }
};

Two Sum

| Method | Time | Space |
| -------- | -------- | -------- |
| Hashtable | $O(n)$ | $O(n)$ |
| Two Pointers| $O(nlogn)$| $O(1)$

3 Sum

| Method | Time | Space |
| -------- | -------- | -------- |
| Hashtable | $O(n^2)$ | $O(n)$ |
| Two Pointers| $O(n^2)$| $O(1)$

#### c. Water
[Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
[Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)

水的量等於 (左右兩邊到該位置最大的值的**較小**的那邊 - 底) x 長度



class Solution {
public:
    int trap(vector<int>& height) {
        // dp

        if(height.size() == 1)
        {
            return 0;
        }

        vector<int> lm(height.size(), 0);
        vector<int> rm(height.size(), 0);

        int area = 0;

        lm[0] = height[0];
        rm[height.size() - 1] = height.back();

        for(int i = 1; i < height.size(); i++)
        {
            lm[i] = max(lm[i - 1], height[i]);
        }

        for(int i = height.size() - 2; i >= 0; i--)
        {
            rm[i] = max(rm[i + 1], height[i]);
        }

        for(int i = 0; i < height.size(); i++)
        {
            area += min(lm[i], rm[i]) - height[i];
        }

        return area;
    }
};

Time: $O(n)$
Space: $O(n)$

class Solution {
public:
    int trap(vector<int>& height) {
        // two pointer
        if(height.size() == 1)
        {
            return 0;
        }

        int l = 0;
        int r = height.size() - 1;
        int maxL = height[l];
        int maxR = height[r];
        int area = 0;

        while(l < r)
        {
            if(maxL < maxR)
            {
                area += maxL - height[l];
                maxL = max(maxL, height[++l]);
            }
            else
            {
                area += maxR - height[r];
                maxR = max(maxR, height[--r]);
            }
        }


        return area;
    }
};

Time: $O(n)$
Space: $O(1)$

### 2. Quick and Slow
兩個指針都從左邊前進 一個會走較快 直到快的抵達最右邊

[Move Zeros](https://leetcode.com/problems/move-zeroes/)

指針1: 非0的位置 指針2: 目前位置

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if(nums.size() == 1)
        {
            return;
        }
        
        int x = 0; // current index
        int y = 0; // none zero
        while(y < nums.size())
        {
            if(nums[y] == 0)
            {
                y++;
            }
            else
            {
                swap(nums[x], nums[y]);
                x++;
                y++;
            }
        }
    }
};

Time: $O(n)$
Space: $O(1)$

另一種做法是先將非零數依序從第一個位置放並記錄，最後再將0個數補上

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int index = 0;
        for(const auto& num : nums)
        {
            if(num != 0)
            {
                nums[index] = num;
                index++;
            }
        }
        
        for(int i = index; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }
};

Time: $O(n)$
Space: $O(1)$

[Remove Duplicates From Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)

[Remove Duplicates From Sorted Array II](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/)

指針1: 非重複的數字位置 指針2: 目前位置

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int index = 1;

        int check = 1;

        int last = nums[0];

        int count = 1;


        while(check < nums.size())
        {
            if(last != nums[check])
            {
                last = nums[check];
                nums[index] = nums[check];
                index++;
                check++;
                count = 1;
            }
            else if(count < 2) // 2 可以換成k
            {
                nums[index] = nums[check];
                index++;
                check++;
                count++;
            }
            else
            {
                count++;
                check++;
            }
        }

        return index;
    }
};

Time: $O(n)$
Space: $O(1)$

另一種直接用for迴圈的寫法

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int index = 0;
        for (int i = 0; i < nums.size(); i++) {
            // 2 可以換成 k
            if (i < 2 || nums[i] > nums[i - 2]) {
                nums[index++] = nums[i];
            }
        }
        return index;
    }
};

Time: $O(n)$
Space: $O(1)$