# Gao's LeetCode 101: Two Pointers
## 0. Post Details
- Reference: [Gao et al., LeetCode 101 - A Grinding Guide, 2001.](https://noworneverev.github.io/leetcode_101/category/4-%E5%8D%83%E5%A5%87%E7%99%BE%E6%80%AA%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95)
- Post by: Jedd Yang
- Date: 2025-03-17
- Keywords: Two Pointers
## 1. Problems
### <font color="#FFA500">167. Two Sum II - Input Array Is Sorted</font>
> Given a 1-indexed array of integers `numbers` that is already sorted in non-decreasing order, find two numbers such that they add up to a specific `target` number. Let these two numbers be `numbers[index_1]` and `numbers[index_2]` where `1 <= index1 < index2 <= numbers.length`. Return the indices of the two numbers, `index_1` and `index_2`, added by one as an integer array `[index_1, index_2]` of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space.
:::danger
- Approach： Double for-loop.
- Complexity: WA. Time $O(n^2)$; Space $O(n)$.
:::
```cpp
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> result;
for (int i = 0; i < numbers.size(); ++i){
int search = target - numbers[i];
for (int j = i + 1; j < numbers.size(); ++j){
if (numbers[j] == search){
result.push_back(i + 1);
result.push_back(j + 1);
return result;
}
}
}
return result;
}
};
```
But 2 for-loop is too slow, try hash table.
:::warning
- Approach： Hash table.
- Complexity: Time $O(n)$; Space $O(n)$.
:::
```cpp
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
unordered_map<int, int> numIndex; //數字 : 索引
for (int i = 0; i < numbers.size(); ++i){
int complement = target - numbers[i];
if (numIndex.count(complement)){
//先查過去有沒有加入當前數字（numbers[i]）的 complment
// 若有，則回傳 {當前數字（numbers[i]）的 complment
// 的索引 + 1（數字小），當前數字（numbers[i]）的索引 + 1（數字大）}
return { numIndex[complement] + 1, i + 1};
}
numIndex[numbers[i]] = i; // 再加 numbers[i]
}
return {};
}
};
```
Hash Table requires additional memory, making it `O(n)`, let's try proper 2 pointers.
:::success
- Approach： Two pointers.
- Complexity: Time $O(n)$; Space $O(1)$.
:::
```cpp
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right){
if (numbers[left] + numbers[right] == target){
return {left + 1, right + 1};
}else if (numbers[left] + numbers[right] < target){
++left;
}else{
--right;
}
}
return {};
}
};
```
Also, becasue we used while-loop, avoiding for-loop, the time complexity is largely decreased.
### <font color="#32CD32">88. Merge Sorted Array</font>
> You are given two integer arrays `nums1` and `nums2`, sorted in non-decreasing order, and two integers `m` and `n`, representing the number of elements in `nums1` and `nums2` respectively. Merge `nums1` and `nums2` into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array `nums1`. To accommodate this, `nums1` has a length of `m + n`, where the first `m` elements denote the elements that should be merged, and the last `n` elements are set to `0` and should be ignored. `nums2` has a length of `n`.
:::warning
- Approach： C++ Introsort.
- Complexity: Time $O((m + n)log(m + n))$; Space $O(1)$.
:::
```cpp
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int i = 0; i < n; ++i){
nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}
};
```
:::success
- Approach： Two pointers.
- Complexity: Time $O(nlog(n))$; Space $O(1)$.
:::
```cpp
class Solution {
public:
void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
int pos = m-- + n-- - 1; // equivalent to int pos = m + n - 1; m--; n--;
while (m >= 0 && n >= 0) {
nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
}
while (n >= 0) { // Needed to copy remaining nums2 elements
nums1[pos--] = nums2[n--];
}
}
};
```
### <font color="#FF0000">76. Minimum Window Substring</font>
> Given two strings `s` and `t` of lengths `m` and `n` respectively, return the minimum window substring of `s` such that every character in `t` (including duplicates) is included in the window. If there is no such substring, return the empty string `""`. The testcases will be generated such that the answer is unique.
:::success
- Approach： Sliding window (two pointers).
- Complexity: Time $O(n)$; Space $O(1)$.
:::
```cpp
string minWindow(string s, string t) {
/* ----- 初始化 ----- */
// 以 ASCII 数量建立 array
vector<bool> valid(128, false); // 存 t 有用到的字符
vector<int> freq(128, 0); // 存 t 字符出现的频率
// 统计 t 中的字符情况。
for (int i = 0; i < t.length(); ++i) {
valid[t[i]] = true;
++freq[t[i]];
}
/* ----- 滑动窗口 ----- */
int count = 0; // 記錄窗口內已滿足 t 的字符數，至多 t.length
int min_l = -1, min_length = -1; // 記錄最小子串的位置和長度
for (int left = 0, right = 0; right < s.length(); ++right) {
/* ----- 先控制右 ptr ----- */
// 若 s[right] 字符不在 t 中，则跳过
if (!valid[s[right]]) {
continue;
}
//
if (--freq[s[right]] >= 0) {
++count;
}
/* ----- 再控制左 ptr ----- */
// sliding window 已包含 t 中全部字符
// 开始缩减 window（右移 l）。
while (count == t.length()) {
// 更新最小子串的位置和長度
// min_length == -1 表示没记录到任何 window
// r - l + 1 表示目前 window 长度
if (min_length == -1 || right - left + 1 < min_length) {
min_l = left;
min_length = right - left + 1;
}
// 把 l 位置的字符移除频 freq，并检查 t 中对应字符是否重新缺失。
if (valid[s[left]] && ++freq[s[left]] > 0) {
--count;
}
++left;
}
}
return min_length == -1 ? "" : s.substr(min_l, min_length);
}
```
### <font color="#FFa500">142. Linked List Cycle II</font>
> Given the `head` of a linked list, return the node where the cycle begins. If there is no cycle, return `null`. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to (0-indexed). It is `-1` if there is no cycle. Note that `pos` is not passed as a parameter. Do not modify the linked list.
:::success
- Approach： [Floyd Cycle Detection Algorithm (two pointers, fast and slow).](https://www.youtube.com/watch?v=wjYnzkAhcNk&t=914s).
每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。
- Complexity: Time $O(n)$; Space $O(1)$.
:::
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// no node or single node
if (!head || !head->next) return nullptr;
// if there's a linked list, let's run the floyd's cycle alg
ListNode *fast = head;
ListNode *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
// bcs even when there's a cycle, it doesnt gaurantee that
// where they meet is the start of the cycle
// from here please refer to NeetCode, Leetcode 287
if (slow == fast) {
slow = head;
while (slow != fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return nullptr;
}
};
```
### <font color="#FFA500">287. Find the Duplicate Number</font>
> Given an array of integers nums containing `n + 1` integers where each integer is in the range `[1, n]` inclusive. There is only one repeated number in `nums`, return this repeated number. You must solve the problem without modifying the array `nums` and using only constant extra space.
:::success
- Approach： [Floyd Cycle Detection Algorithm (two pointers, fast and slow).](https://www.youtube.com/watch?v=wjYnzkAhcNk&t=914s)
同 142，但提醒不要制式化误区——Linked List 不一定要建 ```struct ListNode```，不然你看 ```->next``` 要怎么指？那不是还要再建一个 ```vector<ListNode*>``` 然后再 用 ```->next``` 把它们串起来，岂不找自己麻烦？不如直接用数组的 index 建。
- Complexity: Time $O(n)$; Space $O(1)$.
:::
```cpp
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0];
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
};
```
### <font color="#FFA500">633. Sum of Square Numbers</font>
> Given a non-negative integer `c`, decide whether there're two integers `a` and `b` such that `a^2 + b^2 = c`.
:::danger
- Approach： Two pointers.
- Complexity: Runtime error. Time $O(n)$; Space $O(1)$.
:::
```cpp
class Solution {
public:
bool judgeSquareSum(int c) {
int left = 0;
int right = sqrt(c);
while (right >= left) {
int squareSum = left * left + right * right;
if (squareSum == c) {
return true;
}
else if (squareSum < c) {
left += 1;
}
else{
right -= 1;
}
}
return false;
}
};
```
>[!Caution] Runtime error
> runtime error: signed integer overflow: 829921 + 2146654224 cannot be represented in type 'int'
Simple solution, to solve integer overflow, use larger variables. Replace `int` with `long long`.
:::success
- Approach： Two pointers.
- Complexity: Runtime error. Time $O(n)$; Space $O(1)$.
:::
```cpp
// within while-loop
long long squareSum;
squareSum = (long long) left * left + (long long) right * right;
```
### <font color="#32CD32">680. Valid Palindrome II</font>
> Given a string `s`, return `true` if the `s` can be palindrome after deleting at most one character from it.
:::danger
- Approach： Two pointers.
When encountering different alphabet, pointer jumps to next, `count` adds up, and check if `count` exceeds the limt of modify once at the end.
- Complexity: WA. Time $O(n)$; Space $O(1)$.
:::
```cpp
class Solution {
public:
bool validPalindrome(string s) {
int left = 0;
int right = s.length() - 1;
int count = 0;
while (left < right){ //>
if (s[left] != s[right]){
// --------------------
if (right - left == 1){
return true;
}
if (s[left] == s[right - 1]){
right --;
}
else if (s[left + 1] == s[right]){
left ++;
}
count ++;
// --------------------
}
left ++;
right --;
}
if (count <= 1){
return true;
}
else{
return false;
}
}
};
```
>[!Caution] WA Testcase
> This testcase `s = "abc"` fails the method. Think abput how to effectively limit the program execution time: write a separate function `isPalindrome`.
:::success
- Approach： Two pointers.
- Complexity: Time $O(n)$; Space $O(1)$.
:::
```cpp
class Solution {
public:
bool isPalindrome(const string &s, int left, int right){
while (left < right){
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
bool validPalindrome(string s) {
int left = 0;
int right = s.length() - 1;
int count = 0;
while (left < right){
if (s[left] != s[right]){
// --------------------
return isPalindrome(s, left + 1, right)\
|| isPalindrome(s, left, right - 1);
// --------------------
}
left ++;
right --;
}
return true;
}
};
```
### <font color="#FFA500">524. Longest Word in Dictionary through Deleting</font>
> Given a string `s` and a string array `dictionary`, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
:::warning
- Approach： Two pointers.
First sort the string length long to short, lexigraphical order low to high. Use a for-loop to compare the strings in dictionary one by one. Write the comparison as a private method.
- Complexity: Time $O(n^2)$; Space $O(1)$.
:::
```cpp
class Solution {
private:
bool isSubsequence(const string& s, const string& word) {
int s_ptr = 0, word_ptr = 0;
while (s_ptr < s.size() && word_ptr < word.size()) {
if (s[s_ptr] == word[word_ptr])
word_ptr++;
s_ptr++;
}
return word_ptr == word.size();
}
};
public:
string findLongestWord(string s, vector<string>& dictionary) {
sort(dictionary.begin(), dictionary.end(),
[](const string& a, const string& b) {
if (a.size() == b.size())
// When comparing two strings with '<',
// C++ compares characters one by one from left to right,
// based on their ASCII values.
return a < b;
return a.size() > b.size();
}
);
for (const string& word : dictionary) {
if (isSubsequence(s, word))
return word;
}
return "";
}
```
>[!Warning] Discussion
> Sort wastes too much time. Could we skip it? And is there a better way than comparing elements in dictionary with `s` one by one?
>
> Yes. Index Table + Binary Search.
:::warning
- Approach： Index Table + Binary Search.
- Complexity: Time $O(n log(n))$; Space $O(n)$.
:::
```cpp=
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
vector<vector<int>> next = buildIndexTable(s);
string bestWord = "";
for (const string& word : dictionary) {
if (isSubsequence(s, word, next)) {
if (word.size() > bestWord.size() ||
(word.size() == bestWord.size() && word < bestWord)) {
bestWord = word;
}
}
}
return bestWord;
}
private:
// 这个方法用意是先建立一个 table，我直接查表
vector<vector<int>> buildIndexTable(const string& s) {
// 以 s = "abpcplea" 为例，会建立一个 8 by 26 (alphabets) 的 table, 里面塞满了 8 这个数字
int n = s.size();
vector<vector<int>> next(n + 1, vector<int>(26, n));
for (int i = n - 1; i >= 0; --i) {
// 复制后一行 row 的值到前一行 row
next[i] = next[i + 1];
// 再改特定位置的值——把现在遇到字母的 index 放到现在字母对应的 column
next[i][s[i] - 'a'] = i;
}
// 那现在我们就得到一个 table 长得像这样
// i 代表当前 s 内的 index，每个 column 是一个字母，每个字母下的 row 代表下一次遇到这个字母的位置
/*
| i ( char ) | 'a' | 'b' | 'c' | 'e' | 'l' | 'p' | ... |
|-----------------|-----|-----|-----|-----|-----|-----|-----|
| 0 (s[0] = 'a') | 0 | 1 | 3 | 6 | 5 | 2 | ... |
| 1 (s[0] = 'b') | 7 | 1 | 3 | 6 | 5 | 2 | ... |
| 2 (s[0] = 'p') | 7 | 8 | 3 | 6 | 5 | 2 | ... |
| 3 (s[0] = 'c') | 7 | 8 | 3 | 6 | 5 | 4 | ... |
| 4 (s[0] = 'p') | 7 | 8 | 8 | 6 | 5 | 4 | ... |
| 5 (s[0] = 'l') | 7 | 8 | 8 | 6 | 5 | 8 | ... |
| 6 (s[0] = 'e') | 7 | 8 | 8 | 6 | 8 | 8 | ... |
| 7 (s[0] = 'a') | 7 | 8 | 8 | 8 | 8 | 8 | ... |
| 8 ( boundary ) | 8 | 8 | 8 | 8 | 8 | 8 | ... |
*/
return next;
}
bool isSubsequence(const string& s, const string& word, vector<vector<int>>& next) {
int index = 0;
for (char c : word) {
// c 是 word 里面的字母，c - 'a' 代表这个字母在 next table 中第几个 column
// next[index][c - 'a'] == 8 则代表这字母 c 从 index 之后，不会再出现于 s，
// 既然找不到，则代表 word 不会是 s 的 subsequence
if (next[index][c - 'a'] == s.size()) {
return false;
}
// 将 index 移到已找到的 c 之后一字母
index = next[index][c - 'a'] + 1;
}
return true;
}
};
```
`buildIndexTable()` uses the index table, and the `index = next[index][c - 'a'] + 1` in `isSubsequence()` uses the binary search.
Sign in with Wallet
Connect another wallet