Welcome to Two Pointer CodeSnap

The 'Two-Pointer Technique' is an efficient algorithmic pattern primarily used on sorted arrays or linked lists. It involves using two index pointers that typically traverse the data structure from opposite ends, or sometimes in the same direction at different speeds. This technique excels at problems requiring finding pairs or subsequences that satisfy certain conditions, optimizing comparisons, and reducing time complexity, often from O(n^2) to O(n). Common applications include searching for pairs with a specific sum, palindrome checking, finding subarrays, and calculating container areas.

Table of Contents

• Valid Palindrome

  Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Use two pointers moving from the ends towards the center.

• Two Sum II – Input Array Is Sorted

  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. Use two pointers, one starting from the beginning and one from the end.

• Container With Most Water

  Given an integer array `height` of length `n`, find two lines that together with the x-axis form a container, such that the container contains the most water. Use two pointers starting at both ends and move the pointer pointing to the shorter line inwards.

• 3Sum

  Given an integer array `nums`, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`. The solution set must not contain duplicate triplets. Typically involves sorting and then using a two-pointer approach within a loop.

• Trapping Rain Water

  Given `n` non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Can be solved efficiently using two pointers maintaining left and right maximum heights.