Writing
-
Leetcode: Merge sorted array
Continue readingGiven two lists or arrays,
nums1andnums2as well as two integersmandnwhich give the length of the arraysnums1andnums2respectively.nums1should be modified in place.The first idea that came to my mind was a merge-sort. Given that those initial arrays are already sorted, I could have two pointers and iterate over both arrays simulatenously, copying the values into a third one. The problem here is that the array should be modified in place. The way to achieve this in
O(2(n+m)) => O(n+m)is to iterate over the temporary array and write it back to the initial array. -
Leetcode: Word search
Continue readingGiven a two-dimensional array with english upper- and lowercase letters, named
boardand aword, returnTrueif the word appears on the board and false if not. We can go up, down, left, and right but not diagonal. Letters cannot be used twice.When looking at this problem, it helps to imagine the
boardas a tree. Every letter is a potential root of the tree, depending if it is equal to the start of the word that we are looking for. This allows us to apply a slightly modified version of the breadth-first-search algorightm (BFS). -
Leetcode: Unique paths
Continue readingGiven an
m * ngrid, we start in the top left corner at position(1,1). We want to move to the bottom right corner with eitherrightordownsteps. How many different combinations ofrightanddownare there for a given grid of sizem * n? We need to find an algorithm that works on arbitrarily large grids.Given this example grid of
(2,3):+---+---+---+ | S | | | S = Start +---+---+---+ | | | F | F = Finish +---+---+---+There are
3different ways from start to finish:- Down, Right Right
- Right, Down, Right
- Right, Right, Down
To simplify this problem, we can think of a down move as
1and of a right move as0. This shows us, that we can either do100,010, or001. We observe that the one is in every position. Now, two different down moves are identical, hence there are less than2^nsolutions.If we think of this problem as a backtracking problem, we can come up with a recursive algorithm. At the first position we can go either down or right. Depending on which way we go, we have to shrink the field either on the x or y-axis. We then add the result of going right to the result of going down. This step is repeated until we can only go down or right in which case we can return
1. -
Leetcode: Merge intervals
Continue readingGiven an array of intervals of the form
[start, end], merge all overlapping intervals and return an array of non-overlapping intervals.One example is the following array
[[1,2], [3,4]]. There is no overlap here. Hence the result is the same as the input. Another example is[[1,2], [1,4]]. They are overlapping and the result is[[1,4]]. If the start number of the next element is the same as the end number of the previous element, the items should be treated as overlapping.One possible solution is to first sort the items by start element. This can be achieved with an in-place sorting and a
lambdaexpression:intervals.sort(key=lambda item: item[0]). -
Leetcode: Remove nth node from end of list
Continue readingGiven the
headof a linked list, remove thenthelement from the end of the list and return the head of the list. As a follow-up, this should be done with one iteration.The most obvious solution is to count the number of elements in the list in one iteration. This is necessary, because we don’t know initially how long the list is. Then iterate over the list again and once the index is reached, set
pointer = pointer.next. This way thenthelement is skipped.However, there is a more elegant way to achieve this.