Two Pointers

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Arrays & Hashing と一緒で Two Pointers も比較的とっつきやすい印象です。ただこの辺の分野は概念が簡単な分工夫しやすいのか問題パターンが多岐に渡るそうなのでその点は注意。

10. Valid Palindrome

Problem

Given a string s, return true if it is a palindrome, otherwise return false.

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Example 1:

Input: s = "Was it a car or a cat I saw?"

Output: true

Explanation: After considering only alphanumerical characters we have "wasitacaroracatisaw", which is a palindrome.

Example 2:

Input: s = "tab a cat"

Output: false

Explanation: "tabacat" is not a palindrome.

Constraints:

1 <= s.length <= 1000

s is made up of only printable ASCII characters.

Solution

import re

class Solution:
    def removeNonAlphanumeric(self, text: str) -> str:
        # 正規表現で non-alphanumeric 文字を削除
        return re.sub(r'[^a-zA-Z0-9]', '', text)
    
    def isPalindrome(self, s: str) -> bool:
        # lowerケースのアルファベットと数字だけにする(空白も取り除く)
        removed_nonalpha = self.removeNonAlphanumeric(s)
        low_alpha = ''.join(removed_nonalpha.split()).lower()

        l, r = 0, len(low_alpha) - 1
        while l < r:
            if low_alpha[l] != low_alpha[r]:
                return False
            l += 1
            r -= 1
        
        return True

11. Two Sum II Input Array Is Sorted

Problem

Given an array of integers numbers that is sorted in non-decreasing order.

Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.

There will always be exactly one valid solution.

Your solution must use O(1)

O(1) additional space.

Example 1:

Input: numbers = [1,2,3,4], target = 3

Output: [1,2]

Explanation:

The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1, index2 = 2. We return [1, 2].

Solution

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers)-1

        while l < r:
            total = numbers[l] + numbers[r]
            if total == target:
                return [l+1, r+1]
            elif total < target:
                l += 1
            else:
                r -= 1

12. 3Sum

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.

The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Explanation:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2:

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 1000

-10^5 <= nums[i] <= 10^5

Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()

        res = []
        
        for i in range(len(nums)-2):
            # nums[i]が前回と同じ値になると結果が重複するので
            # そうならないところまでiのポインターを進める
            if i > 0 and nums[i-1] == nums[i]:
                continue
            
            l, r = i+1, len(nums)-1

            while l < r:
                total = nums[i] + nums[l] + nums[r]

                if total == 0:
                    res.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1
                    r -= 1
                elif total < 0:
                    l += 1
                else:
                    r -= 1
        
        return res

13. Container With Most Water

Problem

You are given an integer array heights where heights[i] represents the height of the ith bar.

You may choose any two bars to form a container. Return the maximum amount of water a container can store.

Example 1:

Input: height = [1,7,2,5,4,7,3,6]

Output: 36

Example 2:

Input: height = [2,2,2]

Output: 4

Constraints:

2 <= height.length <= 1000

0 <= height[i] <= 1000

Solution

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        l, r = 0, len(heights) - 1
        max_area = 0

        while l < r:
            width = r - l
            height = 0
            if heights[l] <= heights[r]:
                # 高さが低い方を内側に動かす
                # 同じ高さだった場合はどちらを動かしても結果は変わらない。
                # 仮に動かした方の次のバーが高くても、動かしてない方のバーの高さで
                # 面積は決まるので、動かす前より面積が大きくなることはない
                height = heights[l]
                l += 1
            else:
                height = heights[r]
                r -= 1

            area = height * width
            max_area = max(max_area, area)

        return max_area

14. Trapping Rain Water

Problem

You are given an array non-negative integers heights which represent an elevation map. Each value heights[i] represents the height of a bar, which has a width of 1.

Return the maximum area of water that can be trapped between the bars.

Example 1:

Input: height = [0,2,0,3,1,0,1,3,2,1]

Output: 9

Solution

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height)-1
        left_max = height[l]
        right_max = height[r]
        water = 0

        while l < r:
            if height[l] <= height[r]:
                l += 1
                if height[l] < left_max:
                    water += left_max - height[l]
                else:
                    left_max = height[l]
                    
            else:
                r -= 1
                if height[r] < right_max:
                    water += right_max - height[r]
                else:
                    right_max = height[r]
        
        return water