pattern_two_pointer.py

"""
Two pointers = sorted array/string + find a pair + O(1) space constraint
Whenever you see those 3 signals together, reach for two pointers before a hashmap.

Signal in problem                                   Think
--------------------------------------------------------------------------
Sorted array + find pair + O(1) space               Two pointers
Find max/min area or distance b/w elements end      Two pointers from both Bottleneck logic (min of two things)                Move the shorter pointer
"""

"""
Given a sorted array of integers and a target sum,
return the indices (1-indexed) of the two numbers
that add up to the target.

Example:
Input:  numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]   (because 2 + 7 = 9)

Constraints:
- Exactly one solution exists
- Cannot use the same element twice
- Must use O(1) extra space
"""


def two_sum(nums, target):
    """
    TC: O(n)
    Space: O(1)
    """
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left+1, right+1]  # 1- indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]


"""
Problem 2: Given an array height[] where height[i] is the height
of a vertical line at position i, find two lines that
together with the x-axis forms a container that holds
the most water.

Example:
Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49

Water = min(height[left], height[right]) × (right - left)
"""


def max_water(height):
    # Time: O(n) — one pass
    # Space: O(1) — no extra storage

    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        h = min(height[left], height[right])
        width = right-left
        max_area = max(max_area, h * width)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area


"""
3Sum — find all unique triplets that sum to zero
Fix one number with a loop. On the remaining subarray (which you sort), run two pointers to find a pair that sums to -fixed. This turns an O(n³) brute force into O(n²).

sorted → [-4, -1, -1, 0, 1, 2]
Result: [[-1,-1,2], [-1,0,1]]
"""


def three_sums(nums):
    nums.sort()
    result = []

    for i in range(len(nums)-2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # skiped duplicate fixed value
        left, right = i+1, len(nums)-1
        while left < right:
            s = nums[i]+nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result


"""
Remove duplicates from sorted array — in-place
i/p : [1, 1, 2, 3, 3, 4]
o/p : 4
"""


def remove_duplicates(nums):
    # Time O(n) · Space O(1)
    if not nums:
        return 0
    slow = 1
    for fast in range(1, len(nums)):
        if nums[fast] != nums[fast-1]:
            nums[slow] = nums[fast]
            slow += 1
    # print(nums[:slow]) # For removed List
    return slow


"""
Valid palindrome — ignoring non-alphanumeric chars
 "A man, a plan, a canal: Panama"

cleaned thinking: "amanaplanacanalpanama"

L=0(A) R=last(a) → match (case-insensitive) → L++ R--
L=1(m) R=prev(m) → match → L++ R--
... (skip commas and spaces as we go)
... all chars match
L >= R → return True ✓

"""


def is_palindrome(s):
    # Time O(n) · Space O(1)

    left, right = 0, len(s) - 1

    while left < right:
        # skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        # skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True


"""
Trapping rain water — hardest two pointer problem

Water at any position = min(max_left, max_right) - height[i]. Instead of precomputing both arrays, use two pointers: whichever side has the smaller max determines the water at that position — process it and move inward.

Dry run — [0, 1, 0, 2, 1, 0, 1, 3, 1, 0, 1, 2]
left=0 right=11, max_L=0 max_R=0, water=0

height[L]=0, height[R]=2
max_L=0, max_R=2 → max_L < max_R → process left
  water += max(0, max_L - height[L]) = 0 → L++

L=1(h=1): max_L=1, max_R=2 → process left
  water += max(0, 1-1)=0 → L++

L=2(h=0): max_L=1, max_R=2 → process left
  water += max(0, 1-0)=1 → L++ [total=1]

L=3(h=2): max_L=2 → water+=max(0,2-2)=0 → L++
...continue until L>=R

Final water trapped = 6
"""


def trap(height):
    left, right = 0, len(height) - 1
    max_left = max_right = water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= max_left:
                max_left = height[left]
            else:
                water += max_left - height[left]
            left += 1
        else:
            if height[right] >= max_right:
                max_right = height[right]
            else:
                water += max_right - height[right]
            right -= 1

    return water


if __name__ == "__main__":
    assert (max_water([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49)
    assert (three_sums([-4, -1, -1, 0, 1, 2]) == [[-1, -1, 2], [-1, 0, 1]])
    assert (remove_duplicates([1, 1, 2, 3, 3, 4]) == 4)
    assert (is_palindrome("A man, a plan, a canal: Panama") == True)
    assert (is_palindrome("amanaplanacanalpanama") == True)
    assert (trap([0, 1, 0, 2, 1, 0, 1, 3, 1, 0, 1, 2]) == 6)