<jupyter_start><jupyter_text>Day 1 Binary Search<jupyter_code># Binary Search (Easy)

nums = [-1,0,3,5,9,12]
target = 9

class Solution:
    def search(self, nums, target: int) -> int:
        start, end = 0, len(nums)
        while start != end:
            mid = (start + end)//2
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                end = mid
            else:
                start = mid + 1
        return -1

Solution().search(nums, target)
# First Bad Version (Easy)

n = 5
bad = 4

# API bool isBadVersion(version)
def isBadVersion(ver):
    return False if ver < bad else True

class Solution:
    def firstBadVersion(self, n):
        start, end = 1, n
        while start != end:
            mid = (start + end)//2
            if isBadVersion(mid):
                end = mid
            else:
                start = mid + 1
        return start

Solution().firstBadVersion(n)
# Search Insert Position (Easy)

nums = [1,3,5,6]
target = 4

class Solution:
    def searchInsert(self, nums, target: int) -> int:
        start, end = 0, len(nums)
        while start != end:
            mid = (start + end)//2
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                end = mid
            else:
                start = mid + 1
        return start

Solution().searchInsert(nums, target)<jupyter_output><empty_output><jupyter_text>Day 2 Two Pointers<jupyter_code># Squares of a Sorted Array (Easy)

class Solution:
    def sortedSquares(self, nums):
        """
        Tim Sort w/ O(nlogn)
        :param nums: list[int]
        :return: list[int]
        """
        return sorted([num*num for num in nums])

    def sortedSquares2(self, nums):
        """
        O(n)
        :param nums: list[int]
        :return: list[int]
        """
        left, right = 0, len(nums)-1
        squares = [0]*len(nums)
        cur = len(squares)-1

        while cur >= 0:
            if left == right:
                squares[0] = nums[left]**2
                break
            if abs(nums[left]) > abs(nums[right]):
                squares[cur] = nums[left]**2
                cur -= 1
                left += 1
            elif abs(nums[left]) < abs(nums[right]):
                squares[cur] = nums[right]**2
                cur -= 1
                right -= 1
            else:
                squares[cur-1:cur+1] = [nums[left]**2]*2
                left += 1
                right -= 1
                cur -= 2
        return squares

Testing().test(Solution().sortedSquares([-4,-1,0,3,10]),[0,1,9,16,100])
Testing().test(Solution().sortedSquares([-7,-3,2,3,11]),[4,9,9,49,121])
Testing().test(Solution().sortedSquares2([-4,-1,0,3,10]),[0,1,9,16,100])
Testing().test(Solution().sortedSquares2([-7,-3,2,3,11]),[4,9,9,49,121])
# Rotate Array (Medium)

class Solution:
    def rotate(self, nums, k) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        step = k % len(nums)
        if step:
            nums[:] = nums[-step:] + nums[0:len(nums)-step]

nums = [1,2,3,4,5,6,7]
Solution().rotate(nums, 3)
Testing().test(nums,[5,6,7,1,2,3,4])<jupyter_output><empty_output><jupyter_text>Day 3 Two Pointers<jupyter_code># Move Zeroes (Easy)

class Solution:
    def moveZeroes(self, nums) -> None:
        """
        Time: O(n)
        Space: O(1)
        Solve: 20m

        Do not return anything, modify nums in-place instead.
        """
        # for i, num in enumerate(nums):
        #     print("start", nums)
        #     if not num:
        #         nums.append(nums.pop(i))
        #     print("end  ", nums)

        n, i = len(nums), 0
        for _ in range(n):
            if nums[i]:
                i += 1
            else:
                nums.append(nums.pop(i))

nums = [0,1,0,3,12]
Solution().moveZeroes(nums)
Testing().test(nums,[1,3,12,0,0])

nums = [0]
Solution().moveZeroes(nums)
Testing().test(nums,[0])

nums = [1]
Solution().moveZeroes(nums)
Testing().test(nums,[1])
# Two Sum II - Input Array Is Sorted (Easy)

class Solution:
    def twoSum(self, numbers, target):
        """
        Hash
        Time: O(n)
        Space: O(n)
        Solve: 8m
        """
        comps = {}
        for i, num in enumerate(numbers):
            comp = target - num
            if comp in comps:
                return sorted([i+1, comps[comp]+1])
            comps[num] = i

    def twoSum2(self, numbers, target):
        """
        2 Pointers
        Time: O(n)
        Space: O(1)
        Solve:
        """
        l, r = 0, len(numbers)-1
        while l < r:
            add = numbers[l] + numbers[r]
            if add == target:
                return [l+1, r+1]
            elif add > target:
                r -= 1
            else:
                l += 1

Testing().test(Solution().twoSum2([2,7,11,15], 9),[1,2])
Testing().test(Solution().twoSum2([2,3,4], 6),[1,3])
Testing().test(Solution().twoSum2([-1,0], -1),[1,2])<jupyter_output><empty_output><jupyter_text>Day 4 Two Pointers<jupyter_code># Reverse String (Easy)

class Solution:
    def reverseString(self, s) -> None:
        """
        Time: O(n)
        Space: O(1)
        Solve: 5m
        Do not return anything, modify s in-place instead.
        """
        s[:] = reversed(s)

    def reverseString(self, s) -> None:
        """
        Two pointers
        Time: O(n/2)
        Space: O(1)
        Solve: 4m
        """
        l, r = 0, len(s)-1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

s = ["h","e","l","l","o"]
Solution().reverseString(s)
Testing().test(s,["o","l","l","e","h"])
# Reverse Words in a String III

class Solution:
    def reverseWords(self, s: str) -> str:
        """
        Time:
        Space:
        Solve: 23m
        """
        word = sentence = ""
        for i, char in enumerate(s):
            if char != " ":
                word += char
            else:
                sentence = sentence + word[::-1] + " "
                word = ""
            if i == len(s)-1:
                sentence = sentence + word[::-1]
        return sentence
    def reverseWords2(self, s: str) -> str:
        """
        built-in
        Time:
        Space:
        Solve: 5m
        """
        return ' '.join(s.split()[::-1])[::-1]

Testing().test(Solution().reverseWords2("Let's take LeetCode contest"),"s'teL ekat edoCteeL tsetnoc")
Testing().test(Solution().reverseWords2("God Ding"),"doG gniD")<jupyter_output><empty_output><jupyter_text>Day 5 Two Pointers<jupyter_code># Middle of the Linked list (Easy)

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

class Solution:
    def middleNode(self, head):
        """
        Time: O(N)
        Space: O(1)
        Solve:
        """
        curr_node = mid_node = head
        while curr_node and curr_node.next:
            mid_node = mid_node.next
            curr_node = curr_node.next.next
        return mid_node

a = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
Solution().middleNode(a)
# Remove Nth Node From End of List (Medium)

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

class Solution:
    def removeNthFromEnd(self, head, n: int):
        """
        Time:
        Space:
        Solve:
        """
        slow = fast = head
        for _ in range(n):
            fast = fast.next
        if not fast:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

a = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
node = Solution().removeNthFromEnd(a, 2)
while node:
    print(node.val)
    node = node.next<jupyter_output>1
2
3
5<jupyter_text>Day 6 Sliding Window<jupyter_code># Longest Substring Without Repeating Characters (Medium)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        Time: O(N)
        Space: O(N)
        Solve: 20m
        """
        anchor = max_len = 0
        char_pos = {}
        for idx, char in enumerate(s):
            if char in char_pos:
                anchor = max(anchor, char_pos[char] + 1)
            char_pos[char] = idx
            max_len = max(max_len, len(s[anchor:idx+1]))
        return max_len

Testing().test(Solution().lengthOfLongestSubstring(""),0)
Testing().test(Solution().lengthOfLongestSubstring("abba"),2)
Testing().test(Solution().lengthOfLongestSubstring("abcabcbb"),3)
Testing().test(Solution().lengthOfLongestSubstring("bbbbb"),1)
Testing().test(Solution().lengthOfLongestSubstring("pwwkew"),3)
# Permutation in String (Medium)

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        """
        Time:
        Space:
        Solve: 26m
        """
        s1_sig = self.convertSignature(s1)
        s1_len = len(s1)
        for idx in range(len(s2) - s1_len + 1):
            sub_s2 = s2[idx: idx + s1_len]
            if s1_sig in self.convertSignature(sub_s2):
                return True
        return False

    def convertSignature(self, s):
        return "".join(sorted(s))

    def checkInclusion(self, s1: str, s2: str) -> bool:
        """
        Time: O(n)
        Space: O(n)
        Solve: best solution
        """
        A = [ord(x) - ord('a') for x in s1]
        B = [ord(x) - ord('a') for x in s2]
        target = [0] * 26
        for x in A:
            target[x] += 1

        window = [0] * 26
        for i, x in enumerate(B):
            window[x] += 1
            if i >= len(A):
                window[B[i - len(A)]] -= 1
            if window == target:
                return True
        return False

Testing().test(Solution().checkInclusion("ab", "eidbaooo"),True)
Testing().test(Solution().checkInclusion("ab", "eidboaoo"),False)<jupyter_output><empty_output><jupyter_text>Day 7 Breadth-First Search / Depth-First Search<jupyter_code># Flood Fill (Easy)

from collections import deque

class Solution:
    def floodFill(self, image, sr: int, sc: int, newColor: int):
        """
        Time: O(n)
        Space: O(n)
        Solve:
        """
        # BFS with que
        r_lim, c_lim = len(image), len(image[0])
        oldColor = image[sr][sc]
        q = deque([(sr, sc)])
        seen = set()

        while q:
            point = q.popleft()
            next_points = [(point[0] + 1, point[1]),
                           (point[0] - 1, point[1]),
                           (point[0], point[1] + 1),
                           (point[0], point[1] - 1)]
            for next_point in next_points:
                if 0 <= next_point[0] < r_lim and 0 <= next_point[1] < c_lim and next_point not in seen and image[next_point[0]][next_point[1]] == oldColor:
                    q.append(next_point)
                    seen.add(next_point)
            image[point[0]][point[1]] = newColor
        return image

Testing().test(Solution().floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2),[[2,2,2],[2,2,0],[2,0,1]])
Testing().test(Solution().floodFill([[0,0,0],[0,0,0]], 0, 0, 2),[[2,2,2],[2,2,2]])
# Max Area of Island (Medium)

from collections import defaultdict, deque

class Solution:
    def maxAreaOfIsland(self, grid) -> int:
        """
        Time: O(R*C)
        Space: O(R*C)
        Solve: 25m
        """
        islands = {}
        island_idx = 0
        y_lim, x_lim = len(grid), len(grid[0])
        visited = set()
        for y, row in enumerate(grid):
            for x, val in enumerate(row):
                # check if visited
                if (y, x) in visited:
                    continue
                else:
                    visited.add((y, x))
                # check if island
                if val:
                    q = deque([(y, x)])
                    islands[island_idx] = 1
                    while q:
                        point = q.popleft()
                        next_points = [(point[0] + 1, point[1]),
                                       (point[0] - 1, point[1]),
                                       (point[0], point[1] + 1),
                                       (point[0], point[1] - 1)]
                        for next_point in next_points:
                            next_y, next_x = next_point[0], next_point[1]
                            if 0 <= next_y < y_lim and 0 <= next_x < x_lim and grid[next_y][next_x] == 1 and next_point not in visited:
                                q.append(next_point)
                                visited.add(next_point)
                                islands[island_idx] += 1
                    island_idx += 1
        return max(islands.values()) if island_idx else 0

Testing().test(Solution().maxAreaOfIsland([[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]),6)
Testing().test(Solution().maxAreaOfIsland([[0,0,0,0,0,0,0,0]]),0)<jupyter_output><empty_output><jupyter_text>Day 8 Breadth-First Search / Depth-First Search<jupyter_code># Merge Two Binary Trees (Easy)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def mergeTrees(self, root1, root2):
        """
        Recursion
        Time: O(N)
        Space: O(1)
        Solve: Best Solution
        """
        if not (root1 or root2):
            return None
        tmp_node = TreeNode((root1.val if root1 else 0) + (root2.val if root2 else 0))
        tmp_node.left = self.mergeTrees(root1.left if root1 else None, root2.left if root2 else None)
        tmp_node.right = self.mergeTrees(root1.right if root1 else None, root2.right if root2 else None)
        return tmp_node
# Populating Next Right Pointers in Each Node (Medium)

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root):
        """
        Time: O(N)
        Space: O(1)
        Solve: Best Solution
        """
        if not root: return root
        if root.left:
            left, right = root.left, root.right
            self.connect(left)
            self.connect(right)
            while left:
                left.next = right
                left, right = left.right, right.left
        return root<jupyter_output><empty_output><jupyter_text>Day 9 Breadth-First Search / Depth-First Search<jupyter_code># Matrix (Medium)

class Solution:
    def updateMatrix(self, mat):
        """
        Time: Timeout
        Space:
        Solve: 30M
        """
        self.height = len(mat)
        self.width = len(mat[0])
        self.update_q = {(i, j): mat[i][j] for i in range(len(mat)) for j in range(len(mat[0])) if mat[i][j] > 0}
        self.M = mat
        self.count = 0
        while self.update_q:
            self.count += 1
            tmp_update_q = {**self.update_q}
            for r, c in tmp_update_q:
                self.neighbor(r, c, tmp_update_q)
        return self.M

    def neighbor(self, r, c, tmp_update_q):
        neighbors = [(r, c + 1),
                     (r, c - 1),
                     (r + 1, c),
                     (r - 1, c)]
        for neighb in neighbors:
            if 0 <= neighb[0] <= self.height - 1 and 0 <= neighb[1] <= self.width - 1 and neighb not in tmp_update_q:
                self.M[r][c] = self.count
                self.update_q.pop((r, c))
                break


class Solution:
    def updateMatrix(self, mat):
        """
        Time: O(nxm)
        Space: O(nxm)
        Solve: 28M
        """
        self.q = set((i, j) for i in range(len(mat)) for j in range(len(mat[0])) if mat[i][j] == 0)
        self.unsolved = set((i, j) for i in range(len(mat)) for j in range(len(mat[0])) if (i, j) not in self.q)
        self.M = mat
        self.count = 0
        while self.q:
            self.count += 1
            tmp_q = self.q.copy()
            self.q = set()
            for row, col in tmp_q:
                self.neighbor(row, col)
        return self.M

    def neighbor(self, r, c):
        neighbors = [(r, c + 1),
                     (r, c - 1),
                     (r + 1, c),
                     (r - 1, c)]
        for neighb in neighbors:
            if neighb in self.unsolved:
                self.M[neighb[0]][neighb[1]] = self.count
                self.unsolved.remove(neighb)
                self.q.add(neighb)

Solution().updateMatrix([[0,0,0],[0,1,0],[1,1,1]])
# Plan: BFS - update matrix by each level
# Rotting Oranges (Medium)

class Solution:
    def orangesRotting(self, grid) -> int:
        """
        Time: O(nxm)
        Space: O(nxm)
        Solve: 13M
        """
        self.rotten = set((i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j] == 2)
        self.fresh = set((i, j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j] == 1)
        self.minute = 0
        self.prev_rotten = set()
        while self.fresh:
            if self.rotten == self.prev_rotten:
                return -1
            self.minute += 1
            self.prev_rotten = self.rotten.copy()
            self.rotten = set()
            for rot in self.prev_rotten:
                self.neighbor(rot)
        return self.minute

    def neighbor(self, coord):
        r, c = coord[0], coord[1]
        neighbors = [(r, c + 1),
                     (r, c - 1),
                     (r + 1, c),
                     (r - 1, c)]
        for neighb in neighbors:
            if neighb in self.fresh:
                self.fresh.remove(neighb)
                self.rotten.add(neighb)

Testing().test(Solution().orangesRotting([[2,1,1],[0,1,1],[1,0,1]]),-1)
Testing().test(Solution().orangesRotting([[2,1,1],[1,1,0],[0,1,1]]),4)
Testing().test(Solution().orangesRotting([[0,2]]),0)<jupyter_output><empty_output><jupyter_text>Day 10 Recursion / Backtracking<jupyter_code># Merge Two Sorted Lists (Easy)

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

class Solution:
    def mergeTwoLists(self, list1, list2):
        """
        Time: O(N)
        Space: O(1)
        Solve: 10m
        """
        merged = ListNode()
        curr = merged
        while list1 or list2:
            if not list2:
                curr.next = list1
                break
            elif not list1:
                curr.next = list2
                break

            if list1.val > list2.val:
                curr.next = list2
                list2 = list2.next
            else:
                curr.next = list1
                list1 = list1.next
            curr = curr.next
        return merged.next

    def mergeTwoLists(self, list1, list2):
        """
        Time: O(N)
        Space: O(1)
        Solve: Best Solution
        """
        head = ListNode()
        curr = head
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
        curr.next = list1 if list1 is not None else list2
        return head.next

a = ListNode(1, ListNode(2, ListNode(4)))
b = ListNode(1, ListNode(3, ListNode(4)))
c = Solution().mergeTwoLists(a, b)
# Reverse Linked List (Easy)

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

class Solution:
    def reverseList(self, head):
        """
        Time: O(N)
        Space: O(1)
        Solve: 15M
        """
        reverse = head
        prev = None
        while head:
            reverse = ListNode(val=head.val, next=prev)
            prev = reverse
            head = head.next
        return reverse

class Solution:
    def reverseList(self, head):
        """
        Time: O(N)
        Space: O(1)
        Solve: 15M (Best Solution)
        """
        cur = head
        prev = None
        while cur:
            nextNode = cur.next
            cur.next = prev
            prev = cur
            cur = nextNode
        return prev<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1400842247930684, 'fraction_numerical': 0.029430272520451134, 'mean_word_length': 1.6971279373368147, 'pattern_counts': {'":': 1, '<': 59, '<?xml version=': 0, '>': 59, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '554114', 'license': 'MIT', 'n_tokens_mistral': 7211, 'n_tokens_neox': 6798, 'n_words': 1661, 'path': 'algorithm 1.ipynb', 'repo_name': 'codejacktsu/leetcode', 'size': '20659'}