Day 4 of LeetCode

Documenting LeetCode solving.

Q1

125. Valid Palindrome

Easy. Two pointers.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Extra space
        newStr = ""

        for c in s:
            # isalpha() is to check if the character is alpha numerical
            # (A-Z, a-z, 0-9)
            if c.isalpha() or c.isdigit():
                newStr += c.lower()
        # [::-1]: reverse the string
        return newStr == newStr[::-1]

# No extra space
class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

        while l < r:
            while l < r and not self.alphaNum(s[l]):
                l += 1
            while r > l and not self.alphaNum(s[r]):
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1

        return True

    def alphaNum(self, c: str):
        # Use ASCII value
        return (ord('A') <= ord(c) <= ord('Z') or
                ord('a') <= ord(c) <= ord('z') or
                ord('0') <= ord(c) <= ord('9'))

Q2

167. Two Sum II - Input Array Is Sorted

Medium. Two Pointers

The array is sorted, so we can use two pointers.

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

        while l < r:
            currSum = numbers[l] + numbers[r]

            if currSum == target:
                break
            elif currSum < target:
                l += 1
            else:
                r -= 1

        return [l + 1, r + 1]

Q3

15. 3Sum

Medium. Two pointers

Sort first, then it's converted to two sum II.

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

        for i, a in enumerate(nums):
            # If meet duplicate, continue
            if i > 0 and a == nums[i - 1]:
                continue
            # Same concept of two sum II
            l, r = i + 1, len(nums) - 1

            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum < 0:
                    l += 1
                elif threeSum > 0:
                    r -= 1
                else:
                    res.append([a, nums[l], nums[r]])
                    # Only need to update one pointer, because the if
                    # condition will automaticly update the other
                    l += 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1

        return res

Q4

11. Container With Most Water

Medium. Two pointers.

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

        while l < r:
            res = max(res, (r - l) * min(height[l], height[r]))
            # We want to maximize the height, so move to the next one if
            # the current one is smaller
            if height[l] <= height[r]:
                l += 1
            else:
                r -= 1

        return res