Arrays are collections of elements that can be identified by an index. They are used to implement a ton of other data structures -- like queues, stacks, lists, and sometimes strings.
x = [1, 2, 3]In most languages, indexing starts at 0. The first item in an array can be found at the index 0. Arrays can also have multiple dimensions so matrix operations commonly use them in computer science.
Arrays are stored in memory contiguously, or in one chunk of space, so the memory address of each element in the array can be computed using this formula address = start + (cellsize * index). So an array with three 32-bit integer variables could be stored at addresses 2000, 2004, 2008 so then the address of an item would be 2000 + 4 * index. In many implementations of arrays, the array block of memory only stores a pointer to the item in the array rather than the item itself in order to support dynamic typing.
Arrays have a fixed size when they are created, so insertion and deletion is not natively supported. If you were able to change the size of an array during runtime, there would be no guarantee that there would be more memory in its reserved block to use.
Many high level languages take care of resizing behind the scenes by using dynamic arrays, so the user doesn't need to initialize the array with a certain size. For example, in Python, lists are initialized automatically with overfill (or additional unused slots). They resize at 4, 8, 16, 25 etc. items (source). From a computational perspective, this makes them less efficient but a lot more programmer friendly!
| Operation | Complexity |
|---|---|
| Access | O(1) |
| Search | O(n) |
| Insert | O(n) |
| Delete | O(n) |
- Accessing can be done using the formula
start + (cellsize * index) - Searching is done by iterating through the array and seeing if the value equals the item you are searching for.
- Insertion is done by recreating the array, which means that each item must be recreated.
- Deletion is done by recreating the array, which means that each item must be recreated.
- Check to see if two strings are anagrams of one another.
- Check to see if two strings are permutations of each other.
- Compress a string
- Count the differences between two strings
- Count the positive, negative, and zero values in an array
- Count the valleys in a hike
- Draw a pyramid given its height
- What is the number of deletions needed to make two arrays equal?
- Array left rotation
- Find the item in an array that doesn't have a match
- Find the diagonal difference in a matrix
- Find the maximum and minimum sums in an array
- Check to see if a string can be rearranged as a palindrome
- Check to see if a string can be made from a list of substrings
- See if a word is in a list of words
- Check if a string contains only unique characters
- Find the max subarray
- URLify a string
- Zero a matrix
- Add the even numbers in the Fibonacci sequence
- Find the largest prime factor of a number
- Find the largest palindrome project
- Smallest multiple
- Smallest square difference
- 10001st prime product
- Largest product in a grid
- Large sum
- Find longest Collatz sequence
- Number letter counts
- Maximum path sum I
- Non-abundant sums
- Lexicographic permutations
- Quadratic primes
- Number spiral diagonals
- Pandigital products
- Circular primes
- Double base palindromes
- Truncatable primes
- Maximum path sum II