Image for post
Image for post

Algorithm Tool Kit: Arrays

Arrays are a fundamental data structure in every language. Its ability to provide O(1) random access to elements is something that should not be disregarded. Due to its importance, arrays are guaranteed to be on your next technical interview. Here’s a quick tool kit on techniques and strategies you can employ.

  1. Arrays have O(1) insertion time.
    Note* Arrays in JavaScript and Python have a O(n) time for insertion. This is because we do not allocate how much memory the array has upon initialization. Java and C++ have equivalent data structures known as ArrayLists and Vectors respectively. We express insertion time into an array for Python and JavaScript as O(1) amortized time.
  2. Arrays have O(n) time for deletion and search.
    Some readers will make the claim that search is O(log n) because of binary search. However it is important to remember that binary search is only applicable to sorted arrays.

For Loop

Bet you didn’t see this one coming. The humble for loop should not be neglected for being too elementary. One of the major upsides for arrays is that we can easily iterate through it without creating separate iterator methods.

Two Variable Declaration
Single variable declaration

Recursion

Recursion is the big bad wolf for new developers. All these fancy terms get thrown around: base case, recursive case, substructure, recurrence relation and people get confused. These are all good to know, but we only really need to know base case and recursive case to write a recursive algorithm.

Recursive Reverse

Map

Our first data structure! Maps in JavaScript are essentially objects on super steroids. Just like objects, maps support key -> value pairs. However, what’s really cool about them is they come with methods that help with both readability and functionality. The most important difference is that maps support all types of keys whereas objects only support string keys. Other languages have a variation of Map: Java has HashMap and Python has Dictionary.

Two Sum with map
Two Sum brute force

Set

Set along with Map was introduced in ES6. Set is the JavaScript implementation of other language’s Set data structure. The rule for Set is simple: there can be no duplicates.

Sorting

For all the flak I’ve been giving sorting in the previous sections, it’s surprising that I bring up sorting here as a potential technique.

  1. In the general context of algorithm design, sorting offers valuable take aways that we can apply to other algorithm design. The partitioning function in Quick Sort and the merging function in Merge Sort can all be modified and used to fit certain needs.

Sliding Window

Sliding window algorithm is a technique used to perform operations on an array with a specific buffer. It is similar to declaring multiple pointers in the same for-loop, however we keep the distance between each pointer constant.

Brute Force
Sliding Window

Binary Search

Binary search???? That’s most people’s reaction when I explain you can use this to solve non-searching problems. Binary search has the misfortune of being many people’s first “cool” algorithm. Its implementation is simple and its usage is scarce, so many people either forget about it or don’t understand the properties of it. But its simplicity is what makes it such a powerful technique at times. It can only be used on sorted/semi-sorted arrays.

[4,5,6,1,2,3]
output: 1

Dynamic Programming

Now we’re getting into end game material.
Dynamic programming is an algorithm design paradigm of optimizing recursive algorithms. There are a few key things to note about dynamic programming.

  1. We can avoid recalculating previously found solutions.
  2. We store the calculated solutions to subproblems in an array and refer to it to optimize the runtime. Because we create a cache, the minimum space complexity for a dynamic solution is always O(n).
Fibonacci Sequence

That’s it!

These are most of the techniques I go through when looking at how to solve problems that use arrays. There are a few stuff I left out such as greedy algorithms, divide and conquer, and bit operators since they each deserve a separate post explaining their somewhat fragile implementation and usage.

Java, JavaScript, Open Source enthusiast. Competitive programming, golf, and LoL hobbyist. Carleton College Alumni. www.linkedin.com/in/baedavid

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store