Array Introduction
An array is a container which holds a fix number of items and these items should be of the same type. Arrays is also known as lists.
The two concepts of an array are an element and index. Each element stored in an array is called an element. Each location of an element in an array has a numerical value called index which identifies the element.
The actions/basic operations of arrays are lookup O(1), push/pop O(1), insert O(n) and delete O(n). The push and pop aer O(1), since it adds / removes data from the last position of the array. While insert has to iterate over all values and add 1 to their index, then insert the data it wants.
Python Examples:
cars = ["Ford", "Volvo", "BMW"]
| Method | Description |
|---|---|
| append() | adds an element to the end of the list |
| clear() | removes all elements from the alist |
| copy() | returns a copy of the list |
| count() | returns the number of elements with the specified value |
| extend() | adds the elements of a list to the end of the current list |
| index() | returns the index of the first element with the specified value |
| insert() | adds an element at the specified position |
| pop() | remove the element at the specified position |
| remove() | removes the first item with the specified value |
| reverse() | reverse the order of the list |
| sort() | sorts the list |
Static vs Dynamic Array
The one limitation of static arrays is that they are limited in size. This means you need to specify the size of the array ahead of time. In python as mentioned earlier, they automatically allocate memory because of memory re-sizing.
Strings and Arrays
Treat any string question like an array. A string is basically an array of characeters.
When to use Arrays
Use arras when you need a fast lookups, fast push/pop and ordered makes it fast to access in the memory. Don’t use arrays when you have slow inserts and slow deletes since it has to shift all the indexes O(n)
Common Array Questions
- Max Consecutive Ones
- Find numbers with even number of digits
- Squares of a Sorted Array
- Duplicate Zeros
- Merge Sorted Arrays
- Remove element
- Remove duplicates from Sorted Array
- Check if N and its double exists
- Valid mountain array
- Replace elements with greatest element on right side
- Remove duplicates from sorted array
- Move zeroes
- Sort array by Parity
- Squares of a sorted array
- Height checker
- Max Consecutive ones II
- Third Maximum Number
- Find all Numbers disappeared in an array