Forem: Duncan McArdle

What is LeetCode, and why do I post solutions to it on online?

Duncan McArdle — Wed, 09 Mar 2022 16:22:52 +0000

A few months back, I entered the crazy world of LeetCode.

What is LeetCode

For those of you who don’t know, LeetCode is a site that posts thousands of coding problems at varying difficulties, and asks you to solve them, whilst providing various test cases that your solution must pass. Additionally (and in my opinion most valuably), LeetCode also has a big community of users who share and comment on solutions to said problems.

LeetCode’s most common user is someone seeking employment at one of the world’s biggest tech companies, all of whom utilise coding problems (AKA algorithmic coding) as a means of picking out the best candidates in the thousands of daily applicants they receive.

Now, the rationale here isn’t that you need to be able to come up with complicated algorithmic solutions in order to work at Google or Facebook, but rather that by learning such algorithms and applying them whilst interviewing, you show that you’re willing to go above and beyond to get the job. It’s a bit like asking 100 people interviewing to be a chef to count to 1,000,000 — you may never actually need to do it, but by trying (and potentially succeeding), you’ve differentiated yourself from the rest of the applicants.

Now that isn’t to say that you won’t ever use the kind of complex algorithms and data structures you find on LeetCode in the real world. In fact, there are some concepts, such as “Big O Notation”, that really can change your day-to-day work as an engineer. In addition, depending on the team you end up working in, graph traversal or LinkedList manipulation may be as common a task as writing unit testing. These companies aren’t saying you will use such methods during your time with them, but they want to know that if they need you to, you can.

Why would I want to share LeetCode solutions?

To some, the act of posting a solution to a problem on the open internet may seem a little odd. It’s a bit like posting the answers to a test; yes readers will be able to answer the questions, but if they're asked an even slight variation of the original question, they’ll be stumped.

But in reality, these problems rarely have a single correct answer. In fact, the process is typically more about identifying methods and applying concepts than it is arriving at a single correct solution. Even if you do provide a perfect solution, and one that beats out every other submission in terms of timing, you still might find another solution in the comments that makes you say “Oh, that’s a much better way of doing it!”.

To give you a great example; this LeetCode problem asks you to find all pairs of numbers in an array that add to a given number. The most obvious solution to me was to loop through the array twice (one inside the other), and add all possible pairs together. This solution worked, was pretty quick for the example case of 4 numbers, and was easy to understand. But lo and behold, my submission was incredibly slow compared to others, unusably so with a bigger dataset. So I quickly jumped into the discussion and found a method that’s infinitely better; (Hash)Maps! Now not only do I have a better solution to submit, but the next time I’m writing similar code in my day-to-day work, I stop and think; “Would a Map be better here?”. None of this would be possible without sharing solutions.

Why I started posting the solutions online

So we’ve established what LeetCode is, as well as why you might share solutions for their problems. But why, you may be thinking, post them online?

1. Because the LeetCode discussion section is… meh

Although a fantastic resource for finding solution and guidance, at the end of the day the “Discuss” tab on each LeetCode problem is a fairly typical, short-form post and reply system. The vast majority of responses are short, most submissions are uncommented and underexplained, and generally speaking the whole thing is geared more towards people who are already familiar with the process, and are looking to say “Oh that approach is a little better” rather than “How on earth do I even start to solve this?”.

Now, that isn’t to say that every discussion is like this. Some users go out of their way to take you through their solution step-by-step, some post video walkthroughs, and some just comment their code extensively. There are plenty of great posters on LeetCode who do not fit the description above.

2. Because it helps me learn (and not cut corners)

When faced with a difficult problem on LeetCode, I will often (after staring at the wall for ~10 minutes) switch to the “Discuss” tab and start looking at solutions. If I’m lucky, I’ll soon have a working submission inspired by another poster, and can move onto the next problem.

But the issue here, is that taking this shortcut often leads to under-understanding a solution. Instead of coming up with it organically, and understanding the full process from start to finish, I only really understand how the solution solves the problem (it’s a bit like saying “I know 2 + 2 = 4, but I don’t know why”).

The fix I have come up with to this issue is to write up my solutions in a way that can guide others from start to finish. What this means is that I have to be able to fully understand the solution, in a way that would have allowed me to solve it from scratch, and to a depth at which I am capable of explaining it to the next person in the chain.

It is a strange situation where in order to understand something, I must be able to teach it to others, and I’ve found this really works for me.

3. Because I like writing

As a long-time amateur writer, and frequent online poster on a variety of formats, I enjoy the act of writing. Typically this has been via fiction, but I’ve found it interesting explaining technical solutions in written form, and as per my point above, have found that writing it out aids my own understanding at the same time.

When will I stop?

There are currently almost 2,000 problems on LeetCode. I’ll be surprised if I ever write up 10% of them, not least because beyond that point you’re often repeating the same approach in a slightly modified way.

In truth; I’ll probably stop writing up LeetCode solutions when it stops benefitting me to do so, though it sounds a little selfish to put it that way, doesn’t it?

LeetCode problem #5 — Longest Palindromic Substring (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 16:05:18 +0000

In this LeetCode challenge we’re asked to find the longest palindrome in a given string (a palindrome being a sequence of characters that is the same backwards as it is forwards, such as “bob”).

Now you might be inclined to think that the solution to this is simply to look at every character, and then move outwards until the characters no longer mirror each other. However, whilst this would work for a string like “aba”, it would not work for a string like “abba”, so we need to look for mirrored characters both by individual letter, and by letter-couple.

Solution #1: Loop, call twice, and store globally

Not a catchy title I know, but as this is my only real solution a catchy name seemed unnecessary!

In this solution, we loop through all characters in the string, and for each one, we begin checking for palindromes both on the current character and on the current character-couple. For each palindrome found, we check if it’s the new longest one, and store it if so.

This solution works great, and is pretty quick. In fact, the only way I’ve found to improve its performance is to replace the somewhat expensive string storing operations with pointer storage instead. In other words, instead of storing (and subsequently overwriting) the longest palindromes found each time, we instead store (and overwrite) pointers to the start and end of the longest palindrome. As you can imagine, once we get seriously long strings, this really starts to improve performance (at the cost of readability).

LeetCode problem #4 — Median of two sorted arrays (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 16:02:38 +0000

In this LeetCode challenge we’re provided with two ordered arrays, and asked to find the median value.

Just to clarify, the median is the middle value. So for example, the median of the array [1,2,3] would be 2. However, if there are an odd number of values, then the median is the average (mean) of the middle two values. So in an array of [1,2,3,4] the median value is the average (mean) of 2 and 3, which is 2.5.

Solution #1: The power of JavaScript

Okay, so this is kind of like cheating. With JavaScript, we can concatenate (combine) the arrays, sort them into ascending order, and then just pluck out the middle number(s). This makes things incredibly simple, but isn’t all that efficient:

Solution #2: Looping to the middle

I came up with this idea while trying to crack the “correct” approach (see below). Basically, we start by figuring out the middle point of the combined array, and then we loop towards that point, pulling in the lower value of each array as we do, 1 element at a time, until we reach the middle. Once we reach the middle, we know we’re at the median.

This approach is actually really quite efficient (faster than 97% of JavaScript submissions at the time of writing), but isn’t particularly mathematical, which is what most submissions on LeetCode seem to suggest.

Solution #3: The “right” approach (binary searching)

I’ll be honest and up front here: I do not like this solution at all. Despite being elegant and (eventually) understandable, it’s just not what good programming is to me. If I were to ask someone during an interview to solve this problem (which I would never do), I would be perfectly happy with them spending 5–10 minutes on providing me with either of the above two solutions. Watching them struggle for 45 minutes on this approach would have no value to me.

As a matter of fact, even though I do now, after many hours, finally understand this approach, I just don’t see the point in me writing one out. Instead, this fantastic video will take you through the math behind it and provide some code, in far simpler terms than the “Solution” page on LeetCode.

https://www.youtube.com/watch?v=LPFhl65R7ww

LeetCode problem #3 — Longest substring without repeating characters (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 16:00:11 +0000

In this LeetCode challenge we’re asked to find the length of the longest string of characters in a provided string that does not contain repeating characters. In other words, in the string hello the longest substring without repeating characters is hel (with a length of 3).

The main method for solving this problem is with a “moving window”, and all of the below approaches use some form of this.

Solution #1: Double-loop with a Set

This was my first and by far least sophisticated method. In it, we loop once through all characters in the provided string, and then for each one we loop through the remaining characters, adding each one into a Set until we find a repeating character. At that point, we check if its the longest string found so far, and store its length if so. This repeats until the end of the string until we have found our longest substring.

Solution #2: Array

This solution is similar to the above, but instead uses an array to store the running string, which has the benefit of being ordered, and having the splice and indexOf functionality that make this solution particularly easy on the eye and removes the need for the nested loop.

Solution #3: Map

LeetCode user nilath posted this great solution using a Map, which I have adjusted to improve readability. It takes the moving window concept but utilises Maps for lightning-fast lookups. Interestingly, because a Map is a key-value pair, we’re able to use the letter as the key, and the position that it sits within the string as the value:

Solution #4: Set

This solution was inspired by jeantimex’s Java solution, and builds upon the Map concept but simplifies things slightly to use a Set instead. This has the benefit of reducing code complexity, but arguably damages readability:

Comparing the solutions

All approaches (excluding the double-loop) are of similar performance, and vary between tests enough to make them negligible:

What is interesting however is that LeetCode’s processor is so optimised for array work that if you start all of these approaches by first converting the string to an array (using string.split('')), you’ll see performance gains across the board.

LeetCode problem #2 — Add two numbers (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 15:58:28 +0000

In this LeetCode challenge we’re asked to add together two numbers. Seem simple? Well it isn’t. Of course, it’s a lot simpler than the way it’s explained on the page, but I suppose that’s a matter of opinion… however I encourage you to read the official one first.

Head hurting? Good stuff. Here’s my translation: Given two linked lists, which each represent a number in reverse order, add them together, and return the answer in the same format (a reverse-ordered linked list).

Solution #1: Converting the lists to numbers

My very first instinct on this question was to convert the linked lists to their numerical counterparts, reverse them, add them together, convert the answer to a reverse-ordered linked list, and then return it. So here is what I came up with:

First we establish a function to convert a reverse-ordered linked list into an array of digits, which we call ConvertReverseListNodeToArray. What this function does, is that it takes a linked list, and recursively works its way through the list until it reaches the end, adding each value to an array as it goes. In addition, because we add each layer after the next layer in the list, we end up (intentionally) reversing the original order.

Next up, we convert both lists using the above function, .join() them into numbers, and add them together to get the numerical answer… which we must now convert back into a reverse-ordered linked list.

First up on the back-stretch, we convert the total number to an array for easier traversal. Next we loop through the array, creating a ListNode for each number and adding it to an overall linked list. Once again, because of the order in which we’re doing this, the new list ends up being an (intentionally) reversed version of the original array.

So there you have it, a somewhat straightforward and more mathematical approach to the problem.

Solution #2: While loop

This approach is based on a solution posted by LeetCode user cosde. It works by running a while loop, which continues until all list elements have been traversed. On each iteration, it adds the two values together, checks if there’s a carry value (if the total exceeds 10), and if so passes it to the next iteration. Very elegant, and highly readable:

Solution #3: Recursive function

Another approach that I really liked was to use a recursive function with an optional parameter. This approach was originally posted by anhduc130, with my only alterations being to improve readability. It’s similar to the while loop approach above, but… without the while loop!

The way this approach works is that it makes use of JavaScript’s arguments object, which contains all the arguments passed into a function, even if they weren’t specified in the function header. The reason this is important is that LeetCode already specify the function header, and this can’t be changed, but by using the arguments variable we’re able to get around this. Now, as has been posted in the comments to the above solution, there are potential edge-case issues with this approach, however it does pass on LeetCode, and looks really great:

For each call of the function, it first adds the two ListNode’s values together (if they exist), as well as any value carried over from a previous run (again if it exists), and then calls the function again on the next level of the ListNodes (if they exist), optionally passing a carry value to also be added in (if that exists!).

LeetCode problem #1 — Two-sum (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 15:55:47 +0000

In this LeetCode challenge we’re asked to find two numbers in a given array which add up to make a specific number. So in other words, given the array [1, 2, 3] and a target number of 5 , we would return [2, 3].

Disclaimer: We’re actually asked to return the indices of the numbers, not the numbers themselves, but the above made for a much simpler explanation!

This challenge has a variety of solutions, and all revolve more or less around the same concept: For each number in the provided array, check if the complement to each number exists, and if so return the number and its complement.

Wondering what the complement is? In this case, it means “The number that, when added to the current number, makes the target number”. So for example, if you have 3 and need 5, your complement will be 2, because 5 - 3 = 2.

Solution 1: Nested for loop

Here’s a super straightforward example used a nested loop:

In this example we loop through all of the numbers, and then for each number, we once again loop through all of the numbers (excluding the first one, as the question states we cannot use the same number twice), and check if the second number is the required complement to the first one.

This solution works fine, but nested loops like this are slow and generally frowned upon, so let’s look at some other approaches.

Solution 2: Maps

In this example we declare an empty Map and then loop through the array of numbers. For each number, we check if the required complement exists in the Map, returning both numbers if so, or we add the current number into the Map. By the time the loop has reached the end of the array, we then have a map of all values provided (assuming the solution hasn’t already been found).

Maps are incredibly quick for looking up data, so this solution is much faster than the nested for loop approach, but surprisingly it’s not the most common solution I see to this type of answer.

Solution 3: HashMap / Object lookups

Note: In JavaScript, Objects are not straight up HashMaps, but they’re often referred to as such.

In what is a near-identical solution to the Map approach, this method stores the numbers one-by-one in an object, which then allows the program to lookup the value using an object key, rather than looping. This means that — again similar to Maps — we can look up our complement, rather than looping through all of the data to find it.

Comparing the solutions

In reality, both the Map and Object solutions are very similar in terms of performance, and this shows when benchmarking the approaches:

The actual performance of Maps vs Object lookups varies depending on a lot of things, and as JavaScript engines evolve to prioritise one or the other, this will swing back and forth. The stats above are taken directly from LeetCode, and are based on the specific test cases they supply, so as always, your mileage may vary!

One thing that is clear though, is that a nested for loop is a very bad idea.

Sorting algorithms 101

Duncan McArdle — Wed, 09 Mar 2022 15:47:28 +0000

In the world of programming, there are many ways to sort data. For the average engineer, you might just use .sort(), perhaps with a slightly modified sorting function to return your data in a specific way. But that’s probably about the most you do.

If however you’ve ever taken an algorithms class, used LeetCode, or just dived down a little deeper into sorting performance of a platform, you’ve probably heard of sorting algorithms.

Now, make no mistake, your favourite language’s .sort() (or equivalent) already uses one of these algorithms. In fact, if we’re being honest, it probably uses it in a way that’s faster than what you’re going to write anyway. But that doesn’t mean you won’t occasionally come up against a situation where writing a custom-sorting algorithm wouldn’t benefit you.

So, in this article, I’m going to give a quick overview of the most common sorting-algorithms out there. Over time, I’ll be posting more implementation articles for sorting, and will add links to them here.

Stable vs unstable sorting

Before we dive in, a quick note on stable and unstable sorting. In the sorting world, we’ll often come up against multiple instances of the same value. In the array [1, 5, 7, 5, 3, 5] for example, we’ll encounter 5 three times, and so our algorithm may be doing wasted work on comparing such values together and (potentially) rearranging them.

In a stable sort, our duplicate values will remain in their original order, with no time spent rearranging them for no reason.

In an unstable sort, our duplicate values will be rearranged, with time having been spent on this during the sort.

Below is an example of this, with letters added to the duplicate values to indicate the order pre and post-sort (these letters would not be in the real data and would thus have no bearing on the actual sort):

Stable sort: [1, 5a, 7, 5b, 3, 5c] → [1, 3, 5a, 5b, 5c, 7]

Unstable sort: [1, 5a, 7, 5b, 3, 5c] → [1, 3, 5c, 5a, 5b, 7]

1. Quick sort

This algorithm relies on a simple premise; we sort a single value in an array of data, and then another one, and another one, until we sort the entire array. Each time we do this, we mark the now sorted point as a “pivot”, move all numbers lower than it to its left, move all numbers higher than it to its right, and then repeat the algorithm on either side of that point.

Quick sorts are great if you want to do an in-memory sort, as we are constantly swapping existing data, but picking the “right” pivot point can be the difference between a fast and slow sort. In addition, this algorithm is an unstable one.

This algorithm has a typical time complexity of O(n log n), but a worst-case of O(n²). The space complexity however is just O(log n).

Note: You can see my post on quick-sort implementations here.

2. Merge sort

Here we split our to-be-sorted data into 2, right down the middle. Then, we run each half through the merge-sorting algorithm again, where it will be split recursively until we have just 2 pieces of data (1 on each side). From there, we re-combine each side in sorted order, until we eventually return to the top level with a sorted dataset.

This algorithm is fast, but as it involves re-creating data and lots of moving around, its perhaps not as fast as some others. It is however highly customisable and a personal favourite of mine. Oh, and it’s a stable sort, too!

Merge sorts have a time complexity of O(n log n), but a space complexity of O(n).

Note: You can see my post on merge-sort implementations here.

3. Bucket sort

In this algorithm, we divide our dataset into ordered buckets, sort each bucket, and then concatenate the buckets to give us a fully sorted set. This can make for a very elegant solution, especially if we pick the right number of buckets, however just like with quick-sort, picking the wrong number of buckets can slow things down significantly.

It’s also worth mentioning that once we’ve split our data into buckets, we still have to sort each bucket. This may be done with a recursive bucket sort, or we may combine bucket sort with another algorithm (common implementations seem to involve combining bucket and insertion sorts).

Bucket sorts can be fast if we pick the right number of buckets, and are also very easy to understand and implement. In addition, they are a stable sorting method.

Bucket sorts have a typical time complexity of O(n + k) (where k is the number of buckets), but a worst case of O(n²). The space complexity if O(n*k) in the worst case.

Note: GeeksforGeeks does a great 3 minute video on bucket sort here.

4. Bubble sort

In this sorting algorithm, we are simply comparing values with their immediate neighbours. The way we do this is that we loop through the dataset, and we compare the value at i with the value at i + 1 . If i is higher, than we swap the two values and increment i. After the first run, we will have identified the biggest value in the data, and moved it all the way to the right. Now on the next run, we will identify the second biggest value, and can ignore the already correctly placed value at the end of the array.

Bubble sort is an easy and intuitive algorithm to implement. It performs the sort in-place, and is stable.

In terms of complexity, the worst case for time is O(n²), however the space complexity is a wonderful O(1).

Note: Michael Sambol does a great 2 minute video on bubble sort here.

5. Insertion sort

Much like with bubble sort, insertion sort loops through the values of an array, but this time it compares it with the number to its left. If the left-hand number is lower, then those two values are sorted (for now), and we move onto the next one. Once we find a value that is not lower than the one to its left, we loop through the values on its left until we can find (and place it in) its correct position.

Insertion sort is once again a very easy algorithm to implement, and is also a stable one.

For complexity, insertion sort has a worst-case time complexity of O(n²) (where the original data was presented in descending order and thus every value has to be swapped), but has a space complexity of O(1).

Note: Michael Sambol does a great 2 minute video on insertion sort here.

And beyond

There are a huge number of additional sorting algorithms out there, and I hope to add more to this article in the future.

Quick Sort (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 15:42:01 +0000

Quick sorting is a sorting algorithm that focuses on placing a single value of an array in its correct position for each iteration. It does this by splitting the array at a pivotal point (called the pivot), and then moving all numbers greater than that pivot to be after it, and all numbers less than the pivot to be before it.

For example, given the array [3, 7, 4, 5, 9], you might select a pivot point of index 3 (which has a value of 4 in the above array). You would then go through each number and ask “Is it greater than or less than the pivot?”. In the above example, 3 would be less and so remain as-is. 7 would be greater and so be pushed beyond the pivot. 5 and 9 are then both greater and so remain where they are. So what we’re left with is an array of [3, 4, 7, 5, 9], where the pivot number (4) is now in the correct place in the array.

From there, we can then repeat the process on the values either side of the array recursively, until every value in the array is correctly placed.

In my opinion, quick sort isn’t a great method of sorting. There are far too many arbitrary aspects for how your code can work that make it less of an algorithm and more of an idea, and that makes implementation difficult to understand, as everyone has a slightly different method. In addition, it doesn’t resemble any real-life method of sorting, so I find it a little less intuitive than most. That said, most implementations do share key concepts, so if you can learn those, it makes everything a little bit easier.

In addition, although not my favourite in terms of how it works, what I do like is that it performs the sorting operation in-memory, something you may sometimes be asked to do specifically.

Below are two similar but different methods of implementing quick sort in JavaScript. Both follow the same pattern; we choose a pivot, split the array in 2 (one side with values less than the pivot, the other side with values greater than it), and then repeat the process for each part, until we eventually have a sorted array. Both also have the same final step; after sorting the non-pivot contents of the array, we then place the pivot in between both sides, so as to “correctly” place it.

Method #1: For loop

In this method, we make our pivot our right-most element (so as to make the for loop more readable, as it can still go left-to-right). Then we loop through all of the elements in the array, and move those lower than the pivot to the left hand side, and those greater than it to the right hand side. Finally, we place the pivot in the middle of all these numbers (technically, we swap it for the lowest number that is greater than the pivot), and we have then found the correct placement for the pivot.

This method was inspired by this great video from mycodeschool, which I recommend you check out once you grasp the above.

Method #2: While

In this method, we make our pivot the left-most element. Next we place markers at the next element in the array, and the final element of the array. Now, we move the left-marker right until we find a value that is greater than the pivot, and we move the right-marker left until we find a value that is lower than the pivot. In other words, we constrict the window of observation until we find numbers that belong on the opposite sides. Then we swap these values, so that they are now on the correct sides, and then continue until our markers meet. Finally, we place the pivot in the middle of all these numbers, and we have then found the correct placement for the pivot.

This method was inspired by this great video from Abdul Bari, which I recommend you check out once you grasp the above.

Merge Sort (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 15:39:11 +0000

Sorting data is a notoriously slow process. In real life, if you’re given a list of 10 numbers and asked to sort it, you’ll probably first look through all the numbers for the lowest one, then you’ll look through them again for the next lowest, and you’ll repeat this process until you’ve covered everything.

A lot of the time in code, it’s a similar story. You’ll loop through the numbers, and then for each number, you’ll compare it with all of the other numbers. Slow and inefficient.

Enter “merge sort”, a concept where we split our to-be-sorted data in two, sort each half, and then merge those two halves together.

Now, that probably doesn’t sound terribly intuitive at first. After all, we’re still having to sort each half, so how is that any easier? Well, the key differentiator is that we actually keep splitting our data in half until we have just 2 elements, at which point, we simply compare them to each other in order to sort them.

So let’s imagine we now have two sorted halves. Well, rather than loop through every possible number like we originally had to, we now only ever need to compare the lowest number of each half. For example, if we have sorted arrays of [1, 4, 6, 7] and [2, 3, 5, 8], we can merge them together by saying “Is 1 smaller than 2? Yes, so use 1. Is 4 smaller than 2? No, so use 2. Is 4 smaller than 3? No, so use 3” until we eventually end up with a sorted, merged array of numbers.

Some code

Let’s look at a practical example of merge sort code. In this fairly classic implementation (which has been drawn out a little to aid readability), we recursively split our array in half, until we can no longer split it (only a single element remains). Once we reach that point, we begin backtracking up our recursive calls, and at each stage we then merge the split halves together, until we’re all the way back at the top, with a merged, sorted version of our original array.

Let’s run through this flow with an array of [1, 5, 3, 8, 4, 2, 9, 6].

First, we’ll split it in half, to get our left-hand side of [1, 5, 3, 8]. Now as that’s still too many elements, we’ll split it again to [1, 5], and again to get [1] and [5]. Now that we’ve sufficiently split down our first contenders, let’s compare them. We see that 1 is less than 5, so we return the merged and sorted array of [1, 5]. Similarly, we also compare the next pair of 3 and 8, and return [3, 8], so it’s time for our first merge.

We’ll declare a new array, and then compare each side’s first values; 1 and 3. We know 1 is lower, so we’ll remove 1 from the left-hand side and put it into the new array. So at this point, we have a left-hand side of [5] , a right-hand side of [3, 8] and a new array of [1]. Comparing the next set of values (5 and 3), we can see that 3 is lower, so we remove that and add it to the new array. We now have a left array containing only 5, a right array containing only 8, and a new array of [1, 3]. So we now compare 5 and 8, see that 5 is lower, and so remove that and put it on the new array to give us [1, 3, 5].

At this point, because our left array is empty, we can save time by simply appending what remains of our right array onto the new array, as we know those numbers will be higher than all of the existing numbers in the new array. By doing this, we add our last remaining number of 8 to our new array, to give us [1, 3, 5, 8], a merged and sorted array.

As the call stack moves upward, we’ll then repeat this process with the right-hand side, giving us a sorted array of [2, 4, 6, 9], and then merge-sort the two arrays together, using the aforementioned method, to get [1, 2, 3, 4, 5, 6, 8, 9], a merged and sorted version of the original array.

Closing out

Merge-sorting requires a number of key concepts to be understood before you can fully understand the approach, the most important of which is recursion. But once you have a good understanding of recursion, the rest should start to make sense.

If however you’d like a little more help, I found this video from mycodeschool around the theory of merge-sorting to be a really helpful one, especially as it visualises how the data is manipulated at each individual stage.

Binary search (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 15:36:57 +0000

Searching through data is painful, whether it’s in a database, a spreadsheet, or even on a piece of paper. Even in code, searching data tends to be a fairly slow process, at least when compared to other programmatic actions you might be carrying out.

The classic method of course is with a loop. To find data with a loop, we simply look through every element until we find what we're looking for. This sounds great in principle, and is probably similar to how we’d look through a list of data in real life, but it’s not terribly efficient. However, if the data is randomly inserted and unordered, there’s not much we can do about this.

If on the other hand, the data is sorted, this opens us up for some other options, the primary of which is a binary search. We can think of a binary search as a way of chopping the data to be searched in half, until we reach the answer. To continue the real life example; imagine you have a list of 1,000 forenames in alphabetical order, and you’re looking for the name John. Rather than go through every individual name looking for John, what if we instead looked at entry 500 first? Well, if entry 500 was Lucy, then we’d know our answer lies in the first 500 entries, and so we can discard entries 500–1,000. We’ve just discarded 500 entries in a single check, pretty efficient right? So now all we do is repeat this process, until we are eventually left with just 1 entry.

To give a more practical example, consider this list of 10 names:

1. Amy  
2. Amanda  
3. Bill  
4. John  
5. Lucy  
6. Mark  
7. Nancy  
8. Terry  
9. Viktor  
10. William

Let’s now try and search for Nancy. First off we’ll check entry 5 (Lucy), and see that our name comes after that, so we’ll discard the first half of the list and be left with the following:

6. Mark  
7. Nancy  
8. Terry  
9. Viktor  
10. William

Now let’s check the middle point again; Terry. Well we know Nancy comes before Terry, so we’ll discard the latter section, leaving us with:

6. Mark  
7. Nancy  
8. Terry

This time when we check the middle value, we get a match! We’ve found the answer with just 3 checks, instead of the 7 it would have taken for a conventional loop.

More importantly, this approach scales. If we have a list of 10 entries and we’re looking for a value, we must do up to 10 checks. If we apply that same algorithm to 100,000,000 entries, we must do up to 100,000,000 checks. If instead we utilise a binary search, we will only need to do around 27 checks, depending on the target and the exact approach we use. That’s a pretty significant saving!

Code example

Let’s look at some of this in code. We’ll look at an ordered array of 10 numbers [1, 3, 4, 7, 8, 12, 16, 17, 18, 20], and search for a target number of 16. To achieve this, we’ll use the following binary search implementation:

First off we’ll establish our middle index of 5, which gives us a value in the above array of 12. We then compare that with the target and realise that the number we’re looking for is higher. So, we discard the first half of the data by moving the left-cursor to the middle point plus 1 (as we know the value at the middle point is not the target, having just checked it). This then reduces the array values we’re checking to [16, 17, 18, 20].

Now we’ll establish a new middle index of 2, which gives us a value in the new array of 18. We compare this with our target of 12 and see that it’s higher than our target, so we discard the second half of the new array, leaving us with [16, 17].

Next we pick a new middle index of 1, which gives us a value of 17, and see that this is still above our target value. So we chop off the right-side of the latest array and leave ourselves with [12], which is of course our answer.

Further considerations

It’s worth pointing out that the above implementation is just one, fairly classic implementation of a binary search. There are additional minor tweaks that can be done, such as using the full length of the array, or having a left <= right check rather than left < right. Some of these aid readability and personal understanding, others give very different results, but most follow the same basic concept and thus give the same performance.

Where you are most likely to need to make these sorts of changes is when what you’re looking for is a little more complicated, such as when you need to find not just the first occurrence of a value, but the last occurrence of it, and thus need to do a right-biased search. Or maybe your data isn’t ordered quite the way you expect, and so you need to account for that. In all cases, the fundamentals of a binary search remain the same, but the way in which you traverse the provided values may need to change slightly.

Finally I’d also like to mention a recursive form of binary searching. Once again the principles remain the same, but instead of a while loop running after we shrink the window of inspection (by moving left and right pointers closer together), we simply re-call the function with the smaller window. Personally, I prefer the iterative approach, but I will include it here for completeness:

SOLID principle #5: Dependency Inversion (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 15:24:35 +0000

The dependency injection principle states that high level code should never depend on low level interfaces, and should instead use abstractions. It’s all about decoupling code.

Not following? I don’t blame you, but it’s surprisingly simple.

Let’s say we have a piece of software that runs an online store, and within that software one of the classes (PurchaseHandler) handles the final purchase. This class is capable of charging the user’s credit card, and does so by using a PayPal API:

The problem here is that if we change from PayPal to Square (another payment processor) in 6 months time, this code breaks. We need to go back and swap out our PayPal API calls for Square API calls. But in addition, what if the Square API wants different types of data? Or perhaps it wants us to “stage” a payment first, and then to process it once staging has completed?

That’s bad, and so we need to abstract the functionality out instead.

Rather than directly call the PayPal API from our payment page, we’ll instead create another class called PaymentHandler. The interface for this class will remain the same no matter what underlying payment system we use, even if the two systems are completely different. We’ll still need to make changes to the PaymentHandler interface if we change payment processor, but our higher level interface remains unchanged.

Now you may be looking at this and thinking “but wait, that’s way more code”, and you’d be right. Like many of the SOLID principles (and indeed OO principles in general), the objective is less about writing less code or writing it quicker, and more about writing better code. The above change will save you days or maybe even weeks further down the line, in exchange for spending a few hours on it now.

SOLID principle #4: Interface Segregation (JavaScript)

Duncan McArdle — Wed, 09 Mar 2022 15:22:55 +0000

The interface segregation principle states that an entity should never be forced to implement an interface that contains elements which it will never use. For example, a Penguin should never be forced to implement a Bird interface if that Bird interface includes functionality relating to flying, as penguins (spoiler alert) cannot fly.

Now, this functionality is a little more difficult to demonstrate using JavaScript, due to its lack of interfaces. However, we can demonstrate it by using composition.

Composition is a subject all by itself, but I’ll give a very high level introduction: Instead of inheriting an entire class, we can instead add chunks of functionality to a class. Here’s an example that actually addresses the interface segregation principle:

What this example does is to add the flying functionality (or interface) only to the class(es) that require it. This means that penguins won’t be given the ability to fly, whereas birds will.

This is one method of adhering to the interface segregation principle, but it is a fairly rough example (as, once again, JavaScript doesn’t play well with interfaces).