Two Pointers, Coding Interview Pattern

Harsh Mishra - Jun 14 - - Dev Community

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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 {};
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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--]);
            }
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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--];
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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.

Image
Choosing Between Single Oven Gas and Electric Ovens
Image
Make accessibility a default: Practical tips for Front-End developers

frontend, a11y, testing, tips
Image
Teknik Dapatkan Situs Judi Online Yang Aman
Image
The Latest Advancements in Computer Vision Technology: Transforming Industries with AI
Image
My minimal VS Code setup for Vue, Typescript, Tailwind CSS, etc

vscode, webdev, tutorial, productivity
Image
GitOps: A Strategic Advantage for Automation, Collaboration, and Cost Savings

git, gitops, devops, learning
Image
20 Quotes That Will Help You Understand Replace Bifold Doors
Image
SAAS - retour - widget

webdev, saas, javascript, startup
Image
Single Electric Fan Oven From CDA
Image
If You've Just Purchased Accident Lawyer ... Now What?
Image
How to write GraphQL resolvers effectively

graphql, codegen, node, server
Image
Utamanya Management Waktu Dalam Taruhan Judi Online
Image
The History Of Bifold Repairs Near Me In 10 Milestones
Image
Primbon Jawa Dalam Taruhan Sabung Ayam Online
Image
The Best Place To Research Asbestos Lawsuit Online
Image
The Power of Personalization: Tailoring Digital Marketing for Healthcare
Image
Zatrzymaj Hałas: Skuteczne Metody Wyciszania Mieszkań
Image
Single Electric Fan Oven From CDA
Image
Rails Designer v1.8: Ready for Rails 8 🫶

rails, ruby, tailwindcss, hotwire
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .