1 – Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Solution:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        container = {}

        for i, num in enumerate(nums):
            if target - num in container:
                return [container[target - num], i]
            container[num] = i
        return




2 – Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class ListNode():
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        prev = result = ListNode(None)
        n = 0

        while l1 or l2 or n:
            if l1:
                n += l1.val
                l1 = l1.next

            if l2:
                n += l2.val
                l2 = l2.next

            prev.next = ListNode(n % 10)
            prev = prev.next
            n //= 10

        return result.next




3 – Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Solution:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mapper = {}
        start = 0
        longest = 0

        for i, c in enumerate(s):
            if c in mapper and mapper[c] >= start:
                start = mapper[c] + 1
            else:
                longest = max(longest, i - start + 1)

            mapper[c] = i
        return longest




4 – Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Solution:

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1.extend(nums2)
        nums1 = sorted(nums1)

        if len(nums1) % 2 == 0:
            n = len(nums1) // 2
            return (nums1[n - 1] + nums1[n]) / 2
        else:
            n = (len(nums1) // 2) + 1
            return nums1[n - 1]




5 – Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Solution:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest_str = ''
        n = [len(s) - 1]

        for diff in range(1, len(s)):
            n.append(n[0] + diff)
            n.append(n[0] - diff)

        for i in n:
            if (min(i + 1, 2 * len(s) - 1 - i) <= len(longest_str)):
                break

            if i % 2 == 0:
                left, right = (i // 2) - 1, (i // 2) + 1
            else:
                left, right = i // 2, (i // 2) + 1

            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1

            if right - left - 1 > len(longest_str):
                longest_str = s[left + 1: right]

        return longest_str




6 – ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Solution:

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s

        zigzag = [[] for _ in range(numRows)]
        row = 0
        direction = -1

        for c in s:
            zigzag[row].append(c)
            if row == 0 or row == numRows - 1:
                direction = -direction
            row += direction
        return ''.join([c for r in zigzag for c in r])




7 – Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Solution:

class Solution:
    def reverse(self, x: int) -> int:
        isNegative = x < 0
        x = abs(x)
        reversed = 0        

        while x != 0:
            reversed = reversed * 10 + x % 10
            x //= 10

        if reversed > 2**31 - 1:
            return 0
        else:
            return reversed if not isNegative else -reversed




8 – String to Integer (atoi)

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ‘ ‘ is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Solution:

class Solution:
    def myAtoi(self, str: str) -> int:
        str = str.strip()

        isNegative = False
        if str and str[0] == '-':
            isNegative = True
        if str and (str[0] == '+' or str[0] == '-'):
            str = str[1:]
        if not str:
            return 0

        digits = {i for i in '0123456789'}
        result = 0

        for c in str:
            if c not in digits:
                break
            result = result * 10 + int(c)

        if isNegative:
            result = -result

        result = max(min(result, 2**31 - 1), -2**31)
        return result




9 – Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Solution:

class Solution:
    def isPalindrome(self, x: int) -> bool:
        n = len(str(x)) // 2

        if len(str(x)) % 2 != 0:
            n = len(str(x)) // 2
            return str(x)[:n] == str(x)[:n:-1]
        elif len(str(x)) % 2 == 0:
            return str(x)[:n] == str(x)[n:][::-1]
        else:
            return False




10 – Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for . and *.

. Matches any single character.
* Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Solution:

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        matched = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
        matched[0][0] = True

        for i in range(len(s) + 1):
            for j in range(1, len(p) + 1):
                pattern = p[j - 1]

                if pattern == '.':
                    matched[i][j] = (i != 0 and matched[i - 1][j - 1])
                elif pattern == '*':
                    star = p[j - 2]
                    matched[i][j] = matched[i][j - 2] or (i > 0 and matched[i - 1][j] and 
                                                          (star == s[i - 1] or star == '.'))
                else:
                    matched[i][j] = (i != 0 and matched[i - 1][j - 1] and s[i - 1] == pattern)
        return matched[-1][-1]




11 – Container With Most Water

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Solution:

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        max_area = (right - left) * min(height[right], height[left])

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

            max_area = max(max_area, (right - left) * min(height[right], height[left]))

        return max_area




12 – Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Solution:

class Solution:
    def intToRoman(self, num: int) -> str:
        mappings = [
            (1000, 'M'),
            (900, 'CM'),
            (500, 'D'),
            (400, 'CD'),
            (100, 'C'),
            (90, 'XC'),
            (50, 'L'),
            (40, 'XL'),
            (10, 'X'),
            (9, 'IX'),
            (5, 'V'),
            (4, 'IV'),
            (1, 'I')            
        ]

        roman = []

        for i, val in mappings:
            while num >= i:
                num -= i
                roman.append(val)

        return ''.join(roman)




13 – Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. 
X can be placed before L (50) and C (100) to make 40 and 90. 
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Solution:

class Solution:
    def romanToInt(self, s: str) -> int:
        doubles = {
            'CM': 900,
            'CD': 400,
            'XC': 90,
            'XL': 40,
            'IX': 9,
            'IV': 4
        }

        singles = {
            'M': 1000,
            'D': 500,
            'C': 100,
            'L': 50,
            'X': 10,
            'V': 5,
            'I': 1
        }

        integer = 0
        i = 0

        while i < len(s):
            if i < len(s) - 1 and s[i:i + 2] in doubles:
                integer += doubles[s[i:i + 2]]
                i += 2
            else:
                integer += singles[s[i]]
                i += 1
        return integer




14 – Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Solution:

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''

        strs.sort()
        first_str = strs[0]
        last_str = strs[-1]
        i = 0

        while i < len(first_str) and i < len(last_str) and first_str[i] == last_str[i]:
            i += 1
        return first_str[:i]




15 – 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Solution:

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

        i = 0

        while i < len(nums):
            j = i + 1
            k = len(nums) - 1

            while j < k:
                array_sum = nums[i] + nums[j] + nums[k]

                if array_sum == 0:
                    results.append([nums[i], nums[j], nums[k]])
                    k -= 1

                    while k > j and nums[k] == nums[k + 1]:
                        k -= 1

                    j += 1

                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                elif array_sum > 0:
                    k -= 1
                    while k > j and nums[k] == nums[k + 1]:
                        k -= 1
                else:
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
            i += 1

            while i < len(nums) - 2 and nums[i] == nums[i - 1]:
                i += 1
        return results




16 – 3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Solution:

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        min_dif = 9999999
        nums.sort()
        for i in range(len(nums)-2):
            l = i+1
            r = len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                dif = s - target
                if dif < 0:
                    l += 1
                elif dif > 0:
                    r -= 1
                else:
                    return s   
                if abs(dif) <= abs(min_dif): 
                    min_dif = dif
                    res = s
        return res




17 – Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Solution:

hash_table = {'1':'','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}

class Solution:
    # @param digits, a string
    # @return a string[]
    def _letterCombinations(self, digits):
        if len(digits) == 1:
            ret = []
            for char in hash_table[digits[0]]:
                ret.append(char)
            return ret
        else:
            ret = []
            for char in hash_table[digits[0]]:
                for elt in self._letterCombinations(digits[1:]):
                    ret.append(char+elt)
            return ret

    def letterCombinations(self, digits):
        if not digits:
            return []
        return self._letterCombinations(digits)




18 – 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Solution:

class Solution:
    def fourSum(self, n: List[int], t: int) -> List[List[int]]:
        n.sort()
        if not n: return []
        L, N, S, M = len(n), {j:i for i,j in enumerate(n)}, set(), n[-1]
        for i in range(L-3):
            a = n[i]
            if a + 3*M < t: continue
            if 4*a > t: break
            for j in range(i+1,L-2):
                b = n[j]
                if a + b + 2*M < t: continue
                if a + 3*b > t: break
                for k in range(j+1,L-1):
                    c = n[k]
                    d = t-(a+b+c)
                    if d > M: continue
                    if d < c: break
                    if d in N and N[d] > k: S.add((a,b,c,d))
        return S




19 – Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Solution:

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = fast = head
        head = dummy

        while n > 0:
            fast = fast.next
            n -= 1

        while fast != None:
            fast = fast.next
            dummy = dummy.next

        dummy.next = dummy.next.next

        return head.next




20 – Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Solution:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        braces = {')':'(',']':'[','}':'{'}
        for char in s:
            if char in braces.values():
                stack.append(char)
            elif not stack or stack.pop() != braces[char]:
                return False
        return False if stack else True




21 – Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution:

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack=[]
        while l1:
            stack.append(l1.val)
            l1=l1.next
        while l2:
            stack.append(l2.val)
            l2=l2.next
        stack=sorted(stack)
        dummy=ListNode(-1)
        while stack:
            tem=ListNode(stack.pop())
            tem.next=dummy.next
            dummy=ListNode(-1)
            dummy.next=tem
        return dummy.next




22 – Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution:

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        p = [[] for i in range(n + 1)]
        p[0].append('')
        for i in range(n + 1):
            for j in range(i):
                p[i] += ['(' + x + ')' + y for x in p[j] for y in p[i - j - 1]]
        return p[n]




23 – Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution:

class Solution:
    def mergeKLists(self, lists: 'List[ListNode]') -> 'ListNode':
        nums, dum = [], ListNode(0)
        p = dum
        for l in lists:
            while l:
                nums.append(l)
                l = l.next
        for i in sorted(nums, key = lambda l: l.val):
            p.next = i
            p = p.next
        return dum.next




24 – Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Solution:

class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next: return head
        dummy = ListNode(0)
        dummy.next = head
        cur = dummy

        while cur.next and cur.next.next:
            first = cur.next
            sec = cur.next.next
            cur.next = sec
            first.next = sec.next
            sec.next = first
            cur = cur.next.next
        return dummy.next   




25 – Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Solution:

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        pre, cur = dummy, head
        deque = []
        while cur:
            deque.append(cur)
            cur = cur.next
            if len(deque) == k:
                while deque:
                    pre.next = deque.pop()
                    pre = pre.next
        while deque:
            pre.next = deque.pop(0)
            pre = pre.next
        pre.next = None
        return dummy.next




26 – Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return len(nums)

        j = 0

        for num in nums[1:]:
            if num != nums[j]:
                j += 1
                nums[j] = num
        return j+1




27 – Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Solution:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        x = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[x] = nums[i]
                x += 1
        return x




28 – Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Solution:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        elif needle not in haystack:
            return -1
        else:
            return len(haystack.split(needle)[0])




29 – Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Solution:

class Solution:
    def divide(self, dividend, divisor) -> int:
        positive = (dividend < 0) is (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        while dividend >= divisor:
            temp, i = divisor, 1
            while dividend >= temp:
                dividend -= temp
                res += i
                i <<= 1
                temp <<= 1
        if not positive:
            res = -res
        return min(max(-2147483648, res), 2147483647)




30 – Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Solution:

class Solution:
    # @param S, a string
    # @param L, a list of string
    # @return a list of integer
    def findSubstring(self, S, L):
        if not L or not L[0]: return None
        wl = len(L[0])
        totl = len(L) * wl
        count_tmpl = collections.defaultdict(int)
        for word in L: count_tmpl[word] += 1
        rtn = []
        for i in range(wl):
            count = copy.copy(count_tmpl)
            j = i
            while j < len(S)-wl+1:
                count[S[j:j+wl]] -= 1
                while count[S[j:j+wl]] < 0:
                    count[S[i:i+wl]] += 1
                    i += wl
                j += wl
                if j-i == totl: rtn.append(i)
        return rtn




31 – Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution:

class Solution:
    def nextPermutation(self, nums):
        for i in range(len(nums)-1, -1, -1):
            if i-1 >=0 and nums[i] > nums[i-1]:
                for j in reversed(range(i,len(nums))):
                    if nums[j] > nums[i-1]:
                        nums[i-1], nums[j] = nums[j], nums[i-1]
                        break
                nums[i:] = nums[i:][::-1]
                break
        else:
            nums = nums.reverse()




32 – Longest Valid Parentheses

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Solution:

class Solution:
    def longestValidParentheses(self, s):
        stack, result = [(-1, ')')], 0
        for i, paren in enumerate(s):
            if paren == ')' and stack[-1][1] == '(':
                stack.pop()
                result = max(result, i - stack[-1][0])
            else:
                stack += (i, paren),
        return result




33 – Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Solution:

class Solution:
    def search(self, nums, target):
        l, r = 0, len(nums)-1
        while l <= r:
            mid = l + (r-l)//2
            if nums[mid] == target:
                return mid
            if nums[l] <= nums[mid]:  # here should include "==" case
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1




34 – Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Solution:

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if target not in nums:
            return [-1,-1]
        l=0
        r=len(nums)-1

        while l<=r and l<len(nums)-1 and r>0:
            if nums[l]!=target:
                l+=1
            if nums[r]!=target:
                r-=1
            if nums[l]==target and nums[r]==target:
                break
        if nums[l]==target:
            return [l,r]
        else:
            return [-1,-1]




35 – Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Solution:

class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        for i in range(len(nums)):
            if target <= nums[i]:
                return i
        return len(nums)




36 – Valid Sudoku

Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Solution:

class Solution:
    def isValidSudoku(self, board) -> bool:
        row = [[x for x in y if x != '.'] for y in board]
        col = [[x for x in y if x != '.'] for y in zip(*board)]
        pal = [[board[i+m][j+n] 
            for m in range(3) 
                for n in range(3) if board[i+m][j+n] != '.'] 
                    for i in (0, 3, 6) for j in (0, 3, 6)]

        return all(len(set(x)) == len(x) for x in (*row, *col, *pal))




37 – Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character ‘.’.

Solution:

class Solution:
    col_size = 9  # len(self.board)
    row_size = 9  # len(self.board[0])
    block_col_size = 3
    block_row_size = 3
    digits = '123456789'
    empty_symbol = '.'

    # def solveSudoku(self, board: List[List[str]]) -> None:
    def solveSudoku(self, board):
        self.init(board)
        self.solve()

    def init(self, board):
        self.board = board

        # list all empty cells. a `cell` is a tuple `(row_index, col_index)`
        self.empty_cells = set([(ri, ci) for ri in range(self.row_size) for ci in range(self.col_size) if self.board[ri][ci] == self.empty_symbol])

        # find candidates of each cell
        self.candidates = [[set(self.digits) for ci in range(self.col_size)] for ri in range(self.row_size)]
        for ri in range(self.row_size):
            for ci in range(self.col_size):
                digit = self.board[ri][ci]
                if digit != self.empty_symbol:
                    self.candidates[ri][ci] = set()
                    self.update_candidates((ri, ci), digit)

    def solve(self):
        # if there are no empty cells, it's solved
        if not self.empty_cells:
            return True

        # get the cell with fewest candidates
        cell = min(self.empty_cells, key=lambda cell: len(self.candidates[cell[0]][cell[1]]))

        # try filling the cell with one of the candidates, and solve recursively
        ri, ci = cell
        for digit in list(self.candidates[ri][ci]):
            candidate_updated_cells = self.fill_cell(cell, digit)
            solved = self.solve()
            if solved:
                return True
            self.unfill_cell(cell, digit, candidate_updated_cells)

        # if no solution found, go back and try the next candidates
        return False

    def fill_cell(self, cell, digit):
        # fill the cell with the digit
        ri, ci = cell
        self.board[ri][ci] = digit

        # remove the cell from empty_cells
        self.empty_cells.remove(cell)

        # update the candidates of other cells
        # keep a list of updated cells. will be used when unfilling cells
        candidate_updated_cells = self.update_candidates(cell, digit)

        return candidate_updated_cells

    def unfill_cell(self, cell, digit, candidate_updated_cells):
        # unfill cell
        ri, ci = cell
        self.board[ri][ci] = self.empty_symbol

        # add the cell back to empty_cells
        self.empty_cells.add(cell)

        # add back candidates of other cells
        for ri, ci in candidate_updated_cells:
            self.candidates[ri][ci].add(digit)

    def update_candidates(self, filled_cell, digit):
        candidate_updated_cells = []
        for ri, ci in self.related_cells(filled_cell):
            if (self.board[ri][ci] == self.empty_symbol) and (digit in self.candidates[ri][ci]):
                self.candidates[ri][ci].remove(digit)
                candidate_updated_cells.append((ri, ci))
        return candidate_updated_cells

    def related_cells(self, cell):
        return list(set(self.cells_in_same_row(cell) + self.cells_in_same_col(cell) + self.cells_in_same_block(cell)))

    def cells_in_same_row(self, cell):
        return [(cell[0], ci) for ci in range(self.col_size)]

    def cells_in_same_col(self, cell):
        return [(ri, cell[1]) for ri in range(self.row_size)]

    def cells_in_same_block(self, cell):
        block_first_cell_ri = (cell[0] // self.block_row_size) * self.block_row_size
        block_first_cell_ci = (cell[1] // self.block_col_size) * self.block_col_size
        return [
            (block_first_cell_ri + in_block_ri, block_first_cell_ci + in_block_ci)
            for in_block_ri in range(self.block_row_size)
            for in_block_ci in range(self.block_col_size)
        ]




38 – Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Solution:

class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        s = '1'
        for i in range(n-1):
            count = 1
            temp = []
            for index in range(1, len(s)):
                if s[index] == s[index-1]:
                    count += 1
                else:
                    temp.append(str(count))
                    temp.append(s[index-1])
                    count = 1
            temp.append(str(count))
            temp.append(s[-1])
            s = ''.join(temp)
        return s




39 – Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Solution:

class Solution:
    def combinationSum(self, candidates, target: int):
        def backtrack(candidates, nums, rem):
            print(nums)
            if rem == 0:
                result.append(nums)
            for i, cand in enumerate(candidates):
                if rem >= cand:
                    backtrack(candidates[i:], nums+[cand], rem-cand)

        candidates.sort()
        result = []
        backtrack(candidates, [], target)
        return result




40 – Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Solution:

class Solution:
    def combinationSum2(self, candidates, target):
            candidates.sort()
            ans = []
            l = len(candidates)

            def combinationSum(i, t, res):
                if t == 0:
                    ans.append(list(res))
                    return

                for j in range(i, l):
                    v = candidates[j]
                    if j > i and v == candidates[j - 1]:
                        continue
                    if t < v:
                        break

                    res.append(v)
                    combinationSum(j + 1, t - v, res)
                    res.pop()
            combinationSum(0, target, [])
            return ans




41 – First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Solution:

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0: nums[i] = len(nums)+1
        for i in range(n):
            if abs(nums[i]) <= n: nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1])
        for i in range(n):
            if nums[i] > 0: return i+1
        return n+1




42 – 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 is able to trap after raining.

Solution:

class Solution:
    def trap(self, height):
        left = 0
        right = len(height) - 1
        left_max = right_max = water = 0
        while left <= right:
            if left_max <= right_max:
                left_max = max(left_max, height[left])
                water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1

        return water




43 – Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Solution:

class Solution:
    def multiply(self, num1, num2):
        res = 0
        carry1 = 1
        for n1 in num1[::-1]:
            carry2 = 1
            for n2 in num2[::-1]:
                res += int(n1)*int(n2)*carry1*carry2
                carry2 *= 10
            carry1 *= 10
        return str(res)




44 – Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ? and *.

? Matches any single character.
* Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Solution:

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        res = [[None for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
        res[0][0] = True
        for i in range(1, len(p) + 1):
            if p[i - 1] == '*':
                res[0][i] = res[0][i - 1]
            else:
                res[0][i] = False
        for i in range(1, len(s) + 1):
            res[i][0] = False
        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]:
                    res[i][j] = res[i - 1][j - 1]
                elif p[j - 1] == '*':
                    res[i][j] = res[i - 1][j] or res[i][j - 1]
                else:
                    res[i][j] = False
        return res[len(s)][len(p)]




45 – Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Solution:

class Solution:
    def jump(self, n) -> int:
        N, t, s, f, F = [i+j for i,j in enumerate(n)], len(n) - 1, 0, 0, []
        for i in range(max(N)+1):
            while 1:
                if N[f] >= i:
                    F.append(f)
                    break
                else: f += 1
        while t != 0: t, s = F[t], s + 1
        return s




46 – Permutations

Given a collection of distinct integers, return all possible permutations.

Solution:

class Solution:
    def permute(self, nums):
        ans = [nums]
        for i in range(1, len(nums)):
            m = len(ans)
            for k in range(m):
                for j in range(i):
                    ans.append(ans[k][:])
                    ans[-1][j], ans[-1][i] = ans[-1][i], ans[-1][j]
        return ans




47 – Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Solution:

class Solution:
    def permuteUnique(self, nums):
        perms = [[]]
        for n in nums:
            perms = [p[:i] + [n] + p[i:]
                     for p in perms
                     for i in range((p + [n]).index(n) + 1)]
        return perms




48 – Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Solution:

class Solution:
    def rotate(self, A):
        A[:] = [[row[i] for row in A[::-1]] for i in range(len(A[0]))]




49 – Group Anagrams

Given an array of strings, group anagrams together.

Solution:

class Solution:
    def groupAnagrams(self, strs):
        dic = {}
        for item in sorted(strs):
            sortedItem = ''.join(sorted(item))
            dic[sortedItem] = dic.get(sortedItem, []) + [item]
        return dic.values()




50 – Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (xn).

Solution:

class Solution:
    def myPow(self, x, n):
        if n < 0:
            x = 1 / x
            n = -n
        pow = 1
        while n:
            if n & 1:
                pow *= x
            x *= x
            n >>= 1
        return pow