UNIT 02Prerequisite: Unit 00 + Unit 0190 min read
Everything in data structures starts here. Linked lists, stacks, queues, heaps, graphs — they all either use arrays internally or are compared against arrays. If you understand arrays deeply, the rest of DSA becomes much easier to learn.
In this unit we build arrays from scratch in C, understand exactly how they live in your computer's memory, and implement every core operation with full code and complexity analysis.
// Section 1
What is an Array?
An array is a collection of items stored at contiguous (back-to-back) memory locations, where every item is of the same data type.
The word contiguous is the key. It means the items do not scatter randomly in RAM — they sit in a neat, unbroken row. This single property is what gives arrays their superpower: accessing any element instantly in O(1).
🪑 Think of a row of seats in a cinema
Imagine Row A in a cinema hall. It has seats A1, A2, A3, A4, A5 — all in a straight line, numbered from left to right. Every seat exists, every seat has a number, and they are all together.
Seat number = Array Index
Just like seat A3 always means the 3rd seat, index [2] always means the 3rd element. (We count from 0, not 1 — more on that shortly.)
Row = Contiguous memory
All seats are in one row — just like all array elements occupy one unbroken stretch of RAM. No gaps, no random jumps.
💡 Note
Why does contiguous memory matter? Because the computer can calculate the exact address of any element using simple math:
address of arr[i] = base address + (i × size of one element)
This is why accessing arr[999] is just as fast as accessing arr[0]. No searching needed — pure arithmetic.
// Section 2
How Arrays Sit in Memory
Let us go one level deeper and see exactly what happens in RAM when you create an array in C. This is the part most tutorials skip — and it is the part that makes everything else click.
Say you declare this:
int marks[5] = {85, 92, 78, 60, 95};
An int takes 4 bytes in C. So 5 integers need 5 × 4 = 20 bytes of contiguous RAM. Here is what that looks like:
// int marks[5] in RAM — each cell = 4 bytes
↑ base address: 0x2000
each step = +4 bytes (size of int)
To find marks[3], the computer does:
address = base + (index × size)
address = 0x2000 + (3 × 4)
address = 0x2000 + 12
address = 0x200C → value is 60 ✓
🎯 Pro Tip
This is why arrays start at index 0, not 1. Index 0 means "0 steps from the base." If arrays started at 1, every access would need an extra subtraction. Starting at 0 makes the address formula perfectly clean.
// Section 3
Declaring and Accessing Arrays in C
There are three ways to create an array in C. Each one is useful in different situations.
#include <stdio.h>
int main() {
/* Method 1: declare with size, fill values later */
int scores[5];
scores[0] = 10;
scores[1] = 20;
scores[2] = 30;
scores[3] = 40;
scores[4] = 50;
/* Method 2: declare and initialise together */
int marks[5] = {85, 92, 78, 60, 95};
/* Method 3: let C count the size for you */
int ages[] = {18, 22, 25, 30}; /* compiler sets size to 4 */
/* Accessing elements — always use index */
printf("First mark: %d\n", marks[0]); /* prints 85 */
printf("Third mark: %d\n", marks[2]); /* prints 78 */
printf("Last mark: %d\n", marks[4]); /* prints 95 */
return 0;
}
⚠️ Important
The off-by-one mistake — the most common array error ever. An array of size 5 has valid indices 0, 1, 2, 3, 4. Accessing arr[5] goes out of bounds — you are reading memory that does not belong to you. C will not warn you. It will silently read garbage data or crash your program. Always remember: last valid index = size − 1.
// Section 4
Traversal — Visiting Every Element
Traversal means visiting each element of the array exactly once — from index 0 to index n−1. It is the most basic operation and the foundation of everything else.
#include <stdio.h>
int main() {
int marks[5] = {85, 92, 78, 60, 95};
int n = 5; /* total number of elements */
int i;
printf("All marks:\n");
for (i = 0; i < n; i++) { /* start at 0, stop before n */
printf("marks[%d] = %d\n", i, marks[i]);
}
return 0;
}
/* Output:
marks[0] = 85
marks[1] = 92
marks[2] = 78
marks[3] = 60
marks[4] = 95
*/
Time Complexity:O(n)
Space Complexity:O(1)
We visit n elements so time is O(n). We use no extra memory — just one loop variable i — so space is O(1).
// Section 5
Insertion — Adding an Element
Here is an important truth about arrays: their size is fixed when you create them. You declare int arr[10] and you get exactly 10 slots — no more, no less. So "insertion" in an array means placing a value into an existing empty slot, or shifting elements to make room.
Case 1 — Insert at the end
If there is space at the end, just put it there. No shifting needed.
#include <stdio.h>
int main() {
int arr[10] = {10, 20, 30, 40, 50}; /* array has capacity 10 */
int n = 5; /* currently 5 elements filled */
int newVal = 60;
arr[n] = newVal; /* insert at position n (the next empty slot) */
n++; /* update the count */
/* print to confirm */
int i;
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
/* Output: 10 20 30 40 50 60 */
return 0;
}
Case 2 — Insert at a specific position
This is where arrays show their weakness. To insert at position 2, every element from position 2 onwards must shift one step to the right to make room. The more elements, the more shifting.
// Insert 99 at index 2 — elements must shift right
Before:
→ Shift indices 2, 3, 4 one step right
After inserting 99 at index 2:
#include <stdio.h>
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5;
int pos = 2; /* insert at index 2 */
int newVal = 99;
int i;
/* shift elements right from the end to make room */
for (i = n - 1; i >= pos; i--) {
arr[i + 1] = arr[i]; /* move each element one step right */
}
arr[pos] = newVal; /* place the new value */
n++; /* one more element now */
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
/* Output: 10 20 99 30 40 50 */
return 0;
}
Time Complexity:O(n)(worst case: insert at index 0 shifts everything)
// Section 6
Deletion — Removing an Element
Deletion is the mirror image of insertion. To remove an element at a position, you shift everything after it one step to the left to fill the gap. The array size in memory stays the same — you just track one fewer filled element.
// Delete element at index 2 (value 30) — shift left to close gap
Before:
→ Shift indices 3, 4 one step left
After deleting index 2:
#include <stdio.h>
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5;
int pos = 2; /* delete element at index 2 */
int i;
/* shift elements left from pos+1 onwards */
for (i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1]; /* overwrite with the next element */
}
n--; /* one fewer element now */
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
/* Output: 10 20 40 50 */
return 0;
}
Time Complexity:O(n)(worst case: delete at index 0 shifts everything)
// Section 7
Searching — Finding an Element
To find a value in an unsorted array, the only option is to check each element one by one until you find it or reach the end. This is called linear search.
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
int i;
for (i = 0; i < n; i++) {
if (arr[i] == target) {
return i; /* found — return the index */
}
}
return -1; /* not found — return -1 as a signal */
}
int main() {
int marks[5] = {85, 92, 78, 60, 95};
int n = 5;
int result = linearSearch(marks, n, 78);
if (result != -1) {
printf("Found 78 at index %d\n", result); /* Found 78 at index 2 */
} else {
printf("Not found\n");
}
return 0;
}
Best Case:O(1)(target is at index 0)
Worst Case:O(n)(target at end or not present)
💡 Note
We will cover Binary Search in Unit 10 — a far faster way to search that works in O(log n). But it only works on sorted arrays. For now, linear search is the correct tool for unsorted data.
// Section 8
2D Arrays — Rows and Columns
A 2D array is an array of arrays — like a table or a grid. Think of a spreadsheet: rows going across, columns going down. Every cell has two coordinates — a row number and a column number.
// int matrix[3][4] — 3 rows, 4 columns
matrix[1][2] = 7 | matrix[2][3] = 12 | matrix[0][0] = 1
#include <stdio.h>
int main() {
/* declare a 3x4 matrix and fill it */
int matrix[3][4] = {
{1, 2, 3, 4}, /* row 0 */
{5, 6, 7, 8}, /* row 1 */
{9, 10, 11, 12} /* row 2 */
};
int i, j;
/* print the matrix row by row */
for (i = 0; i < 3; i++) { /* loop over rows */
for (j = 0; j < 4; j++) { /* loop over columns */
printf("%3d ", matrix[i][j]);
}
printf("\n"); /* new line after each row */
}
/* access a specific element */
printf("matrix[1][2] = %d\n", matrix[1][2]); /* prints 7 */
return 0;
}
Traversal Time:O(rows × cols)
Access Time:O(1)
// Section 9
Classic Array Problems — With Full Solutions
These four problems appear constantly in interviews and in real code. Understand every line — do not just copy.
Problem 01Find Maximum and MinimumO(n)
Start by assuming the first element is both the max and the min. Then walk through the rest — if you find something bigger, update max. If smaller, update min.
#include <stdio.h>
int main() {
int arr[] = {64, 25, 12, 90, 38, 7, 55};
int n = 7;
int max = arr[0]; /* assume first element is max */
int min = arr[0]; /* assume first element is min */
int i;
for (i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i]; /* found a new max */
}
if (arr[i] < min) {
min = arr[i]; /* found a new min */
}
}
printf("Maximum: %d\n", max); /* Maximum: 90 */
printf("Minimum: %d\n", min); /* Minimum: 7 */
return 0;
}
Problem 02Reverse an ArrayO(n)
Use two pointers — one at the start, one at the end. Swap them and move inward until they meet in the middle. No extra array needed.
#include <stdio.h>
void reverseArray(int arr[], int n) {
int left = 0;
int right = n - 1;
int temp;
while (left < right) {
/* swap arr[left] and arr[right] */
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++; /* move left pointer inward */
right--; /* move right pointer inward */
}
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = 5;
int i;
reverseArray(arr, n);
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
/* Output: 50 40 30 20 10 */
return 0;
}
Problem 03Find Duplicate ElementsO(n²)
For each element, check if the same value appears again later in the array. This uses a nested loop — O(n²) — which is the straightforward approach. There are faster methods using hashing (Unit 14) but this version requires no extra knowledge.
#include <stdio.h>
int main() {
int arr[] = {4, 2, 7, 2, 9, 4, 1};
int n = 7;
int i, j;
printf("Duplicate elements: ");
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
printf("%d ", arr[i]);
break; /* avoid printing the same duplicate multiple times */
}
}
}
/* Output: Duplicate elements: 4 2 */
printf("\n");
return 0;
}
Problem 04Rotate Array Left by OneO(n)
Save the first element, shift everything left by one position, then place the saved element at the end.
#include <stdio.h>
void rotateLeft(int arr[], int n) {
int first = arr[0]; /* save the first element */
int i;
for (i = 0; i < n - 1; i++) {
arr[i] = arr[i + 1]; /* shift each element one step left */
}
arr[n - 1] = first; /* place saved element at the end */
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = 5;
int i;
rotateLeft(arr, n);
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
/* Output: 20 30 40 50 10 */
return 0;
}
// Section 10
Array Strengths and Weaknesses
No data structure is perfect. Understanding where arrays shine and where they struggle is exactly the kind of thinking interviewers test for.
✅ Strengths
→Access any element by index in O(1) — fastest possible
→Simple to understand and implement
→Cache-friendly — contiguous memory means faster real-world performance
→Works well when size is known in advance
❌ Weaknesses
→Fixed size — you must decide the size before you start
→Insertion and deletion are O(n) — shifting is expensive
→Wasted memory if you declare size 100 but only use 10
→No built-in way to grow or shrink dynamically
🎯 Pro Tip
This is exactly why Linked Lists exist — they solve the fixed-size and slow-insertion problems of arrays. We cover them in Unit 05. Every weakness of arrays becomes a motivation for the next data structure.
| Operation | Best Case | Worst Case | Notes |
|---|
| Access by index | O(1) | O(1) | Always instant — best property of arrays |
| Search (unsorted) | O(1) | O(n) | Best: element at index 0. Worst: not found |
| Insert at end | O(1) | O(1) | Just place in the next slot |
| Insert at position | O(1) | O(n) | Worst: insert at index 0 shifts everything |
| Delete at position | O(1) | O(n) | Worst: delete index 0 shifts everything |
| Traversal | O(n) | O(n) | Must visit all n elements |
// What's Next
You Are Ready for Unit 03
You now understand arrays completely — from how they sit in RAM to every core operation with full complexity analysis. This knowledge will never become irrelevant. Arrays are inside almost every program ever written.
In Unit 03 we cover Strings — which are, at their core, just arrays of characters. You already know how they work in memory. Now we learn how to search, reverse, compare, and manipulate text in C.
UP NEXT → UNIT 03
Strings — Text is Just an Array
Reverse, palindrome, anagram, pattern matching — in C.
🎯 Key Takeaways
- ✓An array stores elements at contiguous (back-to-back) memory locations — all of the same type
- ✓Accessing any element by index is O(1) because the address is calculated with simple math: base + (index × size)
- ✓Arrays are zero-indexed — valid indices are 0 to n−1. Accessing index n is an out-of-bounds error
- ✓Insertion and deletion at a position require shifting elements — worst case O(n)
- ✓Linear search checks every element one by one — O(n) worst case
- ✓2D arrays are tables: accessed as matrix[row][column], traversal is O(rows × cols)
- ✓Arrays are fast to access but slow to insert/delete. This weakness motivates linked lists in Unit 05