Array

What is an array?Array kya hota hai?

An array stores elements of the same type in one contiguous block of memory. Because every element has the same size, the address of any element can be computed directly from its index, which is why access by index takes O(1) time.Array same type ke elements ko memory ke ek hi continuous block mein store karta hai. Har element ka size same hota hai, isliye kisi bhi index ka address seedha calculate ho jaata hai — isi wajah se index se access O(1) time mein hota hai.

Operations and their costOperations aur unki cost

Address calculation (1-D)Address calculation (1-D)

For an array A[lb … ub] with base address B and element size w bytes:Array A[lb … ub] ke liye, jiska base address B hai aur har element w bytes ka hai:

Address(A[i]) = B + (i − lb) × w

TipExample: A[−5 … 5] of 4-byte ints at base 1000. Address of A[2] = 1000 + (2 − (−5)) × 4 = 1028.Example: A[−5 … 5] of 4-byte ints, base 1000. A[2] ka address = 1000 + (2 − (−5)) × 4 = 1028.

Address calculation (2-D)Address calculation (2-D)

For A[lr … ur][lc … uc] with m rows and n columns, the array is laid out either row by row or column by column.A[lr … ur][lc … uc] mein m rows aur n columns hain. Array ya toh row-by-row store hota hai ya column-by-column.

Common mistakeCommon galtiRow-major multiplies by the number of columns (n); column-major multiplies by the number of rows (m). Mixing these up is the most common GATE mistake here.Row-major mein number of columns (n) se multiply karte hain; column-major mein number of rows (m) se. Inko mix karna GATE ki sabse common galti hai.

Special matricesSpecial matrices

• Lower-triangular n × n matrix stores n(n + 1)/2 non-zero elements.
• Row-major index of A[i][j] (i ≥ j, 1-indexed) in a lower-triangular store: i(i − 1)/2 + (j − 1).
• Tridiagonal matrix has 3n − 2 non-zero elements.
• Sparse matrices are stored as (row, col, value) triplets to save space.

• Lower-triangular n × n matrix mein n(n + 1)/2 non-zero elements store hote hain.
• Lower-triangular store mein A[i][j] (i ≥ j, 1-indexed) ka row-major index: i(i − 1)/2 + (j − 1).
• Tridiagonal matrix mein 3n − 2 non-zero elements hote hain.
• Sparse matrix ko space bachane ke liye (row, col, value) triplets mein store karte hain.

Arrays in CC mein arrays

int a[5] = {1, 2, 3, 4, 5};
int *p = a;          // array name decays to &a[0]
printf("%d", *(p + 2));   // 3, same as a[2]
printf("%d", 2[a]);       // also 3: a[i] == *(a + i) == i[a]
sizeof(a);                // 20 (5 × 4) — the whole array
sizeof(p);                // size of a pointer (e.g. 8)

Common mistakeCommon galtiInside a function, an array parameter is just a pointer, so sizeof gives the pointer size, not the array size.Function ke andar array parameter sirf ek pointer hota hai, isliye sizeof pointer ka size deta hai, array ka nahi.