ア

Given an image stored in a 2D Python array, we provide code for rotation by different degrees. Clockwise by 90 degrees Transpose then reverse each row def rotate(image): n = len(image) for i in range(n): for j in range(i+1, n): image[i][j], image[j][i] = image[j][i], image[i][j] for i in range(n): row = image[i] l, r = 0, n-1 while l < r: row[l], row[r] = row[r], row[l] return image Counterclockwise by 90 degrees Reverse each row then transpose Transpose is 180 degrees def rotate_counterclockwise(image): n = len(image) for i in range(n): row = image[i] l, r = 0, n-1 while l < r: row[l], row[r] = row[r], row[l] l += 1 r -= 1 for i in range(n): for j in range(i+1, n): image[i][j], image[j][i] = image[j][i], image[i][j] return image

We edit the popular problem series of best time to buy and sell stocks to allow differing buy and sell prices. def max_profit(buy, sell): n = len(buy) dp_holding, dp_not_holding = 0, 0 dp_holding = -sell[0] for i in range(1, n): tmp = dp_holding dp_holding = max(dp_holding, dp_not_holding - buy[i]) dp_not_holding = max(tmp + sell[i], dp_not_holding) return dp_not_holding

We provide an implementation of removing duplicated values from an (unsorted) array. Sorted version (link) def remove_duplicate(arr): seen = [] for num in arr: seen.append(num) return seen print(remove_duplicate([1, 2, 2, 4, 4])) print(remove_duplicate([5, 4, 1, 5])) print(remove_duplicate([5, 2, 5, 1])) [1, 2, 4] [5, 4, 1] [5, 2, 1] Time and space: $O(N)$. Not possible to be $O(1)$ since we do not know where the duplicate is located and no ordering information. Extra space is needed to check if value has been encountered before.

In this note, we provide code to compute useful statistics in a dataset in $O(1)$ space. Sliding window max and min from collections import deque def sliding_window_maximum(nums, k): """ nums: observed data stream k: window size ( k <= len(nums) ) """ res = [] q = deque() for i in range(k): num = nums[i] while q and nums[q[-1]] <= num: q.pop() q.append(i) res.append(nums[q[0]]) for i in range(k, len(nums)): num = nums[i] # adjust window if q and q[0] <= i-k: q.popleft() while q and nums[q[-1]] <= num: q.pop() q.append(i) res.append(nums[q[0]]) return res # test nums = [1, 1, 2, 3, -1, 3, 2] k = 2 # => [1, 2, 3, 3, 3, 3] print(sliding_window_maximum(nums, k)) def sliding_window_minimum(nums, k): nums_neg = [-num for num in nums] neg_res = sliding_window_maximum(nums_neg, k) return [-num for num in neg_res] nums = [1, 1, 2, 3, -1, 3, 2] k = 2 # => [1, 1, 2, -1, -1, 2] print(sliding_window_minimum(nums, k)) The outputs are the following ...

In this note, we solve a problem from Introduction to Probability (Blitzstein, Hwang) Question There are 100 shoelaces in a box. At each stage, you pick two random ends and tie them together. Either this results in a longer shoelace (if the two ends came from different pieces), or it results in a loop (if the two ends came from the same piece). What are the expected number of steps until everything is in loops, and the expected number of loops after everything is in loops? Solution Start with small case, let $f(n)$ be the number of loops that can be formed. $\mathbb{E}[f(1)] = 1$, since with probability 1 the two ends of the only shoelace are chosen. Then, ...