Arrays

Intro

Arrays hold multiple elements of the same data type in contiguous block of memory. This is also why they, like Strings, are referred to as Sequences. Different languages manage Arrays differently. Fixed size or Dynamically sized? Some languages have fixed size arrays while others are dynamic and grow/shrink as needed.

Implementation

Constant time access

Random access (constant time to read and write at an index). This is done because of the arithmetic done to reach an index in the contiguous memory block, because all the elements in an array are the same type and same max size. // Usually at least, some languages have fancy arrays...

It starts with the address of the array (the first element) plus the size of an element, then multiplied by the index. $array\_addr+elem\_size\ast (index-first\_indx)$ // Since most arrays are 0 indexed, the subtractions often unnecessary.

In Multidimensional arrays

For example if you’re given index (3,4) i, e arr[3][4] in a 3x6 array. Number of elements to skip: the number of rows to skip multiplied by the number of elements per row, plus the number of elements to skip in the intended row: $(3-1)\ast 6+(4-1)=15$ // assuming first index is 1 here...

This 15 is the number of elements to skip we then plug this into the following formula: $elm\_addr=array\_addr+elm\_size\ast num\_skip$

How languages organize and order arrays

1. Row major ordering: stored sequentially, starting at the first row and stores column by column before moving to the next row. Ex: (1,1), (1,2), (1,3)…
2. Column major ordering: also stored sequentially and does start at the first row and first column, but goes row by row before moving on to the next column. Ex: (1,1), (2, 1), (3,1)..

Advantages

1. Store multiple elements of the same type together and use One variable.
2. Accessing elements is O(1) but only if you have the index of the desired element, otherwise you’d need to traverse and find the element which is O(n)

Disadvantages

1. Addition or removal of middle elements is slow, because the entire array needs to be shifted to accommodate the insert/remove. This isn’t the case for ops on the end of the array.
2. In languages with fixed sized arrays, when an array grows beyond that size, a new array must be allocated and all the elements copied over, this is an O(n) operation.

Subarray and Subsequence

• Subarray - A range of contiguous values within an array. Ex: given an array [2, 3, 6, 1, 5, 4], [3, 6, 1] is a subarray while [3, 1, 5] is not a subarray.
• Subsequence - A sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. Ex: given an array [2, 3, 6, 1, 5, 4], [3, 1, 5] is a subsequence but [3, 5, 1] is not a subsequence. // This was copied from the Tech Interview Handbook

Time complexity

Operation	Big-O	Note
Access	O(1)	Given index of element
Search	O(n)	Need to go through the whole array in worst case
Search (sorted array)	O(log(n))	This is due to Binary Search
Insert	O(n)	Insertion requires shifting all the subsequent elements to the right by one and that takes O(n)
Insert (at the end)	O(1)	Special case of insertion where no other element needs to be shifted
Remove	O(n)	Removal requires shifting all the subsequent elements to the left by one and that takes O(n)
Remove (at the end)	O(1)	Special case of removal where no other element needs to be shifted

Edge cases

• Empty sequence (empty array)
• Sequence with 1 or 2 elements
• Sequence with repeated elements
• Duplicated values in the sequence

Dynamic Arrays

Regular arrays are static, meaning once they’re declared and initialized there size is fixed, you can mutate the elements within but the size is done deal. This obviously isn’t optimal at times when we don’t know the number of elements to be stored in the array. And that’s where Dynamic Arrays come in.

Jagged Arrays

A JaggedArray is an array of arrays where the inner arrays are of differing sizes.

int[][] arr = new int[4][];
arr[0] = new int[3];
arr[1] = new int[5];
arr[2] = new int[4];
arr[4] = new int[6];

Whereas a 2D array, Matrix, is uniform such that each row contains the same number of columns.

Techniques

Most strategies that apply to Strings also apply to arrays due to their Sequences nature.

Sliding Window

This is a common problem/technique that requires two pointers moving in the same direction. The window moves based on some conditions on each iteration (loop). The left pointer never surpasses the right. Through one loop, this remains an O(n) operation. Common problems include Array Problems.

Two pointers

Two pointers is a more general version of sliding window where the pointers can cross each other and can be on different arrays. Examples: Sort Colors, Palindromic Substrings

In a two array problem to process, it’s common to have one index per array (pointer) to traverse/compare the both of them, incrementing one of the pointers when relevant. For example, we use this approach to merge two sorted arrays. Examples: Merge Sorted Array

Traversing from the right(end)

Some problems require traversing from the end, decrementing the counter. Examples: Daily Temperatures, Number of Visible People in a Queue

Sorting the Array

Sorting the array helps us make operations faster than the common O(n) time complexity, as we don’t need to iterate through the entire array when we know it’s sorted.

Precomputation

For questions where summation or multiplication of a subarray is involved, precomputation using hashing or a prefix/suffix sum/product might be useful. Examples: Product of Array Except Self, Minimum Size Subarray Sum, LeetCode questions tagged “prefix-sum”

Index as a hash key

If you are given a sequence and the interviewer asks for O(1) space, it might be possible to use the array itself as a hash table. For example, if the array only has values from 1 to N, with N-1 being the key for the last element obviously. Personally, this is a cheesy way of pretending you have a hash table / hash map. Examples: First Missing Positive, Daily Temperatures

Traversing the array more than once

Remember that traversing the array twice/thrice (as long as fewer than n times) is still O(n), because if you traverse say 3 times, then complexity is O(3 * n) which is still O(n). Sometimes traversing the array more than once can help you solve the problem while keeping the time complexity to O(n). Note: don’t confuse this for nested loops that traverse the array together those are $O(n^2)$ or even $O(n^m)$.

Essential questions

• Two Sum
• Best Time to Buy and Sell Stock
• Product of Array Except Self
• Maximum Subarray

Recommended practice questions

Try these after the essentials

• Contains Duplicate
• Maximum Product Subarray
• Search in Rotated Sorted Array
• 3Sum
• Container With Most Water
• Sliding Window Maximum

---

Resources

Readings - Array in Data Structure: What is, Arrays Operations, Guru99 Videos - Arrays, University of California San Diego Websites

• Tech Interview Handbook