Two Pointers, Coding Interview Pattern

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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++:

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.