Two Pointers, Coding Interview Pattern
Tags: algorithms, datastructures, coding, interview
Published: 2024-06-14 07:30:01

## Two Pointers

The Two Pointers technique is a fundamental and versatile approach used to solve a wide range of problems in computer science, particularly those involving linear data structures like arrays and linked lists. This comprehensive guide will cover everything you need to know about the Two Pointers technique, from basic concepts to advanced applications.

### Valid Palindrome
`This question is part of Leetcode problems, question no. 125.`

Here's the Solution class for the "Valid Palindrome" problem in C++:

```cpp
class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0;
        int right = s.size() - 1;
        
        while (left < right) {
            while (left < right && !isalnum(s[left])) {
                left++;
            }
            while (left < right && !isalnum(s[right])) {
                right--;
            }
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};
```

### Pair with Target Sum
`This question is part of Leetcode problems, question no. 1.`

Here's the Solution class for the "Pair with Target Sum" problem in C++:

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;
        
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (seen.find(complement) != seen.end()) {
                return { seen[complement], i };
            }
            seen[nums[i]] = i;
        }
        
        return {};
    }
};
```

### Sum of Three Values
`This question is part of Leetcode problems, question no. 15.`

Here's the Solution class for the "Sum of Three Values" problem in C++:

```cpp
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 > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
};
```

### Remove Element
`This question is part of Leetcode problems, question no. 27.`

Here's the Solution class for the "Remove Element" problem in C++:

```cpp
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != val) {
                nums[index++] = nums[i];
            }
        }
        
        return index;
    }
};
```

### Move Zeroes
`This question is part of Leetcode problems, question no. 283.`

Here's the Solution class for the "Move Zeroes" problem in C++:

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

### Remove Nth Node From End of List
`This question is part of Leetcode problems, question no. 19.`

Here's the Solution class for the "Remove Nth Node From End of List" problem in C++:

```cpp
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = dummy;
        ListNode* second = dummy;
        
        for (int i = 1; i <= n + 1; i++) {
            first = first->next;
        }
        
        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }
        
        ListNode* nodeToRemove = second->next;
        second->next = second->next->next;
        delete nodeToRemove;
        
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};
```

### Sort Colors
`This question is part of Leetcode problems, question no. 75.`

Here's the Solution class for the "Sort Colors" problem in C++:

```cpp
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0, mid = 0, high = nums.size() - 1;
        
        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums[low++], nums[mid++]);
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums[mid], nums[high--]);
            }
        }
    }
};
```

### Valid Palindrome II
`This question is part of Leetcode problems, question no. 680.`

Here's the Solution class for the "Valid Palindrome II" problem in C++:

```cpp
class Solution {
public:
    bool validPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
    
    bool isPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};
```

### Remove Duplicates from Sorted Array
`This question is part of Leetcode problems, question no. 26.`

Here's the Solution class for the "Remove Duplicates from Sorted Array" problem in C++:

```cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        
        int j = 0; // index for unique elements
        
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != nums[j]) {
                nums[++j] = nums[i];
            }
        }
        
        return j + 1;
    }
};
```

### Squares of Sorted Array
`This question is part of Leetcode problems, question no. 977.`

Here's the Solution class for the "Squares of Sorted Array" problem in C++:

```cpp
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        
        int left = 0, right = n - 1;
        int idx = n - 1;
        
        while (left <= right) {
            int leftSq = nums[left] * nums[left];
            int rightSq = nums[right] * nums[right];
            
            if (leftSq > rightSq) {
                result[idx--] = leftSq;
                left++;
            } else {
                result[idx--] = rightSq;
                right--;
            }
        }
        
        return result;
    }
};
```

### Backspace String Compare
`This question is part of Leetcode problems, question no. 844.`

Here's the Solution class for the "Backspace String Compare" problem in C++:

```cpp
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return processString(S) == processString(T);
    }
    
    string processString(string s) {
        string result;
        
        for (char c : s) {
            if (c == '#') {
                if (!result.empty()) {
                    result.pop_back();
                }
            } else {
                result.push_back(c);
            }
        }
        
        return result;
    }
};
```

### Minimum Window Sort
`This question is part of Leetcode problems, question no. 581.`

Here's the Solution class for the "Minimum Window Sort" problem in C++:

```cpp
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;
        
        // Find the first out-of-order element from the left
        while (left < n - 1 && nums[left] <= nums[left + 1]) {
            left++;
        }
        
        // Array is already sorted
        if (left == n - 1) {
            return 0;
        }
        
        // Find the first out-of-order element from the right
        while (right > 0 && nums[right] >= nums[right - 1]) {
            right--;
        }
        
        // Find the minimum and maximum values in the unsorted subarray
        int min_unsorted = nums[left], max_unsorted = nums[right];
        for (int i = left; i <= right; i++) {
            min_unsorted = min(min_unsorted, nums[i]);
            max_unsorted = max(max_unsorted, nums[i]);
        }
        
        // Expand the unsorted subarray to include any additional out-of-order elements
        while (left > 0 && nums[left - 1] > min_unsorted) {
            left--;
        }
        while (right < n - 1 && nums[right + 1] < max_unsorted) {
            right++;
        }
        
        return right - left + 1;
    }
};
```

### Remove Duplicates from Sorted Array II
`This question is part of Leetcode problems, question no. 80.`

Here's the Solution class for the "Remove Duplicates (At Most Twice) from Sorted Array" problem in C++:

```cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) {
            return n;
        }
        
        int index = 2; // Start from the third element
        
        for (int i = 2; i < n; ++i) {
            if (nums[i] != nums[index - 2]) {
                nums[index++] = nums[i];
            }
        }
        
        return index;
    }
};
```

### Container With Most Water
`This question is part of Leetcode problems, question no. 11.`

Here's the Solution class for the "Container With Most Water" problem in C++:

```cpp
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int max_area = 0;
        
        while (left < right) {
            int width = right - left;
            int current_height = min(height[left], height[right]);
            int current_area = width * current_height;
            max_area = max(max_area, current_area);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return max_area;
    }
};
```

### Merge Sorted Array
`This question is part of Leetcode problems, question no. 88.`

Here's the Solution class for the "Merge Sorted Array" problem in C++:

```cpp
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 (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
};
```

### Merge Two Sorted Lists
`This question is part of Leetcode problems, question no. 21.`

Here's the Solution class for the "Merge Two Sorted Lists" problem in C++:

```cpp
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;

        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                current->next = l1;
                l1 = l1->next;
            } else {
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }

        if (l1) {
            current->next = l1;
        } else {
            current->next = l2;
        }

        ListNode* mergedHead = dummy->next;
        delete dummy;
        return mergedHead;
    }
};
```

### Trapping Rain Water
`This question is part of Leetcode problems, question no. 42.`

Here's the Solution class for the "Trapping Rain Water" problem in C++:

```cpp
class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        int waterTrapped = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    waterTrapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    waterTrapped += rightMax - height[right];
                }
                right--;
            }
        }
        
        return waterTrapped;
    }
};
```

Practice these questions diligently to enhance your problem-solving skills. Remember, consistent practice is key to mastering these concepts. If you find yourself stuck or in need of further clarification, be sure to check out video references and tutorials to clear up any doubts.