Overview
An array is a collection of data of the same type stored in contiguous memory space.
It is also the most basic data structure because it is the data structure that best adapts to the memory structure of modern computers, which is also called the "linear list structure". It is the first data structure that almost all algorithm learners come into contact with.
In interviews, questions about arrays generally do not require complex problem-solving thinking. They mainly test the ability to control code. Often when getting array questions, the first feeling is that the idea is very simple, but if the basic skills are not in place, there will always be mistakes in implementation.
If you want to avoid failure on array questions in the interview, you must first understand the characteristics of arrays and the situations in which it is more appropriate to use arrays as data structures.
Memory Structure of Array
Because an array is a collection of data of the same type stored in continuous memory space, the data corresponding to the subscript can be easily obtained through subscript indexing.
Thus, the initiation of array has two features:
- Index of an array always starts from 0.
- The addresses of the array memory space are continuous.
It is because the addresses of arrays in memory space are continuous, that when we delete or add elements, we have to move the addresses of other elements. This is also the main performance overhead of arrays.
For example, we are deleting char "C" with index 3 from the array.
This is based on the characteristics of arrays: array elements cannot be deleted, they can only be overwritten. Therefore, if an element is deleted, all subsequent elements must be shifted to overwrite the previous element. Therefore, in the worst case, if the first element is deleted, all remaining elements in the entire array must be shifted, making the time complexity O(N).
The same is true for insertion. If you need to insert an element at a certain index, and there is already an element at this position (including the subsequent index positions), then the index and all subsequent elements need to be translated backwards. Therefore, when the problem we face does not care about the order of elements, or requires frequent insertion and deletion operations, it usually means that arrays are not an ideal choice.
Pros & Cons of Array
Pros:
- Fast search speed.
- Allows fast random access.
Cons:
- Low efficiency in deletion and insertion.
- Fixed size, no support for dynamic expansion.
- Requires continuous memory space.
Multi-dimensional Array Continuous Memory Problem
By storing arrays in arrays, arrays can be multi-dimensional, but many people have a misunderstanding: that is, they take it for granted that the memory space of high-dimensional arrays is also continuous, but in fact it is not. Take a 3*4 two-dimensional array as an example
It can be seen that the two-dimensional array in the memory is not a 3*4 continuous address space as assumed, but consists of four continuous address spaces.
Sorted Array VS. Non-Sorted Array
From the perspective of arrays, they can be divided into ordered arrays and unordered arrays. In the process of solving array problems, we must first observe the array given in the question, because whether the array is ordered or not will have a great difference in the performance of certain operations, which will directly affect our choice of algorithm.
| Operation | Sorted Array | Non-Sorted Array |
|---|---|---|
| Search By Index | O(1) | O(1) |
| Linear Search | O(N) | O(N) |
| Binary Search | O(log(N)) | Not Support |
| Insert Element (Linear Search) | O(2N) = O(N) | O(2N) = O(N) |
| Insert Element (Binary Search) | O(log(2N)) + O(N) = O(N) | O(2N) = O(N) |
| Delete Element | O(1) + O(N) = O(N) | O(1) + O(N) = O(N) |
| Sort Array | Already Sorted | O(N^2) |
Categories of Array Problem
Because arrays, as a data structure, can only support limited operations, the solutions to array problems are relatively routine, and there are basically five ways to solve the problem.
- Simulation
- Binary Search
- Brute Force Time Complexity:O(n)
- Bineary Search Time Complexity:O(logn)
- Two Pointers
- Brute Force Time Complexity:O(n^2)
- Two Pointers Time Complexity:O(n)
- Sliding Window
- Brute Force Time Complexity:O(n^2)
- Sliding Window Time Complexity:O(n)
- Prefix Sum
- Brute Force Time Complexity:O(n^2)
- Prefix Sum Time Complexity:O(n)
Simulation questions are very common in arrays. They do not involve any algorithms, but are simply simulations, which test your ability to control the code.
Optimizing performance based on brute force search performance under the ordered array conditions
By using two pointers, the work of two for loops is done under one for loop.
The subtlety of the sliding window is that it continuously adjusts the starting position of the subsequence according to the current subsequence and its size, thereby reducing the O(n^2) brute force solution to O(n).
For solving problems like "the sum of the first n terms of a sequence", preprocessing is used to reduce the overall time cost.