LeetCode 21. Merge Two Sorted List

This post explains how to solve leetcode problem – 21. merge two sorted list – using python 3. Let’s take a look at an example. Let’s say there are two lists: 1 -> 3 -> 5 and 2 -> 4. After merging those lists, the expected answer is 1 -> 2 -> 3 -> 4 -> 5. You are supposed to merge the list in sorted order. This problem doesn’t require any tricks but you just need to be able to operate on iterating and merging the list. With that said, the algorithm is very simple.
1. iterate nodes in each list at the same time until at least one list is completely consumed
2. push the smaller node to the result list (merged)
3. After #1, 2, if there is any left over from either of the list, just append to the result list

Let’s take a look at working solution here. In the solution below, I used a dummy node so that I can blindly set the next pointer without having to worry about if it’s first node or not. You just need to make sure not to return the dummy node.

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    merged = ListNode(-1)
    iter = merged
    while list1 and list2:
        if list1.val < list2.val:
            iter.next = list1
            list1 = list1.next
        else:
            iter.next = list2
            list2 = list2.next
        iter = iter.next

    if list1:
        iter.next = list1
    elif list2:
        iter.next = list2

    return merged.next

As you see in the solution above, I am iterating the two lists at the same time, setting the smaller value node to the result list. Once at least one list is completely consumed, I need to check if there are any leftovers and append them to the result.

Time complexity is O(n + m) where n is the length of list1 and m is the length of list2. Space complexity is O(1) since I don’t need any extra space.

LeetCode 206. Reverse Linked List

This post explains leetcode problem 206. reverse linked list using python 3. For example, let’s say there is a linked list: 1 -> 2-> 3-> 4 -> 5. After reversing the list, the expected result is 5 -> 4 -> 3 -> 2 -> 1. This is a fairly easy problem and there is a couple of ways to solve this.

Using stack

This method uses extra space (stack) as the name indicates. The algorithm is:
1. As iterating the original linked list, create the node and push it to the top of the stack. Note that the next pointer should be None
2. After #1, start popping the node from the stack. As you pop the node, connect it with previous (or next depending on your implementation)
3. After #2, you got the reversed linked list

Time complexity: O(n)
Space complexity: O(n) because you have to store all the nodes to the stack

This method is very simple and has pretty decent time complexity. However, even though time complexity is O(n), you are iterating each node twice: 1st when iterating the list, 2nd when popping from the stack. In addition to that, it also uses O(n) space complexity.

The question is, can we do better?

Optimized linked list reversal

We can actually reverse the list in a single traversal without using any extra space. Since code is quite simple, I will just show you the code first then explain.

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    reversed_list = None
    while head:
        next = head.next
        head.next = reversed_list
        reversed_list = head
        head = next
    return reversed_list

As you are iterating the original list, all you need to do is push the current node to the head of the new list. reversed_list is the head of the new list. While you are iterating the original list, save the next node because you are going to pop the current node from the original list and push to the head of the new list (line 4). At line 5,6 you are pushing the current node to the new list. Because you are setting the next pointer to the head of reversed_list, you are automatically disconnecting the node from the original list. At the line 6, it’s making sure to set the new head. Then you keep iterating by setting head to next node which was previously saved.

Time complexity is O(n) which is better than the method above because it only iterates the list one time. Space complexity is O(1) because it doesn’t require any extra space.

Python Context Manager

The purpose of python context manager objects is to control a with statement.
It is primarily used to make try/except/finally block simple.
The finally block exists to execute some code no matter what happens after try/except block, which is usually releasing some resources or clean-up.
Just like finally block, context manager objects actually do perform some block of code.

Context Manager Protocol

The context manager protocol consists of two methods: __enter__ and __exit__.
As you can imagine, __enter__ is called when the with statement starts, which is invoked on the context manager object.
The __exit__ method is called at the end of the with block.

Let’s take a look at a quick example.

class PrintName:
    """This class prints a string NYCOMDORI
    """

    def __enter__(self):
        print('NYCOMDORI ENTER')
        return 12345
    
    def __exit__(self, exc_type, exc_value, traceback):
        print('NYCOMDORI EXIT')
        if exc_type is not None:
            print("Exception happened")
            return True
            
>>> with PrintName() as pn:
	print(pn)

	
NYCOMDORI ENTER
12345
NYCOMDORI EXIT
>>> 

In the example, I just printed pn but you also see additional strings are printed.
I printed “ENTER” when __enter__ is called and “EXIT” when __exit__ is called.
Again, __enter__ is called automatically when with statement starts and __exit__ is called when with statement is done.

There is an important thing to note in this example.
The __enter__ method is invoked on the context manager object – PrintName.
However, pn variable is actually whatever __enter__ returned! In this case, it’s a number 12345.
It means that the context manager object is the result of evaluating the expression after with but pn is the result of calling __enter__ method.
It also implies that as clause is completely optional.

For the last, I just would like to briefly explain exception handling and the parameters in __exit__ method.
Please refer to the python document for more explanation.

please note that I explicitly returned True in order to suppress the exception.

The default behavior of handling exception for __exit__ method is:
1. check if a value is returned from __exit__ method.
2. if nothing is returned, essentially None will be returned, then it will assume exception is not handled properly and will propagate the exception.

The parameters are all related to handling exceptions within the with block.

exc_type: The exception class
exc_value: The exception instance
traceback: A traceback object

Here is another simple example that uses as clause – popular file open example.

>>> with open('test.txt') as f:
	f.read(20)

'This is a test file'
>>> f
<_io.TextIOWrapper name='test.txt' mode='r' encoding='UTF-8'>
>>> f.encoding
'UTF-8'
>>> f.closed
True
>>> f.read(20)
Traceback (most recent call last):
  File "<pyshell#9>", line 1, in <module>
    f.read(20)
ValueError: I/O operation on closed file.

As you can see, although f is still available after with block you cannot do any I/O operation since it’s closed.
And now we all know that f is the result of calling open().

@contextmanager decorator

Although context manager objects could be very useful and handy you might feel lazy to implement __enter__ and __exit__ methods every time.
To make your life simpler, contextlib utilities actually provides a convenient decorator for you, which is called @contextmanager.

The decorator actually lets you build a context manager object from a generator function that you implement.
I understand this might be a little confusing at first glance because generator functions are usually used for iterators or generator expressions.
However, in this case, @contextmanager decorator only requires a single yield because it is only used to split the body of the functions in two parts.
All the expressions before the yield will be used when __enter__ method in the decorator is called.
And the other half, after the yield, will be called when __exit__ method is called.

It is actually quite convenient util provided by the python standard library.
It will be very obvious once you look at the example.

from contextlib import contextmanager

@contextmanager
def print_name():
    print('NYCOMDORI ENTER')
    try:
        yield 12345
    except:
        print('exception happened')
    print('NYCOMDORI EXIT')
    
>>> with print_name() as pn:
	print(pn)

	
NYCOMDORI ENTER
12345
NYCOMDORI EXIT

Using @contextmanager decorator yielded exactly the same result as PrintName class with a much simpler implementation.
Let me add some more explanation about the above example.

The generator function you implemented will be wrapped by the decorator.
The wrapper class actually implemented __enter__ and __exit__ method which calls part of the generator function when the methods are invoked.
As __enter__ method is invoked, it will call the generator function and holds the result to a variable (value returned by yield statement).
Then, it will call next function to invoke yield of which value will be bounded to a target variable.
Then, it will execute whatever is in with block.

The __exit__ method will be called once with block is done, which will first check if an exception was passed (as exc_type).
If that’s true, it will raise the exception in the yield line inside the generator function.
If an exception was not passed in, call next to resume executing the rest of the code after yield in the generator function.

That’s why I guarded the yield line with try/except to protect from an exception raised inside with block.
Please note that nothing is returned when handling exceptions.
It’s because by default @contextmanager assumes the exception is handled and should be suppressed.
You need to explicitly re-raise the exception if necessary.

Conclusion

In this post, I explained about context manager objects and how to implement them in two ways – one explicitly implementing the class with __enter__ and __exit__ methods and the other using @contextmanager decorator which conveniently implements the methods for you.
With context manager objects demystified you should feel more comfortable with using it.
Thank you for reading the post!

Python – best practices using else block

Typical use case of else block is with if in many programming languages.
It usually serves as branch control such if it doesn’t meet certain conditions in if block it will just execute else block instead of if block.
And it is the same case for python else block too.

However, python extended else block usage more than the above.
In python, you can actually use else block not only with if but also with for, while, try blocks.
In that case, the name – else – could be quite misleading when used with for, while, try blocks.
Since we automatically think of if-else we might think it will execute some code inside else block if for, while, try fails.
But it is not the case.

Using else block with for, while, try blocks means to execute code inside else block after executing for, while, try blocks.
In that case, I personally think the name ‘then‘ is more appropriate but for some reason else is used there.
For that reason, I think it is generally recommended not to use else block after for, while loops to avoid any miscommunication.

Regardless, I will still explain else block for each case with examples.

for/else

The else block will run only if for loop completes entirely.
It means that else block will not run for some cases. (i.e. for loop exits with break statement)

Code Example

for i in range(5):
    print(f"loop value:{i}")
else:
    print("else block")
    
# output
# loop value:0
# loop value:1
# loop value:2
# loop value:3
# loop value:4
# else block

for i in range(5):
    print(f"loop value:{i}")
    if i == 3:
        break
else:
    print("else block")
    
# output
# loop value:0
# loop value:1
# loop value:2
# loop value:3

Again, I personally think this is pretty confusing and do not recommend to use it.

while/else

The else block will run only if while loop exits because its condition became false.
Just like for loop, if while loop exits because of break, else block will not run.

counter = 0

while counter < 2:
    counter += 1
    print(f"counter: {counter}");
else:
    print("else block")
    
# output
# counter: 1
# counter: 2
# else block

counter = 0

while counter < 2:
    counter += 1
    print(f"counter: {counter}");
    if counter == 1:
        break
else:
    print("else block")

# output
# counter: 1

While loop is basically the same as for loops and I do not recommend to use while/else together because it looks counter-intuitive.

try/except/else/finally

As you may already know EAFP – easier to ask for forgiveness than permission – is typically considered as more pythonic.
Because of that reason try/except is actually pretty commonly used not only for error handling but also for flow control in python.

At first glance, it seems to be redundant to put else block after try/except.
However, it actually does add some correctness, readability, and clarity.

Let’s take a look at the example below.

try:
    call_may_raise_exception()
    process_no_exception()
    release_resource()
except IndexError:
    print("exception happened")

This python code calls three functions: call_may_raise_exception(), process_no_exception(), and release_resource().
The first function does something and may raise an exception.
The second function just processes some data and does not raise any exception.
The third function releases some resources after all the work.

Now, we probably want to call release_resource no matter what to avoid any leaks.
So it makes sense to put release_resource() function call under finally block like this.

try:
    call_may_raise_exception()
    process_no_exception()
except IndexError:
    print("exception happened")
finally:
    release_resource()

But what about process_no_exception() function?
Strictly speaking, process_no_exception() function should not be placed inside try block since it’s not going to raise any exceptions.
But at the same time, we want to call it before release_resource() only if there weren’t any exceptions.
That’s where we can use else block.

try:
    call_may_raise_exception()
except IndexError:
    print("exception happened")
else:
    process_no_exception()
finally:
    release_resource()

It’s not only correct but also more readable.
The else block makes it clear call_may_raise_exception() function needs to be guarded against and process_no_exception() will be called only if there weren’t any exceptions raised from call_may_raise_exception() function.
In the end, release_resource() is called no matter what.

The else block with try/except/finally is actually recommended since it adds correctness, readability, and clarity.

Conclusion

Python supports else block after for, while loops and try/except.
However, it is not recommended to use else with for/while loops.
Although it seems redundant to use else with try/except the else block actually adds some benefits and is recommended to use with them.