Loading W Code...
Foundation of all data structures - learn how arrays work in C++.
Imagine a row of identical safety deposit boxes or mail slots. Each slot is right next to the previous one, and all slots are numbered sequentially starting from 0. If you want to check the third box, you can walk directly to slot index 2 because you know exactly how far down the row it sits.
In computer science, an Array is a linear data structure that stores a collection of elements of the same data type at contiguous (adjacent) memory locations.
0-indexed).#include <iostream>
using namespace std;
int main() {
// Method 1: Declare and initialize
int numbers[5] = {10, 20, 30, 40, 50};
// Method 2: Declare first, assign later
int marks[3];
marks[0] = 85;
marks[1] = 90;
marks[2] = 78;
// Accessing elements
cout << "First element: " << numbers[0] << endl; // Output: 10
cout << "Third element: " << numbers[2] << endl; // Output: 30
// Array size
int size = sizeof(numbers) / sizeof(numbers[0]);
cout << "Array size: " << size << endl; // Output: 5
// Loop through array
cout << "All elements: ";
for (int i = 0; i < 5; i++) {
cout << numbers[i] << " ";
}
// Output: 10 20 30 40 50
return 0;
}Arrays can be structured in multiple dimensions depending on the complexity of the dataset:
i maps directly to Base Address + i * Element Size.0 is stored first, followed by Row 1, then Row 2.arr[i][j] is computed as Base Address + (i * ColumnCount + j) * Element Size.#include <iostream>
using namespace std;
int main() {
// 1D Array
int arr1D[5] = {1, 2, 3, 4, 5};
cout << "1D Array: ";
for (int i = 0; i < 5; i++) {
cout << arr1D[i] << " ";
}
cout << endl;
// 2D Array (3 rows, 4 columns)
int arr2D[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
cout << "2D Array (Matrix):" << endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
cout << arr2D[i][j] << " ";
}
cout << endl;
}
// Accessing specific element
cout << "Element at row 1, col 2: " << arr2D[1][2] << endl; // Output: 7
return 0;
}Understanding array operation bottlenecks is vital for technical interviews. Here is the operational breakdown:
O(n))Iterating through the array index-by-index using loops to inspect or print values.
O(n))Inserting a value at index i requires shifting all subsequent elements to the right by one position to maintain contiguous storage.
O(1)): Appending to the end (if space exists).O(n)): Inserting at the very front (index 0), forcing all n elements to shift.O(n))Removing a value at index i requires shifting all elements after it to the left to close the gap.
O(1)): Removing the last element.O(n)): Deleting the first element.O(n) / O(log n))O(n)): Checking elements one-by-one.O(log n)): Repeatedly halving the search space. Requires the array to be sorted first.#include <iostream>
using namespace std;
int main() {
int arr[10] = {5, 10, 15, 20, 25};
int n = 5; // Current number of elements
// 1. TRAVERSAL - Print all elements
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 2. INSERTION - Insert 12 at index 2
int insertPos = 2;
int insertVal = 12;
for (int i = n; i > insertPos; i--) {
arr[i] = arr[i - 1]; // Shift elements right
}
arr[insertPos] = insertVal;
n++;
cout << "After inserting 12 at index 2: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
// 3. DELETION - Delete element at index 3
int deletePos = 3;
for (int i = deletePos; i < n - 1; i++) {
arr[i] = arr[i + 1]; // Shift elements left
}
n--;
cout << "After deleting element at index 3: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
// 4. SEARCHING - Linear Search for 20
int target = 20;
int foundIndex = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
foundIndex = i;
break;
}
}
cout << "Element 20 found at index: " << foundIndex << endl;
// 5. UPDATING - Change value at index 1
arr[1] = 100;
cout << "After updating index 1 to 100: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}These fundamental patterns form the building blocks for solving complex DSA problems:
O(n) Time, O(1) Space)Traverse the array once, keeping a running record of the smallest or largest value encountered.
O(n) Time, O(1) Space)Use the Two-Pointer technique. Place one pointer at the start and one at the end, swap their elements, and move them inward until they meet.
O(n) Time, O(1) Space)Traverse and compare every pair of adjacent elements. If arr[i] > arr[i + 1] (for ascending order), the array is unsorted.
O(n) Time with Hash Map, O(n log n) with Sorting)Finding if two numbers sum to a target value. A core interview challenge solved efficiently using sorting & two-pointers, or a Hash Map.
#include <iostream>
#include <algorithm> // for swap
using namespace std;
// Find Maximum Element
int findMax(int arr[], int n) {
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
return maxVal;
}
// Reverse Array
void reverseArray(int arr[], int n) {
int start = 0, end = n - 1;
while (start < end) {
swap(arr[start], arr[end]);
start++;
end--;
}
}
// Check if Sorted (Ascending)
bool isSorted(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false;
}
}
return true;
}
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
int n = 8;
// Find Maximum
cout << "Maximum: " << findMax(arr, n) << endl; // Output: 9
// Check if Sorted
cout << "Is Sorted: " << (isSorted(arr, n) ? "Yes" : "No") << endl; // Output: No
// Reverse Array
reverseArray(arr, n);
cout << "Reversed: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl; // Output: 6 2 9 5 1 4 1 3
return 0;
}When an array is passed to a C++ function, it automatically decays into a pointer to its first element (arr[0]). This design choice has critical implications:
n) as an explicit second argument.O(1) space): C++ only copies the memory address (8 bytes on 64-bit platforms), preventing expensive copies of massive arrays.C++ does not allow returning raw arrays directly from functions. Standard alternatives include:
new keyword (must be cleared with delete[]).std::vector.#include <iostream>
using namespace std;
// Method 1: Array notation
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
// Method 2: Pointer notation (same as above)
void doubleElements(int* arr, int size) {
for (int i = 0; i < size; i++) {
arr[i] *= 2; // This modifies original array!
}
}
// Calculate sum
int arraySum(int arr[], int size) {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += arr[i];
}
return sum;
}
// Fill array with value
void fillArray(int arr[], int size, int value) {
for (int i = 0; i < size; i++) {
arr[i] = value;
}
}
int main() {
int numbers[] = {1, 2, 3, 4, 5};
int size = 5;
cout << "Original array: ";
printArray(numbers, size);
cout << "Sum: " << arraySum(numbers, size) << endl;
doubleElements(numbers, size);
cout << "After doubling: ";
printArray(numbers, size);
fillArray(numbers, size, 0);
cout << "After filling with 0: ";
printArray(numbers, size);
return 0;
}