What Is an Array?
In short, an array is a sequence of values stored contiguously (back-to-back) in memory.
All values in the array must be of the same data type (e.g., integers, characters, etc.).
When an array is created, the computer allocates a continuous block of memory large enough for all its elements.
Unlike individual variables — which might be placed randomly in memory — array elements are stored side by side.
For example, an array of three integers will occupy 12 bytes in total (since an integer is typically 4 bytes), with the four bytes for each integer stored immediately next to the next.
Why Arrays Are Zero-Indexed
When an array is created, the computer:
Allocates a contiguous block of memory large enough for all elements.
Stores the address of the first element (called the base address).
The variable name (e.g., numbers) doesn’t hold all the elements — it only holds this starting address.
So when you write:
let numbers = [10, 20, 30];
The computer knows:
The base address (say, 0x1000) points to the first element (10).
Each integer takes 4 bytes.
Therefore:
numbers[0] → address 0x1000
numbers[1] → address 0x1004
numbers[2] → address 0x1008
This is why arrays start at index 0 —
to access any element, the computer uses the formula:
address = base_address + (index × size_of_each_element)
If indexing started at 1, every lookup would require an extra subtraction (index - 1) —
an unnecessary calculation. Zero-based indexing keeps memory access clean and direct.
When and Why to Use Arrays
Arrays are one of the most common choices for storing data — but when are they actually the best choice?
In general, there are four main operations you might want to perform on a dataset:
Insertion (adding a new item)
Deletion (removing an item)
Selection / Access (finding or reading an item)
Sorting (reordering items)
Let’s see how arrays handle each of these, both in the best and worst cases.
Deletion
It depends on where you delete from:
From the end: very efficient → O(1)
The computer simply forgets the last item — no need to move anything.
From the beginning or middle: slower → O(n)
Imagine removing the first book from a shelf — every other book needs to shift one position left to fill the empty spot.
So deleting the first element is the worst case since the program has to move n–1 items.
Insertion
Again, position matters:
Add to the end: easy → O(1)
The computer just adds one more element to the next empty slot.
Add to the beginning or middle: expensive → O(n)
All the other items need to shift one index to make room.
Selection (Accessing or Searching)
If you already know the index: instant → O(1)
Arrays shine here — the address formula lets you jump directly to any element.
If you don’t know the index: you must look through all items → O(n)
Sorting Is Special..
While most array operations have fixed theoretical costs defined by the structure itself
(e.g., deletion ≈ O(n), insertion ≈ O(n)), sorting is unique because your algorithm choice can change its Big O class entirely —
from O(n²) with simple methods like Bubble Sort to O(n log n) with smarter ones like Merge Sort.
For example:
Sorting an array with Bubble Sort → O(n²)
Sorting the same array with Merge Sort → O(n log n)
Here, the data is the same, but the algorithm changes the efficiency.
Why?
Because sorting isn’t an inherent feature of arrays — it’s an operation applied externally using an algorithm.
In contrast, operations like “add” or “access” are built into how arrays work.
LeetCode Example — Insertion in Arrays
Problem: LeetCode #1389 — Create Target Array in the Given Order
Task:
Given two arrays of integers, nums and index, create a target array following these rules:
Start with an empty array.
For each i, insert nums[i] at position index[i] inside the target array.
Repeat until all elements are processed.
It is guaranteed that all insertions will be valid.
As mentioned earlier, adding to the end of an array (like using .push() in JavaScript) is fast — O(1).
But inserting elements at random positions forces the computer to shift all other elements, which costs O(n) per insertion.
Since this problem requires doing that n times, the total cost becomes O(n²).
Step-by-Step Logic
When thinking through the solution:
Loop through the index array from start to end.
For each index i, find the corresponding number nums[i].
Insert nums[i] into the target array at position index[i].
If that position is already occupied, shift all following elements right.
Translating That Into Code:
function arrayMaker(index, nums) {
let target = [];
for (let i = 0; i < index.length; i++) {
target.splice(index[i], 0, nums[i]);
}
return target;
}
The .splice() method in JavaScript handles insertion directly.
It takes three arguments:
The index where to insert.
How many elements to delete (here, 0).
The new element to insert.
Example:
target.splice(2, 0, 5);
Inserts 5 at position 2, shifting everything after it to the right.
What We Learned
Inserting at the end of an array → O(1)
Inserting in the middle or beginning → O(n)
Doing this repeatedly → O(n²)
Arrays are great for reading and appending data,
but repeated insertions at random positions make them inefficient —
that’s where other data structures like linked lists come in.
Deletion Example — LeetCode #27
Problem: Remove Element
Given an integer array nums and a value val,
remove all occurrences of val in-place and return the new length of the array.
function removeElement(nums, val) {
let k = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[k] = nums[i];
k++;
}
}
return k;
}
Explanation
We use two pointers:
i → reads each element
k → marks the position where the next valid element should go
If the current value isn’t equal to val, we copy it to nums[k] and move k forward.
This overwrites unwanted values as we go — deleting in-place without creating a new array.
Physical deletion (using .splice() or .slice() repeatedly) is not optimal,
because each deletion shifts all following elements one step left —
making it O(n²) when done multiple times.
Instead, overwriting valid elements keeps it O(n) and efficient.
LeetCode #1365 — Counting Smaller Numbers
Problem: How Many Numbers Are Smaller Than the Current Number
We return, for each number, how many others are smaller than it.
var smallerNumbersThanCurrent = function(nums) {
let output = [];
for (let i = 0; i < nums.length; i++) {
let count = 0;
for (let j = 0; j < nums.length; j++) {
if (nums[i] > nums[j]) count++;
}
output[i] = count;
}
return output;
};
Explanation
This approach compares each element with every other element.
If nums[i] > nums[j], we increase the counter.
The result shows how many numbers are smaller than each one.
This works fine for small arrays but is O(n²) in complexity.
We can reduce it to O(n log n) using sorting and mapping —
but first, let’s move to a different array problem that highlights another concept: selection.
LeetCode #448 — Find All Numbers Disappeared in an Array
Step 1 — Brute Force
Compare each number against all possible values 1..n.
Works, but too slow → O(n²).
Step 2 — Smarter (Using a Set)
function missingNums(nums) {
let max = nums.length;
let fullArray = Array.from({ length: max }, (_, i) => i + 1);
let set = new Set(nums);
let missing = fullArray.filter(num => !set.has(num));
return missing;
}
How it works:
Array.from({ length: max }, (_, i) => i + 1) creates [1, 2, 3, ..., n].
new Set(nums) removes duplicates and enables O(1) lookups.
.filter() keeps only numbers missing from the Set.
Time: O(n)
Space: O(n)
Step 3 — Can You Still Do It Better?
Well, yes — you can make this even more efficient,
reduce the time complexity, and avoid using extra space.
Let’s see how
`function DisappearedNums(nums) {
let target = [];
for (let i = 0; i < nums.length; i++) {
let index = Math.abs(nums[i]) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
}
}
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
target.push(i + 1);
}
}
return target;
}`
What’s Happening Here?
Imagine you have a classroom full of students and want to see who’s absent.
Each student goes and marks their seat to show they attended.
Because arrays are zero-based, each student marks the seat at value - 1.
At the end, we check which seats remain unmarked (still positive) —
those correspond to the absent students.
This approach cleverly uses the same array as its own tracker,
so no extra arrays or Sets are needed.
Time Complexity: O(n)
Space Complexity: O(1)
This is one of the most efficient ways to solve the problem.
It shows how the right data structure, combined with the right algorithm,
can dramatically improve performance :)
Top comments (0)