---
# System prepended metadata

title: 2. Two pointers (5) - Python
tags: [working]

---

# 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 可以分為兩種類型: 

* 快慢指標
    * 兩個指標同時往頭/尾的方向走訪
    * 一個指標照順序走訪，另一個指標根據題目需求移動，所以會有快慢之分
    ![fast-slow pointers](https://miro.medium.com/v2/resize:fit:640/format:webp/1*2kuD0zoJ-T3hCCGka0RgJw.gif)
    (圖片來自: [Basics of Two Pointers Technique](https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e))
* 左右指標
    * 兩個指標往相反方向移動
    ![Reverse Pointers](https://miro.medium.com/v2/resize:fit:640/format:webp/1*D9jkUT0zI8dZahhQhCfwrA.gif)
    (圖片來自: [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:

![img](https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/0c25cb81-1095-4382-fff2-6ef77c1fd100/public)

```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 影片後半段解說
:::





