Leetcode Series
Leetcode 48: Rotate Image
Code
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""Do not return anything, modify matrix in-place instead."""
assert matrix is not None, "Matrix is None!"
for row in matrix:
for i in range(len(row) // 2):
temp = row[i]
row[i] = row[len(row) - 1 - i]
row[len(row) - 1 - i] = temp
for k in range(len(matrix)):
for i in range(len(matrix[k]) - 1 - k):
temp = matrix[k][i]
matrix[k][i] = matrix[len(matrix) - 1 - i][len(matrix) - 1 - k]
matrix[len(matrix) - 1 - i][len(matrix) - 1 - k] = temp
First step: Pre-process each row
Each index swaps with the corresponding index at the end of the row. That is:
[0] swaps with [len(row) - 1], [1] swaps with [len(row) - 1 - 1], etc.
len(row) // 2 in the code means we only need to swap half-length amount of time, any more swaps will swap back to the original order.
An example:
1 2 3 3 2 1
4 5 6 -> 6 5 4
7 8 9 9 8 7
Second step: Swap bits diagonally
Imagine the matrix is composed of multiple sub-matrices, swap each diagonal corner pair (top-left with corresponding bottom-right)
that the top-left bit in the pair is LESS than len(matrix) - 1 - k where k represents the row ID. That is, if you notice the diagonal line
starting from top-right to left-bottom, which is a line of bits that are already in their positions by the pre-process (Think about how the rotate works).
And then we just need to swap each one counter diagonally once, therefore only swap the bits LESS than the bit in the diagonal line.
In the below implementation, k represents the row ID, i represents the column ID in that row.
An example:
3 2 1 7 2 1 7 4 1 7 4 1
6 5 4 -> 1st k, 1st i: 6 5 4 -> 1st k, 2nd i: 6 5 2 -> 2nd k, 1st i: 8 5 2
9 8 7 9 8 3 9 8 3 9 6 3
Leetcode 142: Linked List Cycle II
This question is asking for the node where the cycle begins if there's any, without modifying the list. It may comes less intuitive at the first glance, therefore we need some kind of algorithms that can detect the cycle in a different way.
Floyd's cycle-finding algorithm
The idea of this algorithm came up by Robert W. Floyd, is by using two pointers (tortoise and hare), such that one moves twice faster (2x speed) than the other, if there exists a cycle, the pointers will eventually meet at a certain point >= where the cycle starts.
Following the algorithm, consider a single linked list with a cycle like this:
*(Suggest drawing it out to make this clear :D)
Head _ _ _ {x} _ _ Cycle(S) _ _ {y} _ _ Meeting point(M) _ _ {z} _ _ Cycle(S) _ _ _
We know that at the meeting point (M), the distance travelled by the tortoise (the slow pointer) will be x + y, and for the hare (the fast pointer) will be x + y + z + y = x + 2y + z. Since we know the time is constant and the hare moves 2x speed than the tortoise, therefore we can deduce:
2 * (x + y) = x + 2y + z
2x + 2y = x + 2y + z
2x = x + z
x = z
Which means Distance (Head to Cycle start) equals to Distance (Meeting point to Cycle start).
Another way to prove the same statement:
Head _ _ _ {x} _ _ _ Cycle(S) _ _ _ {?} _ _ _ Meeting point(M) _ _ _ {?} _ _ _ (2x) _ _ _ {y} _ _ _ Cycle(S) _ _ _
Assuming the distance between the Head and Cycle(S) is x, when the tortoise arrives at Cycle(S), the hare will be at 2x. Assuming the distance between 2x and Cycle(S) by going forward is y, when the hare reaches Cycle(S) again by following the cycle, the tortoise will be at x + y/2.
So the problem now becomes:
The hare moves 2x faster than the tortoise, the distance between them now is a certain value say
y/2, when will the hare catch the tortoise?
And the answer is when the hare moves y distance, after a time of y/2.
If we think about where the hare starts, it's actually Cycle(S), and after y distance, they will meet, so the meeting point is at x + y.
We know that 2x to Cycle(S) is y, and Distance (Meeting point to 2x) is 2x - (x + y) = x - y, and so Distance (Meeting point to Cycle(S)) is x - y + y which is x itself.
The other case happens when the meeting point occurs before 2x:
Head _ _ _ {x} _ _ _ Cycle(S) _ _ _ (2x) _ _ _ Meeting point(M) _ _ _ {?} _ _ _ Cycle(S) _ _ _
We can still follow the same logic and find out the meeting point is at x + y. And the distance from 2x to the meeting point will be x + y - 2x = y - x. With the fact the distance between 2x and Cycle(S) by going forward is y, Distance (Meeting point to Cycle(S)) will be y - (y - x) which is x itself.
By knowing Distance (Head to Cycle start) equals to Distance (Meeting point to Cycle start), once we detect the tortoise and the hare pointers meet, we can have a pointer starting from the head that moves with a one in the meeting point at the same speed, and the point they meet up will be Cycle(S), the start of the cycle.
Summary
The slow and fast pointers (tortoise and hare) will meet up if there exists a cycle, otherwise the fast pointer will reach a None node.
When they reach at the meeting point, one moves from the head with the slow pointer moves from the meeting point at the same speed, the point they meet up is the start of the cycle.
Code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return None
slow = head.next
fast = head.next.next
while fast != slow:
if fast is None or fast.next is None:
return None
slow = slow.next
fast = fast.next.next
fast = head
while slow != fast:
fast = fast.next
slow = slow.next
return slow
Leetcode 33: Search in Rotated Sorted Array
General Idea
Basically on top of binary search, we make use of the first item in the list, which gives information about whether the smallest is on the left or right side of the current chosen [mid], and handle each case by case. To clarify: If no rotate is made, the algorithm just works as usual.
Explanation at each step within the code below.
Code
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if target < nums[mid]:
if nums[mid] < nums[left]:
"""
Smallest on the left side inclusively,
so if target is less than, it is only
possible on the left.
"""
right = mid - 1
else:
"""
If the smallest is on the right side of mid
caused by a possible rotate.
"""
if target > nums[left]:
"""
nums[left] < target < nums[mid],
since smallest on the right side,
it's a perfect interval (non-decreasing).
"""
right = mid - 1
elif target == nums[left]:
return left
else:
"""
Target possibly on the second half of
the right part.
"""
left = mid + 1
elif target > nums[mid]:
if nums[mid] < nums[left]:
"""Smallest on the left inclusively."""
if target > nums[right]:
"""
Since smallest on the left, leaving
the right part non decreasing. So if
greater, must only possible on the
first part of the left.
"""
right = mid - 1
elif target == nums[right]:
return right
else:
"""
nums[mid] < target < nums[right],
since smallest on the left side,
it's a perfect interval (non-decreasing).
"""
left = mid + 1
else:
"""
Smallest on the right = left part non-decreasing,
therefore if target greater than mid, must be in
the first part of right if exists.
"""
left = mid + 1
else: # target == nums[mid]:
return mid
return -1
Leetcode 1359: Count All Valid Pickup and Delivery Options
General Idea
Basically the idea is to iteratively count the specific "number of orders" based on the number of
possible sequences for "number of orders - 1"; and the number of possibilities of placing Pickup
and Delivery in each previous sequence, which can be calculated by summing up the first
((number of orders - 1) * 2 + 1) natural numbers.
The formula might be a bit vague at the first glance, let's have a look at an example first:
Suppose we are dealing with 2 orders, and we have already known that for 1 order the answer is 1,
which the only possible sequence is (P1, D1). We want to insert P2 and D2 somewhere such that D2 is
always after P2, so let's think about where we can insert P2 first.
We can insert P2 at any position in (P1, D1), and all the possibilities are: (P2, P1, D1), (P1, P2, D1)
and (P1, D1, P2) with the indices being [0, 1, 2], which the number of possibilities of placing P2 is
exactly k * 2 + 1, where k represents the number of orders - 1, and * 2 means each order has 2 states
(Pickup and Delivery).
Why? You can think of it as we can insert P2 right after any index, plus P2 being the first before
all the others, that doesn't violate the conditions since we haven't inserted/considered D2 yet.
Now we can imagine where to put D2 when P2 is settled down, it can be anywhere as long as after P2, right?
So when P2 is at index 0, there can be 3 possibilities D2 can be placed, right after P2 at index 1 -
[P2, D2, P1, D1], or after P1 - [P2, P1, D2, D1], or after D1 - [P2, P1, D1, D2]. And when P2 is at index 1,
there can be 2 possibilities (D2 right after P2 - [P1, P2, D2, D1], or at the last index - [P1, P2, D1, D2]).
And lastly when P2 is at index 2, the only possibility is [P1, D1, P2, D2]. Therefore, 1 * (3 + 2 + 1) = 6 in
total, being the answer for 2 orders.
From the above example, we can observe the pattern: When Pickup is at index say x, The number of possibilities
Delivery of the same number of orders can be placed is of (k * 2 + 1) - x, which means anywhere after x
(inclusively, meaning right after Pickup). Since x can be anything in [0 .. k * 2], therefore the number of
possibilities to place Pickup and Delivery, given a sequence of k (i.e., number of orders - 1), is calculated
by ((k * 2 + 1) - 0, (k * 2 + 1) - 1, ... (k * 2 + 1) - k * 2). That is, for example for 3 orders, which 3 - 1
orders that has 4 states - (P1, D1, P2 and D2), the number of possibilities based on a given previous sequence
is 5 + 4 + 3 + 2 + 1 = 15, that is the sum of the first (k * 2 + 1) natural numbers! And since there are 6
possible sequences for the previous number of orders (= 2), therefore for 3 orders, the answer is 6 * 15 = 90.
Overall, the answer for n orders, equals to:
(The number of possible sequences for n - 1) * (The sum of the first n natural numbers)
Code
class Solution:
def countOrders(self, n: int) -> int:
"""
The sum of the first n natural numbers: (n + 1) * n / 2.
e.g. For 10: (1 + 10) + (2 + 9) + (3 + 8) + ..., in total
that has n / 2 sets such that each set equals to n + 1.
"""
ans = 1
for i in range(2, n + 1):
"""
Here i - 1 represents the previous number of orders, (* 2) represents each has 2 states Pickup and Delivery,
that together gives the total number of elements in each of it's possible sequences. Then + 1
represents other than placing the Pickup at the end of each element, it can be placed at the first index
before everyone else. Together as ((i - 1) * 2 + 1) represents the number of possible places to put the Pickup
and hence the natural number we need.
"""
ans = math.floor((ans * ((((i - 1) * 2 + 1) + 1) * ((i - 1) * 2 + 1) / 2)) % (10 ** 9 + 7))
return ans
Leetcode 904: Fruit Into Baskets
Intuition
Question = Find the longest sub-string consists of only two numbers.
Approach
Keep track of the last seen number before the current index, while Having a pointer to the start of such a
valid sub-string that ends up in the current index (inclusively); Or if the number of the current index cannot be
included in the current sub-string (The first third number, which terminates the construction), update the maximum,
set start to the starting index of the last seen number (which refers to the longest valid sub-string, should the
current number be included). And then update the basket, which is used to keep track of the two numbers (fruits) of the
current sub-string.
If start cannot make the sub-string ending up at i (inclusively) valid, then any starting index before start cannot.
If start can make the sub-string ending up at i (inclusively) valid, then any starting index between start and i can.
Complexity:
Time complexity: O(n)
Space complexity: O(1)
Code
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
start = 0
max_fruits = 0
last_candidate = (0, fruits[0])
basket = []
for i in range(len(fruits)):
if fruits[i] not in basket:
if len(basket) < 2:
basket.append(fruits[i])
else:
max_fruits = max(max_fruits, i - start)
start = last_candidate[0]
basket = [fruits[i], last_candidate[1]]
if fruits[i] != last_candidate[1]:
last_candidate = (i, fruits[i])
return max(max_fruits, len(fruits) - start)