KarmaCoder Day 4 LC24/19/02.07/142

1️⃣ Swap nodes in pairs Link: lc24

1. Draw the next directions can be straightforward.

2️⃣ Remove Nth node from end of list

1. Two pointers, one moves first by n steps, then both move until the first one moves to the last node, then delete the node the second pointer is located at.

3️⃣ Intersection of two linked list

1. Find the length difference of two lists and move the longer list pointer points to the same length position.
2. Move pointers on both lists together until they intersect.

4️⃣ Linked List Cyle II

1. Fast and slow two pointers with step size of 2 and 1, respectively, the distance between the head and the cycle begin is equal to the distance between the intersection and the cycle begin.
2. code is difficult, the key is to find out the above pattern.

KarmaCoder Day 3 LC203/707/206

1️⃣ Remove Linked List Elements Link: lc203

Takeaway:microphone::

1. ListNode construction: value, next
2. Often the process is we find a node, and do some operations on it. Thus, it’s most convenient to identify this node at its previous node, and at the same time, store the pointer to its next node.
3. Creating a dummy node ahead of the head node allows us to process the head node as other nodes.

2️⃣ Design linked list

1. When designing a linked list, initialize a dummy head, then add elements one by one.

3️⃣ Reverse linked list

1. Two pointers, one is cur, the other is pre
2. Temporarily save current node’s next node because we will change it to the previous node.

KarmaCoder Day 2 LC209/59

1️⃣ Minimum size subarray sum Link: lc209

Key points:

1. Two pointers: one goes through the array, the other updates the subarray start to make sure the length is minimum.
2. Once the first pointer moves to a position where the sum reaches target, the second pointer starts to narrow the length of subarray as much as possible while maintaing the sum equal to or larger than the target.

Time complexity: O(n) Space complexity: O(1)

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
  start, sum = 0, 0, 0
  min_len = float('Inf')
  for i in range(len(nums)):
      sum += nums[i]
      while sum >= target:
          min_len = min(min_len, i - start + 1)
          sum -= nums[start]
          start += 1
  return min_len if min_len != float('Inf') else 0

2️⃣ Spiral matrix Link: lc59

Key points:

1. Python can directly initialize a 2D array, but note that [[0] * n for _ in range(n)] is different from [[0] * n] * n. Don’t use the second way in most cases because it creates multiple references to the same inner list, which means updating one inner list appears in all rows because they are the same object.
2. The outer for loop controls how many loops we need to circle, ignoring the center element if n is odd (which will be filled at the end)
3. Inside the outer loop, four parallel inner for loops correspond to four sides note that each inner loop follows the same range pattern (ex. left-inclusive, right-exclusive)

Time complexity: O(n) Space complexity: O(1)

KarmaCoder Day 1 LC704/27/977

1️⃣ Binary search Link: lc704

Key points:

1. The principle is the range definition, either a double-closed range [A, B] or a left-closed right-open range [A, B)
2. the while loop condition depends on the range definition:
   1. double-closed: left <= right is valid
   2. left-closed right open: left < right is valid.
3. the if-else statement depends on the range definition:
   1. double-closed: the updated left or right does not include mid
   2. left-closed right open: the updated right can include mid
4. Similarly, right is initialized to numsSize - 1 or numsSize also depends on the range definition.

Time complexity: O(logn) Space complexity: O(1)

def search(self, nums: List[int], target: int) -> int:
  left = 0
  right = len(nums)
  while left < right:
      mid = (left + right) // 2
      if target < nums[mid]:
          right = mid
      elif target > nums[mid]:
          left = mid + 1
      else:
          return mid
  return -1

2️⃣ Remove element Link: lc27 Key points: