# Two Pointers

[**167. Two Sum II - Input array is sorted**](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)

Use two pointers to move from beginning and end. Until two pointers converge:

* Move end pointer when the sum of two numbers at the pointers are larger than the target. 
* Move start pointer when the sum is smaller than the target
* return pointer positions when the sum equals to the target

```java
public int[] twoSum(int[] numbers, int target) {
    int i = 0;
    int j = numbers.length - 1;
    while (i < j) {
        if (numbers[i] + numbers[j] == target) {
            return new int[]{i + 1, j + 1};
        } else if (numbers[i] + numbers[j] < target) {
            i++;
        } else {
            j--;
        }
    }
    return null;
}
```

#### [**344. Reverse String**](https://leetcode.com/problems/reverse-string/)

```java
public void reverseString(char[] s) {
    int i = 0, j = s.length - 1;
    while (i < j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
        i++;
        j--;
    }
}
```

#### [**151. Reverse Words in a String**](https://leetcode.com/problems/reverse-words-in-a-string/)

Split words by " ". Reverse order by using two pointers technique.

Java:

```java
public String reverseWords(String s) {
    String[] sArr = s.trim().split(" ");
    StringBuilder sb = new StringBuilder();
    for (int i = sArr.length - 1; i >= 0; i--) {
        if (!sArr[i].isEmpty()) {
            sb.append(sArr[i]).append(" ");
        }
    }
    return sb.toString().trim();
}
```

Python:

```python
 def reverseWords(self, s: str) -> str:
        # strs = s.strip().split(" ")
        # i = 0
        # j = len(strs) - 1
        # while i < j:
        #     strs[i], strs[j] = strs[j], strs[i]
        #     i += 1
        #     j -= 1
   return " ".join(reversed(s.split()))

```

#### [**345. Reverse Vowels of a String**](https://leetcode.com/problems/reverse-vowels-of-a-string/)

Save all vowels to a set. Use two pointers to move from beginning and end. Keep moving the pointer until the pointer encounter a vowel character. Swap vowels.

```python
    def reverseVowels(self, s: str) -> str:
        _set = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
        i = 0
        j = len(s) - 1
        strs = list(s)
        while i < j :
            while i < j and strs[i] not in _set :
                i += 1
            while i < j and strs[j] not in _set :
                j -= 1
            strs[i], strs[j] = strs[j], strs[i]
            i += 1
            j -= 1
        return ''.join(strs)
```

#### [**125. Valid Palindrome**](https://leetcode.com/problems/valid-palindrome/)

Use two pointers to move from beginning and end. Keep moving the pointer until the pointer encounter an alphanumeric character. Check if both characters are the same.

```python
    def isPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s) - 1
        s = list(s)
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1
            if s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True
```

#### [**283. Move Zeroes**](https://leetcode.com/problems/move-zeroes/)

Use two pointers to start both at the beginning of array. i to count the numbers of non-zero elements, j to traverse to find none zero elements. When j detects a candidate, swap with i, i++.

```python
    def moveZeroes(self, nums: List[int]) -> None:
     	   i = 0
            for j in range(len(nums)):
                if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
```

Instead of swap, filling the rest of i with 0 also works. This is because i counts the number of non-zeros, the rest would be zeros.

```python
    def moveZeroes(self, nums: List[int]) -> None:
        i = 0
        for j in range(0, len(nums)):
            if nums[j] != 0 :
                nums[i] = nums[j]
                i += 1
        while i < len(nums):
            nums[i] = 0
            i += 1
```

#### [88. Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/)

```python
def merge(self, nums1: List[int], m: int, 
           nums2: List[int], n: int) -> None:
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums2[j] > nums1[i]:
            nums1[k] = nums2[j]
            j -= 1
        else :
            nums1[k] = nums1[i]
            i -= 1
        k -= 1
    nums1[:j + 1] = nums2[:j + 1]
```

#### [27. Remove Element](https://leetcode.com/problems/remove-element/)

```python
   def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for j in range(0, len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        return i
```

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

```python
def removeDuplicates(self, nums: List[int]) -> int:
    i = 0
    for j in range(0, len(nums)) :
        if nums[i] != nums[j]:
            i += 1
            nums[i] = nums[j]
    return i + 1
```

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

One j pointer to loop over the array, the other pointer stores the right sequence of the result, which satisfy that 2 digits behind was smaller than number at j. If the numbers one those two pointers are the same, it means that there are 3 or more than 3 same numbers, thus move j only until you find the next larger element.&#x20;

For example:

&#x20;`i   j`&#x20;

`[1,1,1,2,2,4,5,6,6,6]`

This is a situation to replace the number at i with the number at j.

```python
def removeDuplicates(self, nums: List[int]) -> int:
    i = 0
    for j in range(0, len(nums)) :
        if i < 2 or nums[i - 2] < nums[j]:
            nums[i] = nums[j]
            i += 1
    return i
```

844\. Backspace String Compare

Word Consisted by Another Word

#### [349. Intersection of Two Arrays](https://leetcode.com/problems/intersection-of-two-arrays/) & [350. Intersection of Two Arrays II](https://leetcode.com/problems/intersection-of-two-arrays-ii/)

Use set to store the shorter array and check on the array.

```
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        _set = set() 
        for n in nums1:
            _set.add(n)
        res = set()
        for n in nums2:
            if n in _set: 
                res.add(n)
        return list(res)
```

Use HashMap on 350 to count each element. If sorted. Use two pointers start from beginning.

```python
   def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        res = []
        i = 0
        j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                res.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return res
```

#### Follow up:

What if nums1's size is small compared to nums2's size? Which algorithm is better? HashMap

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?&#x20;

1. Store the two strings in distributed system(whether self designed or not), then using ***MapReduce*** technique to solve the problem;
2. Processing the Strings by ***chunk***, which fits the memory, then deal with each chunk of data at a time;
3. Processing the Strings by ***streaming***, then check.

#### [189. Rotate Array](https://leetcode.com/problems/rotate-array/)

Flip 0 to n - k and flip n - k to n, then flip the entire array

```python
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        nums[0:n-k] = nums[0:n-k][::-1]
        nums[n-k:] = nums[n-k:][::-1]
        nums = nums.reverse()
```

#### [299. Bulls and Cows](https://leetcode.com/problems/bulls-and-cows/)

```python
    def getHint(self, secret: str, guess: str) -> str:
        bullset = set()
        count = {}
        bull = 0
        for i in range(0, len(secret)):
            if secret[i] == guess[i]: 
                bull += 1
                bullset.add(i)
            else :
                if secret[i] in count:
                    count[secret[i]] += 1
                else:
                    count[secret[i]] = 1
        cow = 0
        for i in range(0, len(guess)):
            if i not in bullset:
                if guess[i] in count and count[guess[i]] > 0:
                    cow += 1
                    count[guess[i]] -= 1
        return str(bull) + "A" + str(cow) + "B"
```

#### [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)

```python
    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height) - 1
        result = 0
        while i < j:
            result = max(result, min(height[i], height[j]) * (j - i))
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return result
```

#### [42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)

```java
public int trap(int[] height) {
    int LMax = 0, RMax = 0;
    int L = 0, R = height.length - 1;
    int res = 0;
    while (L < R) {
        if (height[L] < height[R]) {
            if (height[L] > LMax) {
                LMax = height[L];
            } else {
                res += LMax - height[L];
            }
            L++;
        } else {
            if (height[R] > RMax) {
                RMax = height[R];
            } else {
                res += RMax - height[R];
            }
            R--;
        }
    }
    return res;
}
```

217\. Contains Duplicate

219\. Contains Duplicate II

220\. Contains Duplicate III

#### [277. Find the Celebrity](https://leetcode.com/problems/find-the-celebrity/)

```python
    def findCelebrity(self, n: int) -> int:
        cand = 0
        for i in range(1, n):
            if not knows(i, cand):
                cand = i
        for i in range(n):
            if cand != i and (not knows(i, cand) or knows(cand, i)):
                return -1
        return cand
```

#### [75. Sort Colors](https://leetcode.com/problems/sort-colors/)

Use L and R on each k&#x20;

```java
    public void sortColors(int[] nums) {
        int L = 0, R = nums.length - 1, k = 0;
        while (k <= R) {
            if (nums[k] == 0) {
                swap(nums, L++, k++);
            } else if (nums[k] == 2) {
                swap(nums, R--, k);
            } else {
                k++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
```

#### [238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)

Since the requirement states "can't use division", we can only generate the result by multiplication. It starts  to build an array with all product of the elements before current. For example:

Array = \[3,5,1,2], res start withs \[1,1,1, 1],  then res\[i] = res\[i - 1] \* array\[i - 1]

res = \[1, 3, 15, 15]

Then multiply from the right, with a start variable as 1, keeps the variable as all the products along the way.&#x20;

product = 1

1. res = \[          15 ] then product = 2 \* 1 = 2
2. res = \[ .    30,15 ] then product = 1 \* 2
3. res = \[     6, 30,15 ] then product = 5 \* 2 = 10
4. res = \[10, 6, 30,15 ]&#x20;

This method is due to multiply all elements before the current product from left, then multiply all products from the right. It skips the current element.

```java
public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, 1);
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    int product = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] = res[i] * product;
        product *= nums[i];
    }
    return res;
}
```

334\. Increasing Triplet Subsequence

#### [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)

This question can be solved by sort, which takes `O(nlogn)`. A better way is to use a slow and fast pointer:

![Floyd's Tortoise and Hare](https://249794273-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Laur3QE_YAExtEZegFt%2F-M8g4X7jLBJvJXdLwyw9%2F-M8kfKDmfmOdbnASSP1L%2Fimage.png?alt=media\&token=bdd8d5d1-cc79-4bf0-81ad-0fb5754b2188)

1. Start with index 0, find the point where two pointers meet. That indicates that there is a cycle in the array.&#x20;
2. Move one pointer to the start point. Move both pointers forward in the same speed until they meet again.&#x20;
3. Return the index, which is the entrance of the cycle

*Refer to* [*Linked List Cycle II*](https://leetcode.com/problems/linked-list-cycle-ii/)

```
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
```

169\. Majority Element

229\. Majority Element II

Trapping Rain Water

41\. First Missing Positive

#### [243. Shortest Word Distance](https://leetcode.com/problems/shortest-word-distance/)

```java
public int shortestDistance(String[] words, String word1, String word2) {
    int ind1 = -1;
    int ind2 = -1;
    int min = Integer.MAX_VALUE;
    for (int i = 0 ; i < words.length; i++) {
        if (words[i].equals(word1)) {
            ind1 = i;
        } else if (words[i].equals(word2)) {
            ind2 = i;
        }
        if (ind1 != -1 && ind2 != -1) min = Math.min(min, Math.abs(ind1 - ind2));
    }
    return min;
}
```

#### [244. Shortest Word Distance II](https://leetcode.com/problems/shortest-word-distance-ii/)

```java
Map<String, List<Integer>> map;
public WordDistance(String[] words) {
    map = new HashMap<>();
    for (int i = 0; i < words.length; i++) {
        map.putIfAbsent(words[i], new ArrayList<>());
        map.get(words[i]).add(i);
    }
}

public int shortest(String word1, String word2) {
    List<Integer> l1 = map.get(word1);
    List<Integer> l2 = map.get(word2);
    int i = 0, j = 0;
    int min = Integer.MAX_VALUE;
    while (i < l1.size() && j < l2.size()) {
        int a = l1.get(i), b = l2.get(j);
        min = Math.min(min, Math.abs(a - b));
        if (a < b) {
            i++;
        } else {
            j++;
        }
    }
    return min;
}
```

245\. Shortest Word Distance III

611\. Valid Triangle Number

55\. Jump Game

45\. Jump Game II

274\. H-Index

275\. H-Index II

128\. Longest Consecutive Sequence

[697. Degree of an Array](https://leetcode.com/problems/degree-of-an-array/)

```java
public int findShortestSubArray(int[] nums) {
    Map<Integer, Integer> left = new HashMap<>();
    Map<Integer, Integer> right = new HashMap<>();
    Map<Integer, Integer> count = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (!left.containsKey(num)) {
            left.put(num, i);
        }
        right.put(num, i);
        count.put(num, count.getOrDefault(num, 0) + 1);
    }

    int max = Collections.max(count.values());
    int res = nums.length;
    for (int key : count.keySet()) {
        if (count.get(key) == max) {
            res = Math.min(res, right.get(key) - left.get(key) + 1);
        }
    }
    return res;
}
```

[2444. Count Subarrays With Fixed Bounds](https://leetcode.com/problems/count-subarrays-with-fixed-bounds/)

Explanation: <https://leetcode.com/problems/count-subarrays-with-fixed-bounds/editorial>

```cpp
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
    int left = -1;
    int minPos = -1, maxPos = -1;
    long res = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] < minK || nums[i] > maxK) {
            left = i;
        }
        if (nums[i] == minK) minPos = i;
        if (nums[i] == maxK) maxPos = i;
        res += max(0, min(minPos, maxPos) - left);
    }
    return res;
}
```