Background

From time to time, my daughter reads short kid’s English books with an iPad and publishes the videos through Apps. The reading is pleasant but the publishment is tedious. Various Apps (Youtube and others) need to be installed on the iPad and manual work and waitings are needed for publishment. In addition, archiving those videos (for memory and for uploading to any future platform) also becomes an issue since the iPad has 32GB storage only.

Solution Disassembly

Step by step, I’m going to build a solution to tackle all problems mentioned in above.

1, upload iPad video to NAS server

Here iPad can be any iOS devices like an iPhone as long as shortcut is available. Also a NAS server can be any Linux server that is accessible regardless its location (but ideally a home server considering network speed and stable accessibility).

Detailed Steps in :

Upload iPad Video to NAS server

2, processing the video.

2.1 transform the video format (default is Apple’s MOV) to MP4: needed?

2.2 use AI tools to determine the video’s title / tags

2.3 add an opening and water mark to the video

Detailed Steps in : <Article Link to be posted>

3, publishment

Publish the video to different platforms. Per configuration, publishment is scheduled in a way that any channel of any platform will release a video at a given time.

Detailed Steps in : <Article Link to be posted>

Channels in case you are interested

Kid’s Book Reading in English:

https://www.youtube.com/channel/UC-bKYyvCA6ocNZKql1uAJPg

Video Publishment Automation was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Problem Description

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e. perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array. Return the minimum number of operations needed to make all the elements of arr equal.

Example 1:

Input: n = 4
Output: 4
Explanation: arr = [1, 3, 5, 7]
First 3 operations choose x = 3 and y = 0, this leads arr to be [4, 3, 5, 4]
Now take 1 operation choose x = 2 and y = 1, thus arr = [4, 4, 4, 4].

Example 2:

Input: n = 7
Output: 12

Solution

BTW, don’t be frightened by the word “minimum” :)

To start with, just use a simple example like [1,3,5] (where n=3).

As the below picture shows, when n=3, the quickest way to make all elements equal is to

1. increase array[0] by 1 and decrease array[2] by 1
2. repeat #1

So the minimum operation is 2. This is not strict prove and the philosophy behind is to make all values increase/decrease towards the median value since, in each operation, I will have one value increase by 1 and the other decrease by 1, it will be natural to do that against mirrored elements in each end.

Now, look at other examples shown above like n=4 and 6. Mirrored elements will be taken by operations in X times where X=1,3,5,…, n/2 if n % 2 == 0. For n % 2 ==1, X will be 2,4,6,…,n-1.

OK, so the number of operations is the sum of an array

1,3,5,…, n/2 if n % 2 == 0

2,4,6,…,n-1 if n % 2 == 1

This is basically a math question now. The sum of an array like below is (start + end) * size_of_array / 2 = (start + start + size_of_array * 2–2) * size_of_array / 2 = (start + size_of_array -1) * size_of_array

start, start +2, start +4, …, end

Translating above illustration will lead to:

Time & Space Complexity

Since I just put n in a formula to calculate the end result, the time complexity is O(1) meaning no matter how n gets change (for example, from 10 to 100 or to 1000000), the run time will not grow along with it.

Space complexity will be O(1) as well since no extra space(like an auxiliary array) is used.

Extended Reading

Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549

Leetcode 1551. Minimum Operations to Make Array Equal— Graphically Explained Python3 Solution was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Problem Description

Given the root of a binary tree, then the value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N of depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5

Example 2:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5

v = 1

d = 1

Output: 

         1
        /
       4
     /   \
    2     6
   / \   / 
  3   1 5

Solution

The key to this problem is that I need to:

1, know what’s the current depth for a node I visit now.

2, when current depth == d-1, I need to create 2 new children nodes and ask the left child’s left pointing to the current node’s left and the right child’s right pointing to the current node's right.

One corner case is what if d ==1. The problem description mentions that during an interview one may be expected to ask in the first place. So it may be a good practice to not look at the examples after reading the problem description; instead, think about the possible examples (to cover as many as possible scenarios) and then read further on provided examples to compare and reflect.

With the above explanation, hopefully below 2 solutions make more sense.

Recursive (DFS) Solution

Non-recursive(BFS) Solution

Time & Space Complexity

For both above solutions, assuming if there are N nodes, in general, the nodes I need to visit are directly related to N. Therefore the time complexity is also O(N).

When it comes to space complexity:

1. The recursive solution requires O(1) space if the function calling stack is not calculated; otherwise, it’s O(N) since the more nodes you have, on average, the deeper you need to go.
2. The non-recursive solution needs to store one layer of nodes so it is O(x) where x is the maximum possible nodes in a layer of the tree.

Extended Reading

Python3 cheatsheet:

• Python3 Cheatsheet (continuously updated)
• Algorithm Cheatsheet (continuously updated)

LeetCode 623. Add One Row to Tree — Explained Python3 Solution was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Problem Description

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example:

Input: lists = [[1,1,5],[1,3,4],[2,6]]
Output: [1,1,1,2,3,4,5,6]
Explanation: The linked-lists are:
[
  1->1->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->1->2->3->4->5->6

Solution

Obvious Solution

The obvious (and brute force) way is to navigate ALL list items, save them into an array and then sort. The time complexity is: O(kN + kNLog(kN)) since for for total k Lists (each one with average N elements), I need to visit them all and the quick sort on final array takes kNLog(kN). The space complexity is O(kN) as all values will be saved.

Best Solution (to me)

Since each list is already sorted, I can definitely leverage that. To start with, let me use this example:

To show it more clearer, let me put some twists (showing only the leftmost element of each list):

You can see from above, for all current leftmost elements, “1” (doesn’t matter which “1”, so I just pick the one in the first list) is the smallest element. Although I haven’t looked into all other elements, I’m pretty sure it’s the smallest element of ALL elements. Why? The reason is, within current smallest elemements (of all lists), it’s the smallest: smallest among the smallest :).

So “1” will be picked up as current smallest element and its next element (if any) will become current like below right part:

Then I can repeat the process until all elements are visited.

Additional Tips:

There are 2 additional tips (which I use in the source code):

1. Dummy head of linked list

Detailed illustration can be found within below Cheatsheet article (search “dummy” in it). I recommend reading it before checking following source code.

Python3 Cheatsheet (continuously updated)

2. Heapq (priority queue)

Detailed illustration of heapq can be found in above Cheatsheet article (search “heapq” in it). I recommend reading it before continue reading.

The heapq is used in source code to achieve O(1) complexity to get smallest element out of a bunch elements. A detail to know for Python3 heaqp is: when I heappush a tuple, by default, tuple[0] will be used to compare with existing tuples’ tuple[0], if there is equal pair, tuple[1] will be used.

So below code may report “TypeError: ‘<’ not supported between instances of ‘ListNode’ and ‘ListNode'”, since (1,n1)[0] == (1,n2)[0] and Python3 will compare n1 and n2 but “<” operator may not be implemented in ListNode class.

import heapq
h = []
n1 = ListNode(1)
n2 = ListNode(1)
heapq.heappush(h, (1, n1))
heapq.heappush(h, (1, n2)) #TypeError: '<' not supported ...

To avoid that, I add a unique counter to the tuple like:

import heapq
h = []
n1 = ListNode(1)
n2 = ListNode(1)
cnt = 0
heapq.heappush(h, (1, cnt, n1))
cnt +=1
heapq.heappush(h, (1, cnt, n2)) 

Time & Space Complexity

Per above illustration and techniques, all elements will be visited once only and for each element, there will be a Heapq push ( O(LogN) where N is the size of heap) and pop (O(1)). Assuming there are k lists and each one has N elements on average, the total elements are kN, and each element will be processed in heapq by O(Logk), the final time complexity is O(kN Logk).

Since I use a heap size of k, the space complexity is O(k).

Source Code

Thanks for reading and if you feel this article is helpful, please clap for it and follow me in Medium!

LeetCode 23. Merge k Sorted Lists— Graphically Explained Python3 Solution was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Reaching Medium article limit? You can also read my aticle at https://myleetcodejourney.blogspot.com/.

Problem Description

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: 1->1->2->2

Output: <empty>

Example 2:

Input: 1->2->2->3

Output: 1->3

Solution

The most fun (or puzzling) part of this problem is: when you come to a node that is different in value with its previous one, you don’t know whether it’s a duplicate one until you go to its next node.

To me, there is a pattern here: during an iteration, I cannot make a decision on current element before I get to following elments. Normally I can use stack for this pattern. The key is: somehow I store elements in stack (so that I can retrieve them in a reversed or original order) for now and fetch them later basing on situations.

So assume I have an input linked list like:

Step by step walk-through

1. When I iterate the list using a pointer (p) and first I see “1” in the beginning. Since I don’t know whether there will be more ‘1’ along the road (yet), I will just put it in the stack.

2. Now I move p to the second node and I see another “1”. This time I actually know “1” is duplicate but in case there are more “1” following, I will just throw it into the stack as well.

3. Here p points to the third node “2”, since it’s not equal to the top item of the stack (which is “1” as shown in previous step) and this is an ascending linked list, I know a duplication list of “1” ends so I will just clear the stack. And for current node “2”, again I don’t know whether it’s duplicate so I have to push it to the stack.

4. Like #2, I add the last node to the stack and move p to its next.

5. Finally I reach the end of input linked list and since the stack contains more than 2 elements (and for sure they have duplicate values), I will discard them as well. In the end, I will return an empty list (None in Python).

Another tip: a dummy header

In above example, there is actually nothing left in the result. Consider another example 1->2->2->3, similiarly, when I visit the second node which has a different value than stack[-1] and len(stack) == 1, it means the one in the stack is a unique one, I need to put it in final result link. A little tedious handling is: normally I need to see if this unique one is the first unique one and write separate codes to tackle yes/no situations like:

if len(stack)==1 and stack[-1].val != p.val:
  if resultHeader == None:
    resultHeader = stack.pop()
    preNode = resultHeader
  else:
    preNode.next = stack.pop()
    preNode = preNode.next
....
#finally return resultHeader
return resultHeader

It would be beautiful if I can use the same set of codes for both situations! And actually there is a way like:

resultHeader = ListNode() #this is a dummy header
preNode = resultHeader

if len(stack)==1 and stack[-1].val != p.val:
  preNode.next = stack.pop()
  preNode = preNode.next
....

#finally return resultHeader.next
return resultHeader.next

Source Code

Time & Space Complexity

All nodes will be visited once so time complexity is O(N). Stack may contain all nodes in worst case (for example, all elements are distinct) and in that case, space complexity will be O(N).

Extended Reading

Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549

Leet Code 82. Remove Duplicates from Sorted List II — Graphically Explained Python3 Solution was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Problem Description

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Solution

Obvious Solution

The obvious (and brute force) way is to use 2 pointers: left and right. Let left points to index 0 ~ N-1 and then right to left and N-1. For each left and right pair, I can calculate the area[left, right] using (right-left+1) * min(heights[left], heights[left+1],heights[left+2],…,heights[right]). Its time complexity is at least be O(N²).

Best Solution (to me)

[Credit] This is described by @TravellingSalesman in disucssion area (https://leetcode.com/problems/largest-rectangle-in-histogram/solution/) and here I just try to illustrate it further.

Take the example of heights array [2,1,5,6,2,3], each area must be in the height of any element within heights. In other words, the maximum area will either be an area with height=2, or an area with height=1, or an area with height=5 and etc. So instead of using 2 pointers like mentioned in above section, here I can use height central perspective: if I want to use heights[2] (=5) as the height of a candidate area, how to get its width? Not surprisingly, I need to look to its left to find the first (leftmost) height (its index referenced as L in following) that is smaller than 5 and rightmost height (its indexreferenced as R in following) that is smaller than 5: yellow arrows in below graph (Pic 1) illustrate the boundaries. With that the width=(R-L)-1=4–1–1=2 and hence the area = width * height = 2 * 5 = 10 (as shown in yellow rectangle).

What if a height is the samllest one so there is no valid L, R? For example, for heights[1]=1, obviously the area of heights[1]=1 will has the width=6 (the length of the heights array). Logically, I can assume L = -1 while R=size-of-heights. Similar logic applies to an element that seems has only a valid L or R: for example, red rectangle indicates an area with the heights[5] and it’s L=4 and R=6 so its width=R-L-1=6–4–1=1 and its area = 1 * 3=3.

There is a smat way to implement above algorithm: using a stack that stores ascending elements. When I iterate the array, if the top of the stack (as referenced as stack[-1] in Python) is larger than current element, for the one on the top of the stack, we actually find its R; its L is actually the second to the top: with this, I can conclude the area with the height corresponding to the top of the stack; if the top of the stack (as referenced as stack[-1] in Python) is smaller or equal than current element, that means I still don’t know what’s the R for current top element in the stack, so I will just push current element to the stack.

Sounds dizzy? Let me walk through the algorithm with the example [2,1,5,6,2,3]. To simplify writing, I use Area[i] to denote the area whose height is height[i].

0, first I run into index=0 (height=2). It’s the first one and I know its L = -1 but am not sure the value of R, so I just put its index (so that later I can get its index for width calculation and in the same time get its value for height through heights[index]) in the stack. Now stack=[0].

1, now I come to index=1(height=1). It’s less than current top of stack’s value since heights[1] < heights[stack[-1]]. So I find heights[stack[-1]] (aka heights[0])’s R= current index. So for the area of heights[0] (illustrated by green vertical lines in Pic 1) is (R-L-1) * heights[0] = (1-(-1)-1)*2=2. So I have Area[0] calculated. I will pop up index 0 from stack since its area is calcuated; but for index 1, its corresponding area is not yet calculated (I don’t know its R although its L is -1), so I push it to stack and now stack=[1].

2, now I come to index=2(height=5). Since heights[2] > heights[stack[-1]], for stack[-1], I cannot decide its R, just push current index to stack and makes stack=[1,2].

3, now I come to index=3(height=6). Same as #2 and now stack=[1,2,3].

4,now I come to index=4(height=2). Now heights[4] <heights[stack[-1]], it means for index stack[-1] (aka index 3), I find its R and therefore Area[3]= (R-L-1)*heights[3]=(4-heights[stack[-2])*heights[3]=(4–2–1)*6=6. Now I pop up the top of the stack and the stack=[1,2]. Notice stack[-1]=2 and heights[2] >heights[4], it indicates heights[2]’s R=4 as well. So similarly I can have Area[2]= (R-L-1)*heights[2]=(4-heights[stack[-2])*heights[3]=(4–1–1)*5=10 and pop up the stack to get stack=[1]. Now stack[-1]=1 and heights[1] < heights[4] so heights[1]’s R is not yet decided and hence it stays at the stack. Now stack=[1,4].

5,now I come to index=5(height=3) and similar to #3 now stack=[1,4,5].

6, now I go beyond the array. Remember there is a default R=size-of-array=6? So for everyone remaining in the stack, its R is the index after it (except for the last one, it’s 6) and its L is the index before it(except for the first one, it’s -1). Bear in mind that heights array is [2,1,5,6,2,3] and I will have

Area[5]= (6–4–1) * height[5] = 3

Area[4]=(6–1–1) * height[4] = 8

Area[1]=(6-(-1)-1)* height[1] = 6

7, looking at Area[x] where x in 0~5, the largest one will be the answer.

Source Code

Slightly different from above walk-through, I add a “-1” to the stack in the beginning (serving as default L). In the end, an extra checking (corresponding to #6 in above) is performed.

Time & Space Complexity

As illustrated above, I only need to travse the heights array once and when visiting an element, although there is a need to do while loop against the stack, each element will just be inside the stack for once. Therefore, the time complexity is O(N) and so is space complexity.

Extended Reading

Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549

Leet Code 84. Largest Rectangle in Histogram — Graphically Explained Python3 Solution was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Reaching Medium article limit? You can also read my aticle at https://myleetcodejourney.blogspot.com/.

Problem Description

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it. The answer is guaranteed to fit in a 32-bit integer.

Example 1:

Input: s = "12203"
Output: 2
Explanation: It could be decoded as "ABTC" (1,2,20,3) or "LTC" (12,20,3).

Example 2:

Input: s = "20103"
Output: 1
Explanation: It could be decoded as "TJC" (20, 10, 3).

Example 3:

Input: s = "2030"
Output: 0
Explanation: 30 could be decoded.

Solution

Obvious Solution

The obvious (and brute force) way is to try every possible way. The solution looks like below tree and I will calculate final valid path number as the result. For example 1, it’s like a DFS way: first I can decode “1” or “12”, and then under “1”, I can have the choice of decoding “2” and “22”, and then under “2”, I can decode “2” only or “22” and etc. From below grahp, I can see there are some obvious duplicate calculations (like run into ‘0’ and ‘03’ decoding many times).

Best Solution (to me)

I can use Dynamic Programming to solve this. The idea comes from following thoughts: assuming there is a string X(for example, ‘12’) and I know the ways to decode it is 2 ([1,2] or [12]). Now let me append one more char(for example, ‘3’). Obviously, for the new string, the decode way is 2 (by decode 3 to ‘C’ and get [1,2,3] or [12,3]) + 1 (by decode 3 with its previous char ‘2’, and then use adopt the decode ways for ‘1’ which is 1) = 3. So in general, if I use dp[i] for the decode ways of the string ending at index i, I will have

dp[i] = dp[i-1] + dp[i-2] (if 0 < s[i-1] + s[i] ≤ 26)

Above is a raw idea and there are some details to figure out as below.

1. If s[i] is ‘0’, it must combine with its previous char since ‘0’ cannot be decoded; so in this case, there should be a previous char and it should be either ‘1’ or ‘2’. If s[i] is not ‘0’, then dp[i] = dp[i-1].
2. if dp[i] is 0, then I need to immediately return 0 which means it’s impossible to decode the whole string. Think about the example like ‘123012592329’, when I iterate to calculate dp[3], the ‘0’ (at index = 3) itself cannot be decoded and even it gets combined with previous char (‘3’), it cannot produce an valid decoded char and hence it makes no sense to continue.
3. To make sure dp[i-1] and dp[i-2] are always valid, I initiliaze dp=[1,1] and use dp[-1] and dp[-2] instead of dp[i-1] and dp[i-2]. The values of 1s assume there are always 1 way to decode (if not running to “return 0”).

Time & Space Complexity

It takes only one iteration of all input (assuming there are N letters) so the time complexity is O(N).

I use an array to store up to N+1 values (for an initialization value and decode ways of s[:0], s[:1], s[:2] and etc.) so the space needed is propotional to N and hence the space complexity is O(N) as well.

Extended Reading

Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549

Leet Code 91. Decode Ways — Graphical Explained Python3 Solution was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Purpose:

This is a continuous updated post to summarize typical algorithms in Python3 templates. My expectation is to train my muscle memory to these Python3 algorithm implemetations so that whenever I need them in problem solving, I don’t need to think too much (just apply those algorithm implemetation templates) and make little (if not zero) mistakes.

Python3 Templates for Typical Algorithms

1. Typical DFS Python3 template

#params are normally those will change in each round of dfs
#for example, a position that something inside dfs will start with
#I'd suggest a more meaningful name to use than "dfs"
#like rollFrom(postion)

visited = []

def dfs(current_node):
  #processing current_node to generate more leads(nodes)
  nodes = processing of current_node
  visited.append(current_node)
  for node in nodes:
    if node not in visited:
      dfs(params_turning_from_branch_info)

dfs(start_node) #kick start dfs

Above template will check each path one by one, but sometimes I will need to abort the checking if an answer is found in some path. In that case, the template can be slightly modified to be:

#params are normally those will change in each round of dfs
#for example, a position that something inside dfs will start with
#I'd suggest a more meaningful name to use than "dfs"
#like rollFrom(postion)

visited = []

def dfs(current_node):
  #processing current_node to generate more leads(nodes)
  nodes = processing of current_node
  visited.append(current_node)

  #during above processing, some required criteria are met
  if(criteria are met):
    return True
  for node in nodes:
    if node not in visited:
      if dfs(node): 
        return True
  return False

return dfs(start_node) #kick start dfs

2. Typical BFS Python3 template
Similarly to DFS, I may use BFS to find ALL possible answers (which means I need to navigate all nodes). Also, I may just stop by the first answer, which below template applies to.

Also, below template is not using recursive calls.

visited = []
toVisit = [start_node]

while(len(toVisit) > 0):
  toVisitInNextLayer = []

  for current_node in toVisit:  
    #processing node to generate more leads(nodes)
    nodes = processing of current_node
    visited.append(current_node)
  
    #during above processing, some required criteria are met
    if(criteria are met):
      return True

    for node in nodes:
      if node not in visited:
        toVisitInNextLayer.append(node)
   
  toVisit = toVisitInNextLayer

return False

Extended Reading

1. Python3 cheatsheet:

Python3 Cheatsheet (continuously updated)

Algorithm Cheatsheet (continuously updated) was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Useful Build-in Functions

1. zip

A quick show of what it can do:

a = (“John”, “Charles”)
b = (“Jenny”, “Christy”)

x = zip(a, b)

#use the tuple() function to display a readable version of the result:

print(tuple(x)) #print ((‘John’, ‘Jenny’), (‘Charles’, ‘Christy’))

Detailed explanation is available at https://www.w3schools.com/python/ref_func_zip.asp

2. sorted

This is useful to sort any collection(list, dictionary). A simple example looks like:

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

In addition, there is an optional parameter “key” which serves as a function that can take one input (it will be one element of the collection) and return whatever you want for sorting purpose. Certainly, I can put a lambda expression there. An example looks like:

>>> sorted([5, 2, 3, 1, 4], key=lambda x:-x)
[5, 4, 3, 2, 1]
#when 5 is used to compare, I actaully make it -5 so it will be the smallest number and hence it will be the first one.

Detailed explanation is available at

Sorting HOW TO - Python 3.8.5 documentation

3. any

Refer to https://www.programiz.com/python-programming/methods/built-in/any:

The any() function returns True if any element of an iterable is True. If not, any() returns False.

>>> any([0,1])
True
#since 1 is True
>>> any([1,0])
True
#since 1 is True
>>> any([0,None])
False
#since not element is True

4. enumerate()

This function is pretty handy when I want to get both index and value for a list (or key and value for a dict).

names    = ['ant', 'maven', 'gradle']
versions = ['1.0', '2.0', '3.0']

for i, v in enumerate(names):
    full_name = v + '-' + versions[i]
    print(full_name)

'''
Output: 
   ant-1.0   
   maven-2.0
   gradle-3.0
'''

In addition, I can add an optional parameter which specifies the starting index, an example from https://book.pythontips.com/en/latest/enumerate.html looks like:

my_list = ['apple', 'banana', 'grapes', 'pear']
counter_list = list(enumerate(my_list, 1))
print(counter_list)
# Output: [(1, 'apple'), (2, 'banana'), (3, 'grapes'), (4, 'pear')]

5, initilize a multidimensional array

a) To get a one dimension array with all 0, below both ways will do:

>>> f = [ 0 for _ in range(2) ]
>>> f
[0, 0]

OR

>>> f = [ 0 ] * 2 
>>> f
[0, 0]

But per this link, careful — the second technique doesn’t generalize to multidimensional arrays or lists of lists. Which leads to the List of lists changes reflected across sublists unexpectedly problem.

b) to get a multidimensional array

>>> f = [ [0 for _ in range(2) ] for _ in range(2)]
>>> f
[[0, 0], [0, 0]]
>>> f[0][0]=3
>>> f
[[3, 0], [0, 0]]

Lambda Expression

Lambda expression is actaully an anonymous function. It’s pretty handy when I need a small function (one line of code) while I don’t want to take the trouble to write a formal one.

Assume I want a function that can return the value of the input integer minus 2 if input is positive, I can write:

def decreaseByTwo(x):
    return x-2 if x > 0 else x

x = decreaseByTwo(x)

While using lambda expression, it will be

decreaseByTwo = lambda x: x-2 if x > 0 else x
x = decreaseByTwo(x)

Lambda expression can be very useful wherever a function is needed to be a input parameter.

Detailed explanation is available at

https://www.w3schools.com/python/python_lambda.asp

Nested Function

Nested function is a function inside a function. It’s handy when you need to reuse a batch of codes but that reuse only make sense to your current function. At that moment, you can create a nested function inside your current function.

This is an example of a nested function. Inside parent(), a nested function child() is defined and can be invoked after its definition (but still inside parent()).

Introducing nonlocal

The function child() can read or assign a variable‘s value like

def parent():
  a = 3
  b = 9

  def child():
    print(a) #will print 3
    print(b) #will print 9

  child()

However, there is a situation that child() may want to change the value of a variable that is defined in parent() like below.

def parent():
  a = 3

  def child():
    print(a) #will print 3
    a = 5    
    print(a) # will print 5
  
  child()
  print(a) #will still print 3 although in child() it's set to 5

However, in above example, when a=5 is called, Python3 actually creates a local (only valid within child()) variable which is also named ‘a’ and shadows the external a in following executions within child(). But outside child(), a will still refer to outside one.

To ensure the ‘a’ inside child() using the outside one, I need to put “nonlocal” as below.

def parent():
  a = 3

  def child():
    print(a) #will print 3
    nonlocal a
    a = 5    
    print(a) # will print 5
  
  child()
  print(a) #will print 5 since in child() it's set to 5

One possible confusing part is what if I want to change an outside dict/list/other objects inside a nest function, do I need to claim “nonlocal” first? The answer is not since, like child() in below example shows, changing part of variable a is not a new assignment; but in child2(), I use “nonlocal” to completely change outside a instead of partially.

def parent():
  a = {'parent':3}

  def child():
    a['child'] = 2
    print(a) 

  def child2():
    nonlocal a
    a = {1:2}
    print(a) #will print {1:2}

  print(a) #will print {'parent':3}
  child()
  print(a) #will print {'parent':3, 'child': 2}
  child2()
  print(a) #will print {1:2}
  child()
  print(a) #will print {1:2, 'child': 2}

Collections

There are quite a lot of useful classes inside Python3 collection module. Per official doc, collections module

implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple.

What does that mean? Let me use 2 examples to explain:

1. defaultdict

Note: the first letter is in lowercase.

Assume I need to have a hashmap to count how many times a letter appears in a string. I can write below code.

s = '123ab'
m = {}
for c in s:
  if m.get(c) == None: #because c may not be an existing key in m
    m[c] = 0   #I need to initialize it first to avoid exception
  m[c] += 1  

However, it’s a little bit clumsy. Let me show the defaultdict version:

from collections import defaultdict

s = '123ab'
m = defaultdict(int)
for c in s:
  #if c is not yet a valid key, m[c]=0 will be called first
  m[c] += 1

2. Counter

For the example of generating a hashmap to count how many times a letter appears in a string, there is actually another more easy way as below.

from collections import Counter
s = '123ab'
counter_s = Counter(s)
counter_s # print Counter({'1': 1, '2': 1, '3': 1, 'a': 1, 'b': 1})
counter_s['z'] #print 0 since there is no 'z' key

Since Counter is a subclass of dict, I can easily use it to access each key and its value.

Useful Data Structures

1. Hashmap/Dictionary

In Python 3, a dict actually performs like a hashmap. A dict is composed of multiple key/value pairs in the format of key:value, a comman(,) is used to separate each pair. The dict can be initilized like

a={1:2,’strKey’:’strValue’}

Any hashable type can be key. Please note that list (like [1,2,3,4]) and dict (like {‘1’:2}) are not hashabel.

It’s easy to add a key/value pair, just

a[(1,2)]=(3,4)

And easy to remove a pair

del a[(1,2)]

For time complexity, adding or removing and accessing are all O(1) operations.

Iteration of dict elements:

d = {'parent':3, 'child': 4}

#access keys and then use key to access value
for key in d:
  print(key, d[key]) #each time a key/value pair of d is printed

#access key/value
for key, value in d.items():
  print(key, value) #each time a key/value pair of d is printed

#Typical incorrect ways to access key/value
for key, value in d:
  print(key, value)
for key, value in enumerate(d):
  print(key, value)

2. Tuple

According to Python — Tuples — Tutorialspoint:

A tuple is a collection of objects which ordered and immutable. Tuples are sequences, just like lists. The differences between tuples and lists are, the tuples cannot be changed unlike lists and tuples use parentheses, whereas lists use square brackets.

Tuple is very handy whenI need to just group a series of objects, for example, I can use a (x,y) tuples to represent a two dimension point while (x,y,z) to a three dimension point. It looks very logically and elegant.

As mentioned above, a tuple is immutable which means it can not be changed once defined. Look at below example:

a = (1,0)
print(a[0]) #this will print 1
a[0] = 2 #this will throw an error

3. List/Stack

A list is a collection of objects which are NOT immutable. Please compare below codes to the codes in above tuple section and note that square brackets ‘[]’ are used here in list definition while parentheses ‘()’ are used in tuple definition.

a = [1,0]
print(a[0]) #this will print 1
a[0] = 2 
print(a[0]) #this will print 2

Very often, list in Python3 is used as a stack. Data can be pushed to a stack or popped up. The only magic here is the first pushed data will be the last one to pop up (often referred as “first in last out” FILO). The next to-be-popped data stays at the top of stack. Normally a peek function is expected to take a look at the data at the top of stack without actually popping it up. Look at this example to get more understanding:

s = []
s.append(1) #here I use append to serve as push
print(s) #this will print [1]
s.append(2) #now s becomes [1,2]
s.append(3) #now s becomes [1,2,3]
a = s.pop()
print(a)  # it will print 3, which last in but first out
print(s)  # since 3 is popped, s is [1,2]
s.append(3) #now s becomes [1,2,3] again
print(s[-1]) # print 3, s[-1] is equal to peek
print(s)  # print [1,2,3], peek(unlike pop) will not change a stack

4, Heap Queue

Please note that this is a summary and extention with example of official document https://docs.python.org/3/library/heapq.html.

Within Python’s heapq, all elements are placed in a binary tree where any element’s value will be less than or equal to any of its children. Not surprisely, the root of the tree contains smallest value. So Python’s heapq is actually min heap which means on the top of the heap is always the smallest element.

Another fact is that an element can be a integer as well as a basic data structure like tuple. Actually, whatever data structure (like string) I can put inside a list can be an element’s type in heap. That’s why it can be used as Priority Queue as below example illustrates:

>>> from heapq import *
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

A heap queue can be initialized in 2 ways:

1. use a empty list (see above example)
2. use heapq.heapify(list)

>>> from heapq import *
>>> h = [(5, 'write code'),(1, 'write spec')]
>>> heapify(h)
>>> heappop(h) 
(1, 'write spec')
>>> heappop(h)
(5, 'write code')

Pleaes note that each time heappush/heappop is called (when a new element is added or removed), the heap is adjusted internally to againt ensure itself a min heap (therefore, each element is equal to or less than its children, and smallest one on the top).

There are 2 very useful functions in heapq:

heapq.nlargest(n, iterable, key=None)

heapq.nsmallest(n, iterable, key=None)

where key is a function of one argument that is used to extract a comparison key from each element in iterable. An example looks like below.

>>> from heapq import *
>>> h = [(1,4),(2,3)]
>>> heapify(h)
>>> nsmallest(2,a,key=lambda p:p[1])
[(2, 3), (1, 4)]
>>> nsmallest(2,a)
[(1, 4), (2, 3)]

Major heapq operations (heapify, heappush, heappop) has O(N) time complexity while some (nsmallest, nlargest) has O(1).

Some Leetcode problems (which aim to find top K smallest/largest elements) can be easily solved by using heap:

• Top K Frequent Elements - LeetCode
• K Closest Points to Origin - LeetCode

5. Dummy head of Linked List

In many cases, if I want to append a node to a linked list(which may not exist), I need to have an if/else like:

  head = None
  ...
  if head == None: 
    header = ListNode()
  else:
    preNode.next = ListNode()
  preNode = curNode
  ...
  return head

The reason is preNode can be None if the linked list does not yet exist. To make above code more concise and beautiful, there is a technique called dummy head: I don’t create the linked list when needed, instead, I will just go ahead and create the head and have preNode pointing to it so that preNode is always valid. Accordingly, I should remember the real data starts on head.next instead of head since the head is just a dummy placeholder. Compare below code snippet with the previous one to get a understanding of that.

  head = ListNode()
  preNode = head
  ...
  preNode.next = 
  preNode = curNode
  ...
  return head.next

To connect this technique to real world examples, I attach 2 practices of it as below.

• Leet Code 82. Remove Duplicates from Sorted List II — Graphically Explained Python3 Solution
• LeetCode 23. Merge k Sorted Lists— Graphically Explained Python3 Solution

Python3 Cheatsheet (continuously updated) was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.

Problem Description

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [2,2,3,0,4,-1,1,6], k = 7
Output: 3

Solution

Obvious Solution

There is certainly a brute force way. Iterarte the whole list, check the sum of (currentElement to currentElement+1), (currentElement to currentElement + 2), pesudo code looks like:

In total, there are 3 loops and make the time complexity O(N³). It should work but definitely not an efficient way. There are ways to optimize this since there are many duplication of computation and the complexity can be decreased to O(N²).

Best Solution (to me)

Obviously, each subarray will end up with some index. Let me use i to represent that some index. And sum(0 to i) is very easy (and cheap — just take O(N)) to get.

Look at below example at i = 4, sum(0 to 4)= X + K. That means sum(0 to 4) can be broken to 2 parts, the second part is what I desire(with the sum of K), the first part X is actaully another sum which accumulate from 0 to 1. Now there is some light: if I have sum(0 to i), I can assume there is an index j (where j<i) , check if sum(0 to i) - K occurs in previous sum(0 to 0), sum(0 to 1), sum(0 to 2)…sum(0 to i-1), and increase the counter when an occurance is found. The value of the counter is the number of subarrays ending with index i that qualify the sume of K. In below example for index = 4, only sum(0 to 1) + K = sum(0 to 4), then there is only 1 qualified subarray which is [3,0,4].

Please note that in some case, there could be more than 1 qualified subarray.

Again look into another example as followed. For subarrays that ending at index 5, there are 2 cases:

sum(0 to 2) + sum(3 to 5)

sum(0 to 1) + sum(2 to 5)

And sum(0 to 2) and sum(0 to 1) are equal (both to 0).

Therefore, I need a Hashmap to record all sum(0 to x) (as the key) and its occurance (as the value). When I have sum(0 to i), I can check in the hasmap the value of sum(0 to i)-K to get the occurance number, and that number will the subarrays that ending with index i.

There is one trick however, again with my first example, what if sum(0 to i) itself is already equal to K like below the qualified subarray [2,2,3]? At this moment, the breakdown is : sum(0 to 2) = 0 + sum(0 to 2). The trick I play is add {0:1} to the hashmap saying for sum of 0, there is by default 1 occurance.

Alright, now here comes the code.

Time & Space Complexity

As above illustration/code shows, the time complexity is O(N): it just goes through each element in the input array for once only and with the loop each operation is O(1).

When it comes to space complexity: there is a hashmap which can scale (in worse case) with the size of input array, so it can take up to O(N) space and hence the space complexity is O(N).

Python 3 knowledge points

Within the solution, hashmap is used. I put together a post Python Cheatsheet with a section hashmap. Click https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549 to view more cheats :)

Extended Reading/Thinking

What if you are asked to return all subarrays?

Leet Code 560. Subarray Sum Equals K — Explained Python3 Solution was originally published in Tech Life & Fun on Medium, where people are continuing the conversation by highlighting and responding to this story.