Posts

Very quick post about finding the peak element in an array. This is LeetCode problem 162. We have an array nums with \(n\) integers and want to find the index of one of its peaks in \(O(\log n)\) time. The important detail is this: no two neighboring elements have the same value. Let’s dive in! Solution To solve this in logarithmic time, we will use binary search. We start with a left index and a right index. We then compute a mid point mid = (left + right) / 2. Now we investigate what the local behavior around mid is. If nums[mid] > nums[mid + 1], it means that there’s no point searching for the peak at mid + 1 or to its right, so we set right = mid. Otherwise, there’s no point in searching for the peak at mid or to its left, so we set left = mid + 1. ...

Welcome back to another LeetCode walkthrough! Let’s look at LeetCode problem 714. We’re given an array of stock prices. Each day, we can either buy a stock if we have none or sell a stock we own (but not both). When we sell a stock, we have to pay a transaction fee. We want to find the maximum profit we can achieve. We approach this using dynamic programming. Let’s dive in! ...

Welcome back to another LeetCode walkthrough! This time, we’ll be tackling LeetCode problem 1268. We’re given an array of strings called products, as well as a string searchWord. Our goal is to suggest three products after typing each character of searchWord. This is a tiny autocompletion method! We could solve this problem with a Trie, like the one we implemented to solve LeetCode problem 208. Check it out! But today, I felt like solving this without writing hyper-optimized or over-engineered code. Our solution will be simple and straightforward… but still efficient! Let’s dive in. ...

I’ve been learning about CUDA C++ programming this week, following this blog post by Mark Harris. What makes CUDA useful is its ability to execute many computations in parallel instead of sequentially. The linked blog post demonstrates how it can add two very large vectors with a size of 1 million elements each. I’ll present the most interesting code snippets in an approachable way and show how very similar code can perform vector-vector dot products. You can see the full code in my repository here: https://github.com/davidnabergoj/cuda-programming. ...

In this post, we’ll be solving LeetCode problem 1143. We have two strings text1 and text2 with sizes \(n\) and \(m\), respectively. We want to find the length of their longest common subsequence (LCS). A subsequence of a string s is obtained by deleting zero or more characters from s. Strategy Let’s assume we have two strings: s1 with size n1 and s2 with size n2. Let’s also assume we know their LCS length. What can we say about LCS length when we append a character c1 to s1 and a character c2 to s2? ...