# Two pointers (5)
> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
>
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)
<!-- 常用色碼紀錄
Easy: <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard: <font color="#ee2f56">**Hard**</font>
-->
Two pointer 常用於搜索或比較，在給定的資料結構中使用兩個 pointer 做循環，適合題目限定禁止使用額外空間等 in-place 限制的問題，常用在 string、array 或 linked list 的題目中。
Two pointer 可以分為兩種類型:
* 快慢指標
* 兩個指標同時往頭/尾的方向走訪
* 一個指標照順序走訪，另一個指標根據題目需求移動，所以會有快慢之分
(圖片來自: [Basics of Two Pointers Technique](https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e))
* 左右指標
* 兩個指標往相反方向移動
(圖片來自: [Basics of Two Pointers Technique](https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e))
##### Reference:
[[1] Basics of Two Pointers Technique](https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e)
[[2] Two Pointers](https://hackmd.io/@SupportCoding/Two_Pointers)
[[3] 第十天 - Two-pointer 介紹](https://ithelp.ithome.com.tw/m/articles/10262277)
## 1. Valid palindrome
<font color="#00ad5f">**Easy**</font>
> Given a string `s`, return `True` if it is a **palindrome**, otherwise return `False`.
>
> A **palindrom** is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alplanumeric charcters.
### Example 1:
```java
Inputs: s = "Was it a car or a cat I saw ?"
Output: True
```
Explanation: After considering only alphanumerical characters we hae "wasitacaroracatisaw", which is a palindrome.
### Example 2:
```java
Input: s = "tab a cat"
Output: False
```
### Constraints
* `1 <= s.length <= 1000`
* `s` is made up of only printable ASII characters.
### Solution
#### 1. Me
```python=
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.strip("?.!") # s = "Was it a car or a cat I saw?"
s = s.split(" ") # s = ["Was", "it", "a", "car", "or", "a", "cat", "I", "saw"]
s = "".join(s) # s = "WasitacaroracatIsaw"
s = s.lower() # s = "wasitacaroracatisaw"
for i in range(len(s)):
if s[0+i] == s[-1-i]:
continue
else:
return False
return True
```
隱含 two pointer 的概念，但一開始處理字串的過程過於粗糙，無法對應到所有可能出現的標點符號，且空格的處理也不太漂亮。
#### 2. Reverse
```python=
# Reverse
class Solution:
def isPalindrome(self, s: str) -> bool:
newStr = ""
for c in s:
if c.isalnum():
newStr += c.lower()
return newStr == newStr[::-1]
```
使用 Python 內建的字串方法 `isalnum()` 檢查字元或字串是不是由字母和數字組成。再比較原始字串與反轉後的字串是否相等。
幾個問題點 :
* 考試不一定能夠使用 `isalnum()` 字串方法處理原始字串
* 根據 constraints 的說明，可以考慮使用 ASCII code 來解決
* 需要額外的空間儲存新字串，空間複雜度為 $O(n)$
* 可以使用 two pointer 的方式改善
#### 3. Two pointer
```python=
# Two pointer
class Solution:
def isPalindrome(self, s: str) -> bool:
LeftPointer, RightPointer = 0, len(s) - 1
while (LeftPointer < RightPointer):
while (LeftPointer < RightPointer) and (not self.AlphaNum(s[LeftPointer])):
LeftPointer += 1
while (LeftPointer < RightPointer) and (not self.AlphaNum(s[RightPointer])):
RightPointer -= 1
if (s[LeftPointer].lower() != s[RightPointer].lower()):
return False
LeftPointer += 1
RightPointer -= 1
return True
def AlphaNum(self, ch):
return (ord("a") <= ord(ch) <= ord("z")) or \
(ord("A") <= ord(ch) <= ord("Z")) or \
(ord("0") <= ord(ch) <= ord("9"))
```
幾個改善後的點 :
* 使用 [ASCII code](https://www.ascii-code.com/) 的方法來判斷字元是否為字母或數字
* 原始字串兩端分別用兩個 pointer 循歷，循歷的過程中同時檢查該字元是否為字母/數字
* 非字母/數字的話使用 `while` 迴圈不斷 +1/-1 直到 pointer 指向字母/數字
* 勿忘邊界條件
## 2. Two Sum Ⅱ Input Array Is Sorted
<font color="#ffbb00">**Medium**</font>
> Given an array of integers `numbers` that is sorted in **non-decreasing order**.
>
> Return the indices (**1-indexed**) of two numbers, ``[index1, index2]``, such that they add up to a given target number `target` and `index1 < index2`. Note that `index1` and `index2` cannot be equal, therefore you may not use the same element twice.
>
> There will always be **exactly one valid solution**.
>
> Your solution must use $O(1)$ additional space.
### Example 1:
```java
Input: nubers = [1, 2, 3, 4], target = 3
Output: [1, 2]
```
Explanation:
The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, `index1` = 1, `index2` = 2. We return `[1, 2]`.
### Constraints
* `2 <= numbers.length <= 1000`
* `-1000 <= numbers[i] <= 1000`
* `-1000 <= target <= 1000`
### Solution
#### 1. My
```python=
# My solution
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for p1 in range(len(numbers)-1):
for p2 in range(p1+1, len(numbers)):
if (numbers[p1] + numbers[p2]) == target:
return [p1+1, p2+1]
```
最基礎的暴力解，時間複查度是 $O(n^2)$，空間複雜度符合要求是 $O(1)$
---
嘗試使用 two pointer 的方式解決。給定兩個 pointer，一個是從左向右尋遍的 `slowPointer`，一個是從右向左尋遍的 `fastPointer`。
因為 array 已經以 **non-decreasing** 的方式排序，所以檢查每組最大的的數字
* 如果 `slowPointer + fastPointer < target`
* 答案太小，所以 slowPointer + 1 往右移動來讓數字變大
* 如果 `slowPointer + fastPointer > target`
* 答案太大，所以 `fastPointer - 1` **不斷**往左移動來讓數字變小直到符合 target
* 如果沒有解，則 `slowPointer + 1` 後重頭開始上面步驟
但因為內部涉及到 `fastPointer` 不斷往左移動，最壞情況會一樣會跑完整個 array，所以時間複雜度依舊是 $O(n^2)$
```python=
# My solution (2)
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
slowPointer = 0
while slowPointer < len(numbers):
fastPointer = len(numbers) - 1
if (numbers[slowPointer] + numbers[fastPointer]) == target:
return [slowPointer+1, fastPointer+1]
elif (numbers[slowPointer] + numbers[fastPointer]) < target:
slowPointer += 1
else:
while fastPointer != slowPointer:
if (numbers[slowPointer] + numbers[fastPointer]) == target:
return [slowPointer+1, fastPointer+1]
else:
fastPointer -= 1
slowPointer += 1
```
#### 2. Correct version
參考上面的 two pointer 中的左右指標概念做修改。當 `slowPointer + fastPointer > target` 答案太大時，只要把 `fastPointer` 往左**移動一次**即可，移動後再重複整個步驟。
```python=
# My solution (3)
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
LeftPointer, RightPointer = 0, len(numbers) - 1
while LeftPointer < RightPointer:
if numbers[LeftPointer] + numbers[RightPointer] > target:
RightPointer -= 1
elif numbers[LeftPointer] + numbers[RightPointer] == target:
return [LeftPointer+1, RightPointer+1]
else:
LeftPointer += 1
```
## 3. 3 sum
<font color="#ffbb00">**Medium**</font>
> Given an integer aray `nums`, return all the triples `[nums[i], nums[j], nums[k]]` where `nums[i] + nums[j] + nums[k] == 0`, ans the indices `i`, `j` and `k` are all distinct
>
> The output should *not* contain any duplicate triplets. You may return the output and the triplets in **any order**
### Example 1:
```java
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
```
Explanation:
`nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0`.
`nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0`.
`nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0`.
The distinct triplets are `[-1,0,1]` and `[-1,-1,2]`.
### Example 2:
```java
Input: nums = [0, 1, 1]
Output: []
```
### Example 3:
```java
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
```
### Constraints
* `3 <= nums.length <= 1000`
* `-10^5 <= nums[i] <= 10^5`
### Solution
#### 1. Brute-force
暴力解，必須使用三個迴圈來表示三數字歷遍整個陣列，複雜度為 $O(n^3)$
#### 2. Correct
因為 two pointer 的目的是可以降低 array 在搜索時的複雜度，從 $O(n^2)$ 變為 $O(n)$。
此處的 3-sum 問題中，同樣使用三個變數來表示歷遍 array 的三個數字，但
* 其中兩個變數使用 two pointer 的方式做搜尋，使複雜度從 $O(n^3)$ 降為 $O(n^2)$
* 在歷遍 array 的過程中三個變數每推進一位就要檢查是不是會與前一個元素相同
```python=
# correct solution
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for idx, a in enumerate(nums):
if a > 0: # if a > 0, then all rest number is greater than 0
break # then the 3-sum can't equal to 0
if idx > 0 and a == nums[idx-1]: # check if the first pointer a is same as the previous
continue
LeftPointer, RightPointer = idx + 1, len(nums) - 1
# use two pointer to check 3-sum
while LeftPointer < RightPointer:
ThreeSum = a + nums[LeftPointer] + nums[RightPointer]
if ThreeSum > 0:
RightPointer -= 1
elif ThreeSum < 0:
LeftPointer += 1
else:
res.append([a, nums[LeftPointer], nums[RightPointer]])
LeftPointer += 1
RightPointer -= 1
while ((nums[LeftPointer]==nums[LeftPointer-1]) and
(LeftPointer < RightPointer)):
LeftPointer += 1
while ((nums[RightPointer]==nums[RightPointer+1]) and
(LeftPointer < RightPointer)):
RightPointer -= 1
return res
```
## 4. Trapping Rain Water
<font color="#ee2f56">**Hard**</font>
> You are given an array non-negative integers heights which represent an elevation map. Each value `heights[i]` represents the height of a bar, which has a width of `1`.
>
> Return the maximum area of water that can be trapped between the bars.
### Example 1:
```java
Input: height = [0, 2, 0, 3, 1, 0, 1, 3, 2, 1]
Output: 9
```
### Constraints
* `1 <= height.length <= 1000`
* `0 <= height[i] <= 1000`
### Solutio
#### 1. Correct (1)
核心想法是考慮每個位置能夠裝多少的水。每個位置能夠裝多少水而不會溢出，是由該點的兩側邊界決定。找到該點左側跟右側邊界後取最小值 `min(LBound, RBound` 就可以就可以知道能裝多少水。
但實際上如果該點的高度超出邊界最小值，也還是不能裝水，所以需要再檢查 `min - height[i] < 0` 是否成立，也就是該點高度會不會超出邊界，如果超出邊界那該點也不能裝水。
只要歷遍 array 一次就可以得到各點對應的邊界值，所以時間複雜度是 $O(n)$，但因為需要額外的 array 儲存邊界值，所以空間複雜度是 $O(n)$。
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| LBound | 0 | 0 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 |
| RBound | 0 | 2 | 0 | 3 | 1 | 0 | 1 | 3 | 2 | 1 |
| `height[i]` | 0 | 2 | 0 | 3 | 1 | 0 | 1 | 3 | 2 | 1 |
```python=
# Correct (1)
class Solution:
def trap(self, height: List[int]) -> int:
LP, RP = 0, 0
LBound, RBound = [0]*len(height), [0]*len(height)
res = 0
for i in range(1, len(height)):
if height[i-1] > LP:
LP = height[i-1]
LBound[i] = LP
else:
LBound[i] = LP
for j in range(-2, -1-len(height), -1):
if height[j+1] > RP:
RP = height[j+1]
RBound[j] = RP
else:
RBound[j] = RP
for i in range(len(height)):
minimum = min(LBound[i], RBound[i])
if minimum > height[i]:
res += (minimum - height[i])
else:
continue
return res
```
#### 2. Correct (2) modify
:::warning
使用 two pointer 的方法可以讓空間複雜度達到 $O(1)$，詳見 Neetcode 影片後半段解說
:::
Sign in with Wallet
Connect another wallet