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.
Before going into a deep dive in array manipulation let’s brush up on some array trivia.
- Arrays are data structures that are represented by contiguous blocks of memory. This means that we are able to iterate through it unlike pointer based data structures such as linked lists.
- 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. - 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…
