leetcode solutions

leetcode.py

import string
import collections
from typing import List


# https://leetcode.com/problems/rotate-array/
def rotate(nums: List[int], k: int) -> None:
    k = k % len(nums)
    nums[:] = nums[-k:] + nums[:-k]
    return nums


assert rotate([1, 2, 3, 4, 5, 6, 7], 3) == [5, 6, 7, 1, 2, 3, 4]
assert rotate([-1, -100, 3, 99], 2) == [3, 99, -1, -100]


# https://leetcode.com/problems/reverse-words-in-a-string/
def reverseWords(s: str) -> str:
    return " ".join(reversed(s.split()))


assert reverseWords("the sky is blue") == "blue is sky the"
assert reverseWords("  hello world  ") == "world hello"
assert reverseWords("a good   example") == "example good a"


# https://leetcode.com/problems/evaluate-reverse-polish-notation/
def evalRPN(tokens: List[str]) -> int:
    stack = []
    for t in tokens:
        if t not in "+-*/":
            stack.append(int(t))
        else:
            right, left = stack.pop(), stack.pop()
            if t == "+":
                stack.append(left + right)
            elif t == "-":
                stack.append(left - right)
            elif t == "*":
                stack.append(left * right)
            else:
                stack.append(int(left / right))
    return stack.pop()


assert evalRPN(["2", "1", "+", "3", "*"]) == 9


# https://leetcode.com/problems/word-ladder/
def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
    queue = collections.deque([(beginWord, 1)])
    visited = set(beginWord)
    wordSet = set(wordList)
    while queue:
        word, dist = queue.popleft()
        if word == endWord:
            return dist
        for i in range(len(word)):
            for j in string.ascii_lowercase:
                tmp = word[:i] + j + word[i + 1 :]
                if tmp not in visited and tmp in wordSet:
                    queue.append((tmp, dist + 1))
                    visited.add(tmp)
    return 0


assert ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) == 5
assert ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == 0


# https://leetcode.com/problems/word-ladder-ii/
def findLadders(beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
    wordList = set(wordList)
    res = []
    layer = {}
    layer[beginWord] = [[beginWord]]

    while layer:
        newlayer = collections.defaultdict(list)
        for w in layer:
            if w == endWord:
                res.extend(k for k in layer[w])
            else:
                for i in range(len(w)):
                    for c in "abcdefghijklmnopqrstuvwxyz":
                        neww = w[:i] + c + w[i + 1 :]
                        if neww in wordList:
                            newlayer[neww] += [j + [neww] for j in layer[w]]

        wordList -= set(newlayer.keys())
        layer = newlayer

    return res


assert findLadders("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) == [
    ["hit", "hot", "dot", "dog", "cog"],
    ["hit", "hot", "lot", "log", "cog"],
]
assert findLadders("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == []


# https://leetcode.com/problems/kth-largest-element-in-an-array/
def findKthLargest(nums: List[int], k: int) -> int:
    return sorted(nums)[-k]


assert findKthLargest([3, 2, 1, 5, 6, 4], 2) == 5
assert findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4


# https://leetcode.com/problems/wildcard-matching/
def isMatch(s: str, p: str) -> bool:
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[0][0] = True
    for i in range(1, len(p) + 1):
        if p[i - 1] == "*":
            dp[0][i] = dp[0][i - 1]
    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            if p[j - 1] == "?" or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == "*":
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
    return dp[-1][-1]


assert isMatch("aa", "a") is False
assert isMatch("aa", "*") is True
assert isMatch("cb", "?a") is False


# https://leetcode.com/problems/merge-intervals/
def merge(intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    merged = [intervals[0]]
    for (current_start, current_end) in intervals[1::]:
        previous_end = merged[-1][1]
        if previous_end >= current_start:
            merged[-1][1] = max(previous_end, current_end)
        else:
            merged.append([current_start, current_end])
    return merged


assert merge([[1, 3], [2, 6], [8, 10], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]
assert merge([[1, 4], [4, 5]]) == [[1, 5]]


# https://leetcode.com/problems/insert-interval/
def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    return merge(intervals + [newInterval])


assert insert([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]]
assert insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) == [[1, 2], [3, 10], [12, 16]]


# https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
def twoSum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        if numbers[left] + numbers[right] == target:
            return [left + 1, right + 1]
        elif numbers[left] + numbers[right] < target:
            left += 1
        else:
            right -= 1
    return []


assert twoSum([2, 7, 11, 15], 9) == [1, 2]
assert twoSum([2, 3, 4], 6) == [1, 3]
assert twoSum([-1, 0], -1) == [1, 2]


# https://leetcode.com/problems/3sum/
def threeSum(nums: List[int]) -> List[List[int]]:
    res = []
    nums.sort()
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                res.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
    return res


assert threeSum([-1, 0, 1, 2, -1, -4]) == [(-1, -1, 2), (-1, 0, 1)]
assert threeSum([]) == []
assert threeSum([0]) == []


# https://leetcode.com/problems/subsets/
def subsets(nums: List[int]) -> List[List[int]]:
    result = [[]]
    for num in nums:
        result += [i + [num] for i in result]
    return result


assert subsets([1, 2, 3]) == [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
assert subsets([0]) == [[], [0]]


# https://leetcode.com/problems/group-anagrams/
def groupAnagrams(strs: List[str]) -> List[List[str]]:
    d = collections.defaultdict(list)
    for s in strs:
        d[tuple(sorted(s))].append(s)
    return list(d.values())


assert groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) == [
    ["eat", "tea", "ate"],
    ["tan", "nat"],
    ["bat"],
]
assert groupAnagrams([""]) == [[""]]
assert groupAnagrams(["a"]) == [["a"]]


# https://leetcode.com/problems/container-with-most-water/
def maxArea(height: List[int]) -> int:
    left, right, max_area = 0, len(height) - 1, 0
    while left < right:
        max_area = max(max_area, min(height[left], height[right]) * (right - left))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area


assert maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert maxArea([1, 1]) == 1


# https://leetcode.com/problems/letter-combinations-of-a-phone-number/
def letterCombinations(digits: str) -> List[str]:
    if not digits:
        return []
    mapping = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }
    res = [""]
    for i in digits:
        res = [c + d for c in res for d in mapping[i]]
    return res


assert letterCombinations("23") == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
assert letterCombinations("") == []
assert letterCombinations("2") == ["a", "b", "c"]


# https://leetcode.com/problems/valid-sudoku/
def isValidSudoku(board: List[List[str]]) -> bool:
    boardMap = collections.defaultdict(list)
    for x in range(9):
        for y in range(9):
            char = board[x][y]
            if char != ".":
                if char in boardMap:
                    for pos in boardMap[char]:
                        if (
                            (pos[0] == x)
                            or (pos[1] == y)
                            or (pos[0] // 3 == x // 3 and pos[1] // 3 == y // 3)
                        ):
                            return False
                boardMap[char].append((x, y))
    return True


assert (
    isValidSudoku(
        [
            ["5", "3", ".", ".", "7", ".", ".", ".", "."],
            ["6", ".", ".", "1", "9", "5", ".", ".", "."],
            [".", "9", "8", ".", ".", ".", ".", "6", "."],
            ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
            ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
            ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
            [".", "6", ".", ".", ".", ".", "2", "8", "."],
            [".", ".", ".", "4", "1", "9", ".", ".", "5"],
            [".", ".", ".", ".", "8", ".", ".", "7", "9"],
        ]
    )
    is True
)
assert (
    isValidSudoku(
        [
            ["8", "3", ".", ".", "7", ".", ".", ".", "."],
            ["6", ".", ".", "1", "9", "5", ".", ".", "."],
            [".", "9", "8", ".", ".", ".", ".", "6", "."],
            ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
            ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
            ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
            [".", "6", ".", ".", ".", ".", "2", "8", "."],
            [".", ".", ".", "4", "1", "9", ".", ".", "5"],
            [".", ".", ".", ".", "8", ".", ".", "7", "9"],
        ]
    )
    is False
)


# https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
def maxProfit(prices: List[int]) -> int:
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit


assert maxProfit([7, 1, 5, 3, 6, 4]) == 7
assert maxProfit([1, 2, 3, 4, 5]) == 4
assert maxProfit([7, 6, 4, 3, 1]) == 0


# https://leetcode.com/problems/gas-station/
def canCompleteCircuit(gas: List[int], cost: List[int]) -> int:
    if sum(gas) < sum(cost):
        return -1
    start, tank = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start


assert canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3
assert canCompleteCircuit([2, 3, 4], [3, 4, 3]) == -1