.png)
C - Edition
DSA Chapter 2: Arrays
The Backbone of Data Structures
If you are new to array check these before moving forward
Introduction to Arrays, Addition of two arrays, Product of two matrices, Pointers & arrays,
Example on pointer & arrays, Passing arrays to functions,
What is an array?
An array in C is a collection of elements of the same type stored in contiguous memory locations. Elements are accessed by integer indices starting at 0.
Example:
int arr[5] = {10, 20, 30, 40, 50};
Why Are Arrays Important?
> Fast access: O(1) — direct indexing
> Easy iteration: O(n)
> Foundation for:
Strings
Matrices
Hashing
Dynamic arrays
Heaps
Segment trees
Array Time Complexities (Interview-Must Know)
Operation Time Complexity Explanation Access O(1) Direct index lookup Search O(n) Linear search Insert at end O(1)* Amortized (dynamic arrays) Insert at beginning O(n) Shifting required Delete at beginning O(n) Shifting required
Memory layout & indexing
-
Contiguous memory →
&arr[i+1] == &arr[i] + 1(scaled by element size). -
Access
arr[i]costs constant time O(1). -
Element size (
sizeof(type)) matters for pointer arithmetic.
Arrays vs Pointers — the relationship
-
The name
arrdecays to&arr[0]in most expressions (exceptsizeof(arr)and&arr). -
arr[i]is equivalent to*(arr + i). -
But
arr(a fixed-size array) andint *p(pointer) are different at compile time:sizeof(arr)gives total bytes;sizeof(p)gives pointer size.
Static vs Dynamic arrays
Static array — compile-time or block-scoped with fixed size:
int a[100];-
Pros: simple, no malloc overhead.
-
Cons: fixed size, stack usage (if local).
-
-
Dynamic array — allocated at runtime:
int *a = malloc(n * sizeof *a);-
Pros: flexible, use heap.
-
Must
free(a)when done. -
Handle allocation failures:
if (!a) { /* handle */ }.
-
Multidimensional arrays
-
2D static array:
int mat[3][4];→ contiguous storage row-major in C. -
Access
mat[i][j]→ element offseti * cols + j. -
For dynamic 2D arrays, you can allocate a single block (
malloc(rows*cols*sizeof)) and index manually, or allocate array of pointers (less contiguous).
Passing arrays to functions
-
Arrays decay to pointers; function signature typical:
void f(int arr[], int n) void f(int *arr, int n).-
You must pass the size separately if needed.
-
For 2D static arrays you need column size:
void f(int mat[][COLS])or use pointer-to-pointer or single-block trick.
Common operations & complexity
-
Access by index: O(1).
-
Traverse/search (linear): O(n).
-
Insert/delete at arbitrary index: O(n) (shifts).
-
Insert/delete at end (if space available): O(1).
-
Sorting: depends on algorithm (e.g., quicksort average O(n log n)).
-
Space complexity: in-place ops use O(1) extra (except recursion).
Pointer arithmetic examples
int a[3] = {1,2,3};
int *p = a; // points to a[0]
*(p + 2); // a[2]
Important implementation patterns (C-focused)
-
Iterate safely: always ensure index bounds. Undefined behavior on out-of-bounds.
-
Dynamic resizing (vector-like):
-
Double capacity when full; shrink optionally.
-
Use
realloccarefully (check returned pointer before replacing original).
-
-
Use
size_tfor sizes/indices — it is unsigned and standard for sizes. -
Initialization: static arrays default to zero if global/static; local automatic arrays contain garbage unless initialized.
-
Avoid returning pointer to local array — they go out of scope. Use
mallocor caller-allocated buffers.
Common pitfalls
-
Off-by-one errors (loop bounds).
-
Using signed vs unsigned for indexes causing logic issues when mixing with
size_t. -
Not checking
malloc/reallocresult. -
Freeing memory twice or using freed memory (use-after-free).
-
Mixing arrays with pointer arithmetic incorrectly for multi-dimensional indexing.
Useful array techniques for DSA
-
Two pointers — often used for sorted arrays (left/right indices).
-
Sliding window — for subarray problems with sum/length constraints.
-
Prefix sum — build
pref[i] = sum(arr[0..i-1])to get range sums O(1). -
Suffix arrays (not string SA but suffix sums) — useful for suffix queries.
-
In-place partitioning — e.g., Dutch National Flag for three-way partition (0/1/2).
-
Frequency arrays / counting sort — when value range small.
-
Hashing using arrays — direct-address tables for small ranges.
-
Bitset/bit-array — memory efficient (use
unsigned longand bit ops). -
Circular buffers / ring buffers — fixed-size queue using modulo indexing.
Strings and char arrays
-
C strings are
chararrays terminated by'\0'. Always ensure termination. -
Use
strlen,strcpy,strncpy(careful),memcmp,memcpyfor low-level ops. -
For performance in DSA, prefer manual loops with bounds checks over unsafe library misuse.
Example: dynamic array (simple vector)
typedef struct {
int *data;
size_t size;
size_t capacity;
} Vector;
void vector_init(Vector *v) {
v->size = 0;
v->capacity = 4;
v->data = malloc(v->capacity * sizeof *v->data);
}
void vector_push(Vector *v, int x) {
if (v->size == v->capacity) {
size_t newcap = v->capacity * 2;
int *tmp = realloc(v->data, newcap * sizeof *v->data);
if (!tmp) { /* handle OOM */ return; }
v->data = tmp;
v->capacity = newcap;
}
v->data[v->size++] = x;
}
void vector_free(Vector *v) {
free(v->data);
v->data = NULL;
v->size = v->capacity = 0;
}
How arrays fit into the DSA roadmap
-
Arrays → fundamental for sorting, searching, two pointers, sliding window, hashing.
-
Many more advanced DS (segment trees, Fenwick trees, suffix arrays) are built on array concepts.
-
Master arrays first; then move to linked lists → stacks/queues → trees → graphs → DP.
Most Important Array Interview Questions
These are mandatory. Companies repeatedly ask them.
-
Find largest and smallest element
-
Reverse an array
-
Left rotate and right rotate array
-
Remove duplicates
-
Find missing number in 1…n
-
Find the second largest element
-
Count frequency of elements
-
Move all zeros to end
-
Kadane’s algorithm (max subarray sum)
-
Two-sum problem
-
Pair with given sum
-
Sort 0s,1s,2s (Dutch National Flag problem)
C Edition – 20 Practice Questions
-
Write a C program to find the largest element in an array.
-
Write a C program to find the smallest element in an array.
-
Write a C program to search for an element in an array using linear search.
-
Write a C program to reverse an array without using a second array.
-
Write a C program to insert an element at a given position in an array.
-
Write a C program to delete an element from a given index in an array.
-
Write a C program to count the frequency of each element in an array.
-
Write a C program to find the second largest element in an array.
-
Write a C program to remove duplicate elements from an array.
-
Write a C program to print all unique elements of an array.
-
Write a C program to count the total number of even and odd numbers in an array.
-
Write a C program to left rotate an array by one position.
-
Write a C program to right rotate an array by one position.
-
Write a C program to left rotate an array by K positions.
-
Write a C program to merge two arrays into a third array.
-
Write a C program to find the missing number in an array containing 1 to n.
-
Write a C program to find the sum and average of array elements.
-
Write a C program to check whether an array is sorted or not.
-
Write a C program to copy all elements from one array to another.
-
Write a C program to find the maximum subarray sum (Kadane’s algorithm).
✔ Conclusion
Arrays are the strongest base for mastering:
-
Searching
-
Sorting
-
Recursion
-
Backtracking
-
Dynamic Programming
-
Graphs
-
Trees
Mastering arrays is the first step to cracking 90% of interviews.
ALSO CHECK
ALSO CHECK
Comments
Post a Comment