Scribbling

The first solution is using binary search. class Solution: def missingNumber(self, nums: List[int]) -> int: left, right = 0, len(nums) while left < right: mid = (left + right) // 2 cnt = 0 for num in nums: if num int: ret = len(nums) * (len(nums) + 1) // 2 for num in nums: ret -= num return ret

My own code is always messy. The idea is to sort the list and calculate sums. Time complexity will be O(NlogN) due to sorting. class Solution: def numPairsDivisibleBy60(self, time: List[int]) -> int: time = [t % 60 for t in time] time.sort() ret = 0 l, r = 0, len(time) - 1 while l < r: if time[l] + time[r] == 60: if time[l] == 30: cnt = 0 while l 0 else c[0] c[t] += 1 return ans

My somewhat complicated code using queue. Both time and memory complexities are O(N). # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return '' ret = str(root.val) + ' ' q = [r..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None odd_ptr = head even_ptr = even_head = ListNode() cur = head.next cnt = 2 while cur != None: if cnt % 2 != 0: odd_ptr.next = cur odd_ptr = cur else: even_pt..

To solve this problem in-place, we can think of using two more states(2, 3) rather than two states(1, 0). class Solution: def gameOfLife(self, board: List[List[int]]) -> None: """ Do not return anything, modify board in-place instead. """ m, n = len(board), len(board[0]) for y in range(m): for x in range(n): cnt = self.countOnes(board, y, x) if board[y][x] == 0: if cnt == 3: board[y][x] = 3 else..

As a novice, it was not easy at all for me to solve this problem. I relied on other people's explanations and codes, and this post is to summarize their ideas. It is very tricky to solve this problem within O(N) time & O(1) memory. (* without modifying the array) The best way is "Floyd's Algorithm" as this problem can be seen as a linked list with a cycle. Check out the below video for further e..

O(N**2) Time Complexity, O(N) Memory Not an effective solution at all especially in terms of time complexity. class Solution: def numSquares(self, n: int) -> int: INT_MAX = int(1e5) dp = [INT_MAX] * (n+1) x = 1 while x * x int: psns = [] x = 1 while x * x int: INT_MAX = int(1e5) dp = [INT_MAX] * (n+1) dp[0] = 0 for i in range(1, n+1): for j in range(1, int(i**0.5)+1): dp[i] = min(dp[i], dp[i-j*j..

Several different solutions class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: j = bisect_right(matrix[0], target) - 1 i = bisect_right([mat[0] for mat in matrix], target) - 1 while i >= 0 and j >= 0: if matrix[i][j] < target: return False for k in range(0, i+1): if matrix[k][j] == target: return True for k in range(0, j+1): if matrix[i][k] == target: return Tr..

Using two pointers. class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ j = 0 for i, num in enumerate(nums): if num != 0: nums[j] = num j += 1 for k in range(j, len(nums)): nums[k] = 0

Solution for Q.234 within O(N) time complexity and O(1) memory. To check whether it's a palindrome, we have to check two elements simultaneously from the head and tail. But in singly linked list, we have no way to check the elements in reverse order from the tail. So, the solution is simple. Reverse the second half of the list and compare two lists. Below is the code. # Definition for singly-lin..