Array Data Structure Data Structure
An Array stores elements of the same type in contiguous memory, delivering O(1) random access and optimal CPU cache locality at the cost of O(n) middle insertions and deletions.
| Operation | Complexity |
|---|---|
| Access | O(1) |
| Search | O(n) / O(log n) sorted |
| Insertion | O(n) / O(1) amortized end |
| Deletion | O(n) / O(1) end |
| Space | O(n) |
Interactive Visualizer · C++ / Python / Java / JS Code
Array Data Structure
An Array stores elements in a contiguous block of memory, allowing any element arr[i] to be accessed in $O(1)$ time via simple address arithmetic (base_address + i * sizeof(T)). Dynamic arrays (std::vector in C++, list in Python, ArrayList in Java) double capacity on overflow so appending at the end runs in $O(1)$ amortized time.
At a Glance
| Operation | Static Array | Dynamic Array (std::vector) |
| :--- | :--- | :--- |
| Random Access arr[i] | $O(1)$ | $O(1)$ |
| Search (Unsorted / Sorted) | $O(n)$ / $O(\log n)$ | $O(n)$ / $O(\log n)$ |
| Insert / Delete at End | $O(1)$ (if space) | $O(1)$ amortized |
| Insert / Delete at Index i | $O(n)$ (shift elements) | $O(n)$ (shift elements) |
| Auxiliary Space | $O(n)$ | $O(n)$ |
---
Core Concepts & Memory Layout
- Contiguous Memory = Cache Speed: Modern CPUs fetch memory in 64-byte cache lines. Scanning an array linearly triggers hardware prefetching, making arrays 5–10× faster to iterate than Linked Lists of the same size.
- Amortized $O(1)$ Resizing: When a dynamic array doubles its capacity from $1 \to 2 \to 4 \to \dots \to n$, total copied elements across all $n$ appends is $1 + 2 + 4 + \dots + n < 2n$, averaging
lt; 2$ copies per append!
Loading AntInLoop...
- Essential Array Patterns: Prefix Sums ($O(1)$ range sums), Difference Arrays ($O(1)$ range updates), Two Pointers, Sliding Window, and Kadane's Algorithm.
---
Practice Problems
Easy
1. Prefix Sum Array for $O(1)$ Range Sum Queries
Preprocess an array in $O(n)$ so any range sum sum(l, r) is answered in $O(1)$.
Approach: Build pref[i + 1] = pref[i] + a[i]; then sum(l, r) = pref[r + 1] - pref[l]. Time: $O(n)$ build, $O(1)$ query. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
class PrefixSum {
std::vector<long long> pref;
public:
explicit PrefixSum(const std::vector<int>& a) : pref(a.size() + 1, 0) {
for (size_t i = 0; i < a.size(); ++i) pref[i + 1] = pref[i] + a[i];
}
long long rangeSum(int l, int r) const { return pref[r + 1] - pref[l]; }
};
int main() {
PrefixSum ps({2, 4, 1, 7, 3});
std::cout << ps.rangeSum(1, 3) << " " << ps.rangeSum(0, 4) << "\n"; // 12 17
return 0;
}
</details>
2. Rotate Array Right by $k$ Steps In-Place (LeetCode 189)
Rotate an array to the right by k positions in $O(n)$ time and $O(1)$ extra space.
Approach: Reverse the whole array, reverse the first k % n elements, then reverse the remaining n - (k % n) elements! Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
void rotateRight(std::vector<int>& a, int k) {
int n = static_cast<int>(a.size());
if (n <= 1) return;
k %= n;
std::reverse(a.begin(), a.end());
std::reverse(a.begin(), a.begin() + k);
std::reverse(a.begin() + k, a.end());
}
int main() {
std::vector<int> a = {1, 2, 3, 4, 5, 6, 7};
rotateRight(a, 3);
for (int x : a) std::cout << x << " ";
std::cout << "\n"; // 5 6 7 1 2 3 4
return 0;
}
</details>
---
Intermediate
3. Maximum Subarray Sum (Kadane's Algorithm, LeetCode 53)
Find the contiguous non-empty subarray with the largest sum in $O(n)$ time and $O(1)$ space.
Approach: Maintain cur = max(x, cur + x) and best = max(best, cur). Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int maxSubArray(const std::vector<int>& nums) {
int cur = nums[0], best = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
cur = std::max(nums[i], cur + nums[i]);
best = std::max(best, cur);
}
return best;
}
int main() {
std::cout << maxSubArray({-2, 1, -3, 4, -1, 2, 1, -5, 4}) << "\n"; // 6
return 0;
}
</details>
4. Product of Array Except Self Without Division (LeetCode 238)
Return an array where ans[i] equals the product of all elements except nums[i], in $O(n)$ time and $O(1)$ extra space (excluding output).
Approach: Pass 1 stores prefix products in ans[i]; Pass 2 multiplies ans[i] by a running suffix product from right to left. Time: $O(n)$. Space: $O(1)$ extra.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
std::vector<int> productExceptSelf(const std::vector<int>& nums) {
int n = static_cast<int>(nums.size());
std::vector<int> ans(n, 1);
int prefix = 1;
for (int i = 0; i < n; ++i) {
ans[i] = prefix;
prefix *= nums[i];
}
int suffix = 1;
for (int i = n - 1; i >= 0; --i) {
ans[i] *= suffix;
suffix *= nums[i];
}
return ans;
}
int main() {
for (int x : productExceptSelf({1, 2, 3, 4})) std::cout << x << " ";
std::cout << "\n"; // 24 12 8 6
return 0;
}
</details>
---
Hard
5. First Missing Positive Integer in $O(n)$ Time and $O(1)$ Space (LeetCode 41)
Given an unsorted integer array, find the smallest positive integer (>= 1) missing from the array using only $O(1)$ auxiliary space.
Approach: Cyclic sort! Every value v in [1..n] belongs at index v - 1. Repeatedly swap nums[i] into nums[nums[i] - 1] while it's in range and not already placed. Finally, the first index i where nums[i] != i + 1 gives i + 1 (else n + 1). Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
#include <vector>
int firstMissingPositive(std::vector<int> nums) {
int n = static_cast<int>(nums.size());
for (int i = 0; i < n; ++i) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
std::swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
int main() {
std::cout << firstMissingPositive({3, 4, -1, 1}) << " "
<< firstMissingPositive({1, 2, 0}) << "\n"; // 2 3
return 0;
}
</details>
---
Related Structures & Algorithms
- Linked List — $O(1)$ pointer-based middle insertion/deletion without contiguous shifts.
- Two Pointers & Sliding Window — linear-time array algorithms.