Arrays
An array is one of the most basic and important data structures in DSA.
Array = A collection of elements of the same data type stored in a sequence, usually in contiguous memory locations.
Arrays are important because many later DSA topics build on the concepts you learn here.
1. Why Do We Need Arrays?
Suppose you want to store the marks of 5 students.
Without an array:
int mark1 = 80; int mark2 = 75; int mark3 = 90; int mark4 = 65; int mark5 = 88;
This becomes difficult to manage when you have hundreds or thousands of students.
With an array:
int marks[5] = {80, 75, 90, 65, 88};
Now all the marks are stored under one variable:
marks ├── 80 ├── 75 ├── 90 ├── 65 └── 88
2. Basic Structure of an Array
Suppose:
int arr[5] = {10, 20, 30, 40, 50};
The array contains 5 elements.
We can visualize it as:
Index: 0 1 2 3 4 ┌────┬────┬────┬────┬────┐ Value: │ 10 │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┴────┘
The important thing is:
Array indexing usually starts from 0.
So:
arr[0] = 10 arr[1] = 20 arr[2] = 30 arr[3] = 40 arr[4] = 50
3. Declaring an Array
In C++:
int arr[5];
This means:
Create an integer array that can contain 5 elements.
General syntax:
data_type array_name[size];
Examples:
int numbers[10]; float prices[5]; char letters[26]; double values[100];
4. Initializing an Array
You can initialize an array when creating it.
int arr[5] = {10, 20, 30, 40, 50};
Or:
int arr[] = {10, 20, 30, 40, 50};
In the second example, C++ determines the size automatically.
So:
int arr[] = {10, 20, 30, 40, 50};
has:
Size = 5
5. Accessing Array Elements
You access an element using its index.
int arr[5] = {10, 20, 30, 40, 50}; cout << arr[0];
Output:
10
Another:
cout << arr[3];
Output:
40
Remember:
arr[0] → first element arr[1] → second element arr[2] → third element arr[3] → fourth element arr[4] → fifth element
6. Why Does Index Start at 0?
This is an important concept.
An array stores elements in memory locations next to each other.
If the starting memory address is:
1000
and each integer occupies 4 bytes:
Index Address 0 1000 1 1004 2 1008 3 1012 4 1016
The address of an element can conceptually be calculated as:
Address = Base Address + (Index × Element Size)
For arr[2]:
1000 + (2 × 4) = 1008
This direct calculation is one reason array access is O(1).
7. Updating an Array Element
You can change an existing element.
int arr[5] = {10, 20, 30, 40, 50}; arr[2] = 100;
Now:
Index: 0 1 2 3 4 ┌────┬─────┬────┬────┬────┐ Value: │ 10 │ 20 │100 │ 40 │ 50 │ └────┴─────┴────┴────┴────┘
So:
cout << arr[2];
gives:
100
This operation is:
O(1)
8. Traversing an Array
Traversal means visiting each element of an array.
Example:
int arr[5] = {10, 20, 30, 40, 50}; for(int i = 0; i < 5; i++) { cout << arr[i] << " "; }
Output:
10 20 30 40 50
We use the index:
0 → 1 → 2 → 3 → 4
Complexity
We visit every element.
Therefore:
Time Complexity = O(n)
9. Taking Array Input
Instead of manually entering values:
int arr[5]; for(int i = 0; i < 5; i++) { cin >> arr[i]; }
If the user enters:
10 20 30 40 50
The array becomes:
[10, 20, 30, 40, 50]
10. Finding the Sum of an Array
Example:
int arr[5] = {10, 20, 30, 40, 50}; int sum = 0; for(int i = 0; i < 5; i++) { sum += arr[i]; } cout << sum;
Output:
150
Why?
10 + 20 + 30 + 40 + 50 = 150
Complexity:
Time = O(n) Space = O(1)
11. Finding the Maximum Element
Suppose:
[10, 45, 20, 80, 35]
We want:
80
Algorithm:
int arr[5] = {10, 45, 20, 80, 35}; int maximum = arr[0]; for(int i = 1; i < 5; i++) { if(arr[i] > maximum) { maximum = arr[i]; } } cout << maximum;
Output:
80
Complexity:
Time = O(n) Space = O(1)
12. Finding the Minimum Element
Same idea.
int arr[5] = {10, 45, 20, 80, 35}; int minimum = arr[0]; for(int i = 1; i < 5; i++) { if(arr[i] < minimum) { minimum = arr[i]; } } cout << minimum;
Output:
10
Complexity:
Time = O(n) Space = O(1)
13. Searching in an Array
Suppose:
[10, 20, 30, 40, 50]
We want to find:
40
We can check elements one by one.
int target = 40; for(int i = 0; i < 5; i++) { if(arr[i] == target) { cout << "Found"; break; } }
This is called Linear Search.
Complexity
Worst case:
O(n)
Because we might have to check every element.
Later, you'll study Binary Search, which can achieve:
O(log n)
when the data is appropriately sorted.
14. Insertion in an Array
This is where arrays have an important limitation.
Suppose:
[10, 20, 30, 40]
We want to insert 25 between 20 and 30.
We need to shift elements:
Before: 10 20 30 40 ↓ 25
After shifting:
10 20 25 30 40
Elements after the insertion position may need to move.
Therefore insertion can take:
O(n)
in the worst case.
15. Deletion in an Array
Suppose:
[10, 20, 30, 40, 50]
We delete:
30
We need to shift the elements after it:
Before: 10 20 30 40 50 Delete 30 10 20 40 50 Shift: 10 20 40 50
Again, elements may need to move.
Worst-case complexity:
O(n)
16. Array Operations and Complexity
This table is important:
| Operation | Typical Complexity |
|---|---|
| Access by index | O(1) |
| Update by index | O(1) |
| Traversal | O(n) |
| Linear search | O(n) |
| Insertion | O(n) |
| Deletion | O(n) |
For insertion and deletion, the exact complexity depends on where the operation occurs.
For example, inserting at the end of a fixed-size array doesn't require shifting existing elements, while inserting at the beginning may require shifting many elements.
17. Fixed-Size Arrays
Traditional C++ arrays have a fixed size.
int arr[5];
You cannot make it become:
10 elements
automatically.
The size is determined when the array is created.
For example:
int arr[5];
means space for 5 integers.
This is one limitation of traditional arrays.
18. Array Memory Layout
One of the most important properties of an array is:
Array elements are stored contiguously.
Conceptually:
Memory: 1000 → arr[0] 1004 → arr[1] 1008 → arr[2] 1012 → arr[3] 1016 → arr[4]
There aren't arbitrary gaps between normal array elements.
This gives arrays excellent cache locality and makes direct index access efficient.
19. One-Dimensional Array
The array examples we've seen are 1D arrays.
Example:
int arr[5] = {10, 20, 30, 40, 50};
Visual representation:
[10] [20] [30] [40] [50]
20. Two-Dimensional Array
A 2D array can be thought of as a table or matrix.
Example:
int matrix[3][3];
It has:
3 rows 3 columns
Example:
int matrix[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
Visual representation:
Column 0 1 2 Row 0 1 2 3 Row 1 4 5 6 Row 2 7 8 9
Access:
cout << matrix[1][2];
Output:
6
Because:
matrix[row][column] matrix[1][2] = 6
21. Traversing a 2D Array
We generally use nested loops.
int matrix[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { cout << matrix[i][j] << " "; } cout << endl; }
Output:
1 2 3 4 5 6 7 8 9
Complexity:
O(rows × columns)
For a square n × n matrix:
O(n²)
22. Array vs Variable
A normal variable stores one value:
int age = 22;
An array stores multiple values:
int ages[5] = {18, 19, 20, 21, 22};
Think:
Variable: age → 22 Array: ages → [18, 19, 20, 21, 22]
23. Array vs Linked List
You'll study Linked Lists next after Strings, but it's useful to understand the basic difference.
Array
[10][20][30][40][50]
Elements are stored contiguously.
Linked List
[10] → [20] → [30] → [40] → [50]
Nodes can be stored in different memory locations and connected through pointers.
This gives them different performance characteristics.
24. Advantages of Arrays
1. Fast access
arr[index]
is generally:
O(1)
2. Simple
Arrays are easy to understand and use.
3. Memory efficient
They don't require pointer information for every element like a linked list does.
4. Good cache locality
Contiguous storage can make sequential processing efficient on modern computers.
5. Useful foundation
Arrays are used to build and understand many other concepts.
25. Disadvantages of Arrays
1. Fixed size
Traditional arrays have a fixed capacity.
2. Insertion can be expensive
Elements may need to be shifted.
O(n)
3. Deletion can be expensive
Again, elements may need to be shifted.
O(n)
4. Possible unused space
If you allocate:
1000 elements
but only use:
100 elements
the remaining capacity may be unused.
26. Important Array Problems
After understanding the basics, you should be able to solve problems such as:
Basic
- Print an array
- Find sum
- Find maximum
- Find minimum
- Count elements
- Calculate average
Searching
- Linear search
- Find first occurrence
- Find last occurrence
- Count occurrences
Modification
- Insert an element
- Delete an element
- Update an element
- Reverse an array
More challenging
- Find second largest
- Remove duplicates
- Find missing number
- Find duplicate number
- Move zeros to the end
- Rotate an array
- Merge two arrays
- Find pairs with a given sum
- Find maximum subarray sum
These problems develop your actual problem-solving skills.
27. Important Array Pattern
When solving an array problem, ask yourself:
1. What is the input size? ↓ 2. Do I need to traverse the array? ↓ 3. Do I need searching? ↓ 4. Do I need sorting? ↓ 5. Can I solve it in one pass? ↓ 6. What is the time complexity? ↓ 7. What is the space complexity?
This connects directly to the Complexity Analysis topic you just learned.
28. Example: Reverse an Array
Suppose:
[10, 20, 30, 40, 50]
We want:
[50, 40, 30, 20, 10]
A common approach uses two pointers:
left right ↓ ↓ 10 20 30 40 50
Swap:
50 20 30 40 10
Move pointers:
left right ↓ ↓ 50 20 30 40 10
Continue until the pointers meet.
This can be done in:
Time = O(n) Space = O(1)
This is an important example of efficient in-place array manipulation.
29. Static Array vs Dynamic Array
It's useful to distinguish them.
Static/fixed array
int arr[5];
Size is fixed.
Dynamic array
A dynamically resizable structure can grow when needed.
In C++, vector is the standard example:
vector<int> arr;
You can add elements:
arr.push_back(10); arr.push_back(20); arr.push_back(30);
It can automatically manage its storage.
You will encounter vector frequently when solving DSA problems in C++.
30. The Most Important Things to Remember
Array │ ├── Stores multiple values │ ├── Usually same data type │ ├── Uses index │ ├── Index starts at 0 │ ├── Elements stored contiguously │ ├── Random access → O(1) │ ├── Traversal → O(n) │ ├── Search → O(n) for linear search │ ├── Insertion → O(n) worst case │ └── Deletion → O(n) worst case
One simple example
int arr[5] = {10, 20, 30, 40, 50};
Think of it as:
Array ↓ ┌────┬────┬────┬────┬────┐ Index│ 0 │ 1 │ 2 │ 3 │ 4 │ ├────┼────┼────┼────┼────┤ Value│ 10 │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┴────┘
If you understand indexing, traversal, searching, insertion, deletion, memory layout, and complexity, you have the core foundation needed for arrays.