Arrays and Strings

A computer does not "find" the element you wrote as A[5] — it computes the memory address with a formula and jumps there in one step. Master that one formula, and every multidimensional and pointer question in GATE becomes trivial; misread it, and you lose three easy marks every year.

Definition: A one-dimensional array is a sequence of equally-sized memory cells stored contiguously, accessed by an integer index.

Definition: The base address of an array is the memory address of its first element. The word size w is the number of bytes each element occupies.

The Master Formula

For a 1-D array A declared with lower bound L, the address of element A[i] is:

Address(A[i]) = Base + (i − L) × w

where Base is the address of A[L] (the first element), and w is the size of each element in bytes. The formula has only two ideas: (i − L) is the number of slots from the start, and multiplying by w converts slot count into bytes.

In C, all arrays start at index 0, so L = 0, and the formula collapses to the familiar form:

Address(A[i]) = Base + i × w

In Pascal, FORTRAN, or any language where you can declare an array as A[5..15], L is non-zero, and you must subtract it. This subtraction is the single most common source of GATE errors.

Why Subtract L?

Imagine A is declared from index 10 to 20. The first cell is A[10], not A[0]. If you ask for A[12], you are at the third cell — that is, two slots past the base, not twelve. The (i − L) term shifts your thinking so that the first element is always at offset zero, regardless of how the programmer chose to label the indices. This is what makes the formula language-agnostic.

Why it matters: GATE consistently asks "given Base = 1000, element size 4 bytes, lower bound 5, find the address of A[10]." A student who applies the formula gets it in 5 seconds: 1000 + (10 − 5) × 4 = 1000 + 20 = 1020. A student who forgets to subtract 5 gets 1040 — a confident wrong answer. Examiners design the distractors around exactly this mistake.

Real-world example: Consider a 1-D int array int A[100] in C running on a 64-bit machine. With sizeof(int) = 4 bytes and base address 0x7ffd1000, A[37] sits at 0x7ffd1000 + 37 × 4 = 0x7ffd1094. The C compiler emits a single lea (load effective address) instruction that computes precisely this expression at runtime. The formula is not just exam fodder — it is the physical machine operation.

Common misconception: "The address of A[i] is Base + i × w in every language." False. The shortcut Base + i × w only works when L = 0. The general formula is always Base + (i − L) × w. GATE has tested this distinction in multiple years (notably with arrays declared as A[−5..5] or A[1..10]).

Worked Example — Non-Zero Lower Bound

Question: A 1-D array A is declared as A[5..50] with each element occupying 4 bytes. If the base address is 1000, find the address of A[30].

Solution:
Step 1: Identify the parameters. Base = 1000, L = 5, i = 30, w = 4.
Step 2: Apply the master formula: Address(A[30]) = Base + (i − L) × w = 1000 + (30 − 5) × 4.
Step 3: Compute (i − L) = 25. This is the count of cells between A[5] and A[30].
Step 4: Multiply by w = 4 bytes per cell: 25 × 4 = 100 bytes of offset.
Step 5: Add to base: 1000 + 100 = 1100.
Conclusion: A[30] is at address 1100. Verification: there are 25 cells before A[30] starting from A[5], each occupying 4 bytes, so the offset is 25 × 4 = 100, matching.

Total Memory Occupied

For an array of n elements, each occupying w bytes, the total memory is simply n × w bytes. If A is declared as A[L..U], then n = U − L + 1 (don't forget the +1 — both endpoints are included). For A[5..50], n = 50 − 5 + 1 = 46 cells, occupying 46 × 4 = 184 bytes.

The "+1 trap" is another favourite of paper-setters. Always remember: number of elements from L to U inclusive equals U − L + 1, not U − L.

Why This Underpins Higher Dimensions

The 1-D formula is the seed. The 2-D formula in row-major order for an array A[m][n] is:

Address(A[i][j]) = Base + ((i − L₁) × n + (j − L₂)) × w

and in column-major order:

Address(A[i][j]) = Base + ((j − L₂) × m + (i − L₁)) × w

Both reduce to repeated application of "count slots, multiply by width." If you cannot do the 1-D formula in your sleep, the 2-D and 3-D versions become a nightmare. So practise the 1-D drill until it feels automatic.

A Subtle Pointer-Arithmetic Twist

In C, the expression A + i is not equal to (char *)A + i. The compiler scales i by sizeof(*A) automatically. So if A is int *, then A + 1 is 4 bytes ahead of A, not 1 byte. GATE has framed questions where you must decide whether the offset was already scaled or whether you must scale it yourself. The rule is: typed pointer arithmetic scales automatically; raw byte arithmetic does not.

:::compare

:::keypoints

• Master formula: Address(A[i]) = Base + (i − L) × w.
• In C arrays L = 0 always; the formula simplifies to Base + i × w.
• Always subtract the lower bound before scaling by the element size.
• Number of elements from L to U inclusive is U − L + 1, not U − L.
• Total memory of n-element array = n × w bytes.
• Typed pointer arithmetic in C scales offsets by sizeof(*p) automatically.
• The 1-D formula is the foundation for all row-major and column-major 2-D addressing.
  :::

:::memory
"Count the gap from the lower bound, scale by the width." Whenever you see A[i], whisper "i minus L, times w, plus base."
:::

:::recap

• The address formula is a two-step machine: compute slot offset, then scale by element size.
• Subtracting the lower bound L is non-negotiable for arrays not starting at index zero.
• Off-by-one errors come from forgetting the +1 when counting elements between two indices.
• All higher-dimensional addressing extends this same idea — perfect the 1-D version first.
  :::

Some numbers refuse to fit into the neat p/q box, no matter how clever your algebra. These restless numbers — root 2, root 3, root 5, pi — are called irrational, and proving they are irrational is one of the most elegant exercises in your NCERT Class 10 chapter.

Definition: A rational number is any number that can be written in the form p/q, where p and q are integers and q is not zero. Examples include 3, -7/4, 0, and 0.25 (which is 1/4).

Definition: An irrational number is any real number that cannot be written as p/q with integers p and q. Its decimal expansion is non-terminating and non-repeating. Examples include the square root of 2, the square root of 3, the square root of 5, and pi.

A key theorem we will lean on

Before any irrationality proof, we recall this theorem (a consequence of the Fundamental Theorem of Arithmetic, which says every integer greater than 1 has a unique prime factorisation):

If p is a prime number and p divides a^2 (where a is a positive integer), then p also divides a.

The intuition is simple. When you square a number, every prime in its factorisation appears with an even exponent. So if a prime p shows up inside a^2, it must already have been inside a — at least once. We use this fact like a hammer in every proof that follows.

Method: proof by contradiction

To prove a number is irrational, mathematicians use the classic strategy called proof by contradiction. The steps are:

1. Assume the opposite — pretend the number IS rational, so it can be written as p/q.
2. Insist that the fraction is in lowest terms, meaning the only common factor of p and q is 1. (Every rational can be reduced to lowest terms, so this costs us nothing.)
3. Do honest algebra. At some point you will discover that p and q share a prime factor after all.
4. That contradicts the lowest-terms assumption. So our original assumption was false, and the number must be irrational.

This idea is centuries old but still feels magical: we prove a number is not rational by pretending it is and watching the pretence collapse.

Worked example — root 3 is irrational

Question: Prove that the square root of 3 is irrational.

Solution:
Step 1: Assume, for contradiction, that root 3 is rational. Then root 3 = p/q for some integers p, q with q non-zero, and the fraction p/q is in lowest terms (gcd(p, q) = 1).
Step 2: Square both sides: 3 = p^2 / q^2, so 3 q^2 = p^2. This means 3 divides p^2.
Step 3: By the key theorem (with p = 3), since 3 is prime and 3 divides p^2, it follows that 3 divides p. Write p = 3m for some integer m.
Step 4: Substitute back: 3 q^2 = (3m)^2 = 9 m^2, so q^2 = 3 m^2. This means 3 divides q^2, and again by the theorem, 3 divides q.
Step 5: But now 3 is a common factor of p and q — contradicting our lowest-terms assumption in Step 1.
Conclusion: Our assumption was false. Hence root 3 is irrational.

The exact same template proves that root 2, root 5, root 7 and every root of a prime is irrational. NCERT chapter 1 asks for at least one such proof — examiners may pick any prime.

Why it matters

Irrational numbers complete the real number line. Without them, the line would be full of microscopic holes — the point on a 1-by-1 square's diagonal (length root 2) would have no number to label it. The Class 10 board exam tests three abilities: stating what irrational means, executing the proof by contradiction cleanly, and combining rational and irrational numbers under the closure rules. Mastery here also feeds directly into surds, logarithms and the completeness of real numbers that you will meet in Class 11.

Real-world example

Pi (pi), the ratio of a circle's circumference to its diameter, is irrational. That is why your school calculator can only ever approximate the area of a circle — every digit of pi after the decimal is a fresh, unrepeating value. When the Mangalyaan probe was navigated to Mars, ISRO engineers carried pi to dozens of decimal places because every truncation introduces error. The irrationality of pi is the reason that "exact" trajectory work always uses the symbol pi instead of a decimal.

Common misconception

The most common mistake is forgetting to state that p/q is in lowest terms at the very start. Without that condition, finding that 3 divides both p and q does not contradict anything — the fraction simply was not in simplest form. Another error: claiming a number is irrational "because it looks messy" or "because the calculator does not show a pattern." Looks can deceive — 1/7 = 0.142857142857... looks endless on screen, but it actually repeats and is perfectly rational.

Useful closure facts

These three facts get tested in MCQ form:

• Rational + irrational = irrational. (Example: 2 + root 3 is irrational.)
• A non-zero rational times an irrational = irrational. (Example: 5 root 2 is irrational.)
• Sum of two irrationals may be rational or irrational. (Example: root 2 + (-root 2) = 0, which is rational.)

:::compare

:::keypoints

• An irrational number cannot be written as p/q where p, q are integers and q is non-zero.
• The decimal expansion of an irrational number is non-terminating and non-repeating.
• To prove a number is irrational, assume it is rational in lowest terms, then derive a contradiction.
• Key theorem: if a prime p divides a^2, then p divides a.
• Forgetting the lowest terms condition is the most common proof error.
• Rational + irrational is always irrational; non-zero rational times irrational is irrational.
• Square roots of all primes (2, 3, 5, 7, 11, ...) are irrational by the same template.
  :::

:::memory
"ALAS" — Assume rational, write in Lowest terms, do Algebra, find Shared factor (contradiction). Each letter is a step in the proof template. Once you hear "prove irrational", the word ALAS should reach for the chalk for you.
:::

:::recap

• Rational means expressible as p/q; irrational means it cannot be expressed that way.
• Proof by contradiction is the standard NCERT method.
• The proof always ends by showing p and q share a prime factor — contradicting lowest terms.
• Pi, root 2, root 3, root 5 are the standard irrational examples to remember.
  :::

"Find the molecular formula" is one of the most reliable easy-marks questions in NEET Chemistry. The path from a percentage analysis to the actual molecular formula is always the same four steps; once you internalise the algorithm, you can solve these in under a minute.

Definition: Empirical formula is the simplest whole-number ratio of atoms in a compound.

Definition: Molecular formula is the actual number of atoms of each element in one molecule; it is always an integer multiple of the empirical formula, where the multiplier n = molar mass / empirical mass.

Setting up the problem

We are given a compound that, on combustion analysis, was found to contain 40% C, 6.7% H, 53.3% O by mass. Its molar mass, measured separately (say by vapour density or mass spectrometry), is 60 g/mol. We are asked: what is the molecular formula?

The trick that makes percentages painless is to assume you have exactly 100 g of the compound. Then the percentages become grams directly, and you avoid carrying "%" through every line.

The four-step algorithm

Step 1: Convert mass percentages to moles.
Step 2: Divide every mole value by the smallest one to get the simplest ratio.
Step 3: Write the empirical formula and compute its empirical mass.
Step 4: Find n = (molar mass) / (empirical mass); multiply subscripts by n.

That is the entire method. Let us walk through it carefully.

Worked example — full execution

Question: A compound contains 40 % C, 6.7 % H, 53.3 % O by mass. Its molar mass is 60 g/mol. Find the molecular formula.

Solution:
Step 1: Assume 100 g of the compound, so we have 40 g of C, 6.7 g of H and 53.3 g of O.

Convert to moles using atomic masses (C = 12, H = 1, O = 16):

• Moles of C = 40 / 12 = 3.33
• Moles of H = 6.7 / 1 = 6.7
• Moles of O = 53.3 / 16 = 3.33

Step 2: Divide by the smallest mole value (3.33):

• C : 3.33 / 3.33 = 1
• H : 6.7 / 3.33 = 2.01 ≈ 2
• O : 3.33 / 3.33 = 1

Step 3: The simplest whole-number ratio is C : H : O = 1 : 2 : 1, so the empirical formula is CH₂O. Its empirical mass = 12 + 2(1) + 16 = 30 g/mol.

Step 4: Find n = molar mass / empirical mass = 60 / 30 = 2. Multiply each subscript of the empirical formula by 2 to get the molecular formula C₂H₄O₂.

Conclusion: The compound is C₂H₄O₂ — acetic acid (CH₃COOH).

Why this algorithm works (the WHY)

Percentages by mass tell us the mass of each element in a fixed amount of compound. Dividing by atomic mass converts mass to moles, and moles are the same thing as "number of atoms" up to Avogadro's constant. So the mole ratio is the atom ratio. Dividing by the smallest mole value rescales that ratio so the smallest term is 1, which is the cleanest way to read off small integer subscripts.

The factor n comes from the fact that the empirical formula carries only the ratio; it loses the absolute count. The measured molar mass restores that count.

Why it matters

Why it matters: This kind of question appears almost every year in NEET, JEE Main and CBSE Class 11 boards. It is also the conceptual foundation for combustion analysis, percent purity problems, and the elemental analysis component of organic chemistry. If you can do this confidently, you will pick up 4 easy marks that many students lose to silly arithmetic.

Real-world example

Real-world example: The compound we just identified — acetic acid — is the active ingredient in vinegar (about 5 % by mass in table vinegar). When a food chemist sends an unknown organic acid for elemental analysis and gets back 40 / 6.7 / 53.3 for C / H / O with molar mass 60, this exact calculation is how they conclude "yes, this is acetic acid." The same method, with nitrogen included, is how forensic labs identify drug compounds.

Handling messy ratios

If after Step 2 you get values like 1, 1.5 — multiply every term by 2 (giving 2, 3). If you get 1, 1.33 or 1, 1.67 — multiply by 3 (giving 3, 4 or 3, 5). The tip in your fragment is the key rule:

• ratio ≈ 0.33 or 0.67 → multiply by 3
• ratio ≈ 0.5 → multiply by 2
• ratio ≈ 0.25 or 0.75 → multiply by 4
• ratio ≈ 0.2 → multiply by 5

Do not round 1.5 down to 1 or up to 2 — that gives the wrong formula. Multiply instead.

Always verify

Always verify: once you have your molecular formula, compute its molar mass back from atomic masses and check it matches the given molar mass.

For C₂H₄O₂: 2(12) + 4(1) + 2(16) = 24 + 4 + 32 = 60 g/mol. ✓ Matches.

This 10-second check has saved thousands of students from a careless subscript error.

Common misconception

Common misconception: "Empirical formula and molecular formula are the same thing." They coincide only when n = 1. For water (H₂O, molar mass 18) both are H₂O. For glucose, the empirical is CH₂O (mass 30) but the molecular is C₆H₁₂O₆ (mass 180, so n = 6). And our acetic-acid example also has empirical CH₂O — three different molecules can share an empirical formula. You need the molar mass to distinguish them.

Another common error: forgetting that the percentages must add to 100 %. If C + H = 46.7 % and no oxygen is mentioned, assume the remaining 53.3 % is the oxygen (or whichever element is implied by the chemistry). NEET sometimes tests this — read carefully.

:::compare

:::keypoints

• Assume 100 g of compound — % becomes grams instantly.
• moles_i = mass_i / atomic_mass_i.
• Divide every mole value by the smallest to get the atom ratio.
• If ratios aren't whole numbers, multiply (×2 for .5, ×3 for .33/.67, etc.). Never round!
• n = molar_mass / empirical_mass. Multiply subscripts by n.
• Verify by recomputing the molar mass of your final formula.
• Empirical formula is unique up to a positive integer multiplier; molar mass picks the right one.
  :::

:::memory
MMRM: Mass-percent → Moles → Ratio → Molecular formula. Four letters, four steps. The order never changes.
:::

:::recap

• Four-step algorithm: percentages → moles → smallest ratio → multiply by n.
• n = actual molar mass / empirical mass.
• Always recompute the molar mass of your answer to catch arithmetic slips.
• Empirical and molecular formulas are equal only when n = 1.
  :::

Access by index: O(1) (random access via address arithmetic). Search (unsorted): O(n) linear scan; (sorted): O(log n) with binary search. Insertion/deletion at the END of a dynamic array: O(1) amortized; at an arbitrary position: O(n) because elements must shift. Inserting at the BEGINNING is worst case—every element shifts, O(n). Memory aid: 'arrays are cheap to read, expensive to reshape.' Updating an element in place is O(1). The fixed-size limitation forces O(n) resizing in static arrays. Contrast with linked lists, which give O(1) insert/delete at a known node but O(n) access. GATE frequently tests this access-vs-modify tradeoff.

You append a million items to a Java ArrayList and the average time per append is constant. Yet somewhere inside, the array had to be reallocated and every existing element copied — multiple times. How can a sometimes-expensive operation have a constant average cost? The answer is amortized analysis, and the dynamic-array doubling trick is the cleanest example in all of algorithms.

Definition: A dynamic array is a contiguous array that grows automatically when it runs out of space, hiding the resize from the caller. C++ std::vector, Java ArrayList, Python list, and Go slice are all dynamic arrays.

Definition: Amortized cost is the cost of an operation averaged over a worst-case sequence of operations. It is not the same as the average-case cost, which depends on a probability distribution over inputs.

The growth strategy that makes everything work

When a dynamic array is full and a new append arrives, the implementation:

1. Allocates a new buffer of larger capacity.
2. Copies all n current elements to the new buffer.
3. Frees the old buffer.
4. Appends the new element to the new buffer.

The cost of one such resize is O(n) — every element must be copied. If we did this on every single append, total cost across n appends would be 1 + 2 + 3 + ... + n = O(n²), and the per-append cost would be O(n). That is unacceptable.

The trick is to double the capacity each time the array fills up. Now a resize happens only when the current size hits a power of 2.

The geometric-series argument

Suppose we start with capacity 1 and append n elements. Resizes happen at sizes 1, 2, 4, 8, ..., up to roughly n. The cost of the resize at size 2^i is 2^i (we copy 2^i elements). Summing all resize costs:

1 + 2 + 4 + 8 + ... + n ≤ 2n

This is a geometric series with ratio 2. The total resize work across all n appends is bounded by 2n, which is O(n). Add the n cheap append steps (one assignment each), and the grand total is 3n = O(n).

Per append, the amortized cost is total / n = O(1). A constant. That is the entire payoff.

You can also derive this the other way around: the cost of n appends is total = n + n/2 + n/4 + n/8 + ... < 2n if you write the series starting from the final resize and counting backwards. Same answer, same logic.

Why doubling, and not adding a constant?

What if, instead of doubling, we grew the array by a constant amount c each time (say, c = 10)? The number of resizes would be roughly n/c, and the i-th resize would cost i × c elements copied. Total resize work:

c × (1 + 2 + 3 + ... + n/c) = c × (n/c)(n/c + 1)/2 ≈ n²/(2c)

That is O(n²) total, or O(n) per append amortized — disastrously worse. Constant-amount growth turns a near-free operation into a quadratic-time disaster on long sequences.

This is why every modern dynamic-array implementation uses geometric growth. The growth factor does not have to be 2 — C++ vector implementations have used 1.5, Python list uses about 1.125 with offsets, Java ArrayList uses 1.5 — but the principle is identical. As long as the new capacity is a constant multiple greater than the old, the geometric series converges to O(n) total work.

Why it matters: Algorithmic correctness alone does not make a data structure usable. The asymptotic constant matters in practice, and the geometric growth factor is a knob real implementations tune to balance memory waste (a larger factor wastes more) against re-copy frequency (a smaller factor copies more often).

Three flavours of amortized analysis

Amortized analysis can be done three different ways, all yielding the same answer:

• Aggregate method: Sum the total cost of n operations, divide by n. This is what we just did with the geometric series.
• Accounting method: Charge each cheap append a small extra "credit" that pays for future resizes. Show that the credits accumulated by the time a resize is needed exactly cover its cost. For doubling, each append banks 3 units of credit; when a resize from m to 2m happens, the m credits banked since the last resize cover the m copy operations.
• Potential method: Define a potential function Φ that measures stored work. Show that amortized cost = actual cost + ΔΦ ≤ constant for every operation.

GATE has tested all three. For the dynamic-array problem the aggregate method is the cleanest, but the accounting method is the most intuitive — each append "pre-pays" a little for its share of a future resize.

Worst case versus amortized

A single append in the worst case is O(n) — exactly when the resize triggers. Amortized cost is O(1) because the expensive operations are rare and their cost is spread over the many cheap operations they enable.

In a hard real-time system, you may care about the worst-case latency of a single operation, not the average. For such systems, a different data structure (linked list, or a deamortized variant) may be preferred. But for almost every general-purpose application, amortized O(1) is exactly what you want — and explains why ArrayList in Java or vector in C++ feel "constant time" even though they are doing periodic batch reorganisations.

Worked example

Question: Starting from a dynamic array with capacity 1, perform 17 appends. Compute the total copy work using the doubling strategy.

Solution:
Step 1: Resizes happen when the array is full. With initial capacity 1, resizes occur at sizes 1, 2, 4, 8, 16. Copy work at each resize: 1, 2, 4, 8, 16 elements.
Step 2: Total copy work = 1 + 2 + 4 + 8 + 16 = 31.
Step 3: Cheap append work = 17 (one slot-write per append).
Conclusion: Total = 31 + 17 = 48 unit operations for 17 appends, or about 2.8 per append. As n grows, this constant tightens toward 3 — confirming the O(1) amortized bound.

Real-world example

Real-world example: Pinterest, Flipkart, and most large Indian e-commerce backends store user-session event logs in dynamically resizable buffers before flushing them to a database. A user might trigger a few events or a few thousand in a single session. The dynamic array gives O(1) amortized append for the common case, and the rare resize copy is invisible because it is amortized over millions of cheap appends. Without geometric growth, the server would spend quadratic time per session — unacceptable at scale.

Common misconception

Common misconception: "Amortized cost is the same as average-case cost." Wrong. Average-case cost depends on a probability distribution over inputs — for example, the average lookup time in a hash table assuming uniformly distributed keys. Amortized cost is a worst-case guarantee on a sequence: no matter how the adversary orders n appends, the total cost is O(n). It is a deterministic bound, not a statistical average.

:::compare

:::keypoints

• Dynamic arrays grow geometrically — typically doubling — when full.
• Resize cost is O(n), but happens only at sizes 1, 2, 4, 8, ... — rare.
• Total work over n appends is bounded by geometric series ≤ 2n.
• Amortized cost per append is O(1) — a worst-case-sequence guarantee.
• Constant-amount growth would be O(n²) total, catastrophic at scale.
• Amortized ≠ average; amortized is deterministic, average is probabilistic.
• A single append can still cost O(n) — only the sequence average is O(1).
  :::

:::memory
"Doubling makes the rare expensive copy pay for many cheap appends." The geometric series 1 + 2 + 4 + ... + n < 2n is the entire mathematics of dynamic arrays — recall this sum, you recall the algorithm.
:::

:::recap

• Doubling dynamic arrays give O(1) amortized append, O(n) worst case for one append.
• Geometric (not constant) growth is what makes this work.
• Amortized analysis is a worst-case sequence bound, not a probabilistic average.
• The total copy work across n appends is at most 2n.
  :::

Reversing an array sounds trivial — and yet it is the operation behind rotation, palindrome checking, and several classic GATE PYQ questions. Getting the loop bound and index arithmetic right is the difference between a clean O(n) solution and a subtle bug.

Definition: An in-place algorithm modifies its input directly using only a small, constant amount of extra memory (O(1) auxiliary space), rather than constructing a new copy of the data.

Definition: An array reversal is the operation that rearranges the elements of an array so that the element originally at index i ends up at index n − 1 − i, where n is the array's length.

The Two-Pointer Idea

The clean way to reverse an array in place is the two-pointer technique:

1. Place pointer i at the start (index 0).
2. Place pointer j at the end (index n − 1).
3. Swap A[i] with A[j].
4. Move i forward, move j backward.
5. Stop when i ≥ j.

A loop-based version using a single index expresses the same idea:

for i = 0 to n/2 - 1:
    swap(A[i], A[n - 1 - i])

The expression n − 1 − i is the mirror image of index i about the centre of the array. Swapping each i with its mirror, only over the first half, reverses the array. The middle element (when n is odd) maps to itself — no swap needed.

Why n/2 — Not n

The most common bug is writing for i = 0 to n - 1. This swaps each pair twice: once when i is on the left of the pair, and once when i is on the right. Two swaps cancel out — and the array returns to its original state. Always use n/2 as the upper bound (use integer division).

Complexity Analysis

• Time complexity: O(n). The loop runs n/2 times, each iteration performs one swap (three constant-time operations). The total is c × n/2, which is Θ(n).
• Space complexity: O(1). Only one temporary variable is needed for the swap (or none if using (a, b) = (b, a) tuple-assignment in Python). No new array is allocated.

This makes reversal the gold standard of in-place operations — minimal memory, optimal time.

Building Block for Rotation

Reversal becomes the elegant primitive for array rotation. To rotate an array of length n by k positions to the left:

1. Reverse the first k elements: A[0..k−1].
2. Reverse the remaining n − k elements: A[k..n−1].
3. Reverse the entire array A[0..n−1].

Result: A is rotated left by k. Why does this work? Each of the three reversals is its own inverse; the composition of the three reversals equals a cyclic left-shift by k. Total cost: three O(n) reversals = still O(n) time, O(1) extra space. This is the famous "reversal algorithm" that GATE has tested at least twice as a one-mark MCQ.

For right rotation by k, simply reverse-rotate by n − k (or apply the same three reversals in opposite order).

Why it matters: GATE CSE Data Structures section regularly tests array manipulation under tight complexity bounds. Knowing both the in-place trick and the rotation-by-reversal idea covers a large slice of probable questions.

Real-world example: WhatsApp message bubbles displayed bottom-up are conceptually the reverse of the chronological log. Internally, a fixed-size buffer is reversed in place to keep memory usage flat — exactly the pattern this lesson teaches.

Common misconception: "Reversing an array of size n takes n swaps." Wrong. It takes exactly ⌊n/2⌋ swaps. For n = 6, that is 3 swaps: (0,5), (1,4), (2,3). For n = 7, also 3 swaps: (0,6), (1,5), (2,4); the middle element (index 3) stays put.

Question: An array A of size n = 5 holds [10, 20, 30, 40, 50]. Show each step of the in-place reversal.
Solution:
Step 1: i = 0, j = 4. Swap A[0] and A[4]. Array becomes [50, 20, 30, 40, 10].
Step 2: i = 1, j = 3. Swap A[1] and A[3]. Array becomes [50, 40, 30, 20, 10].
Step 3: i = 2, j = 2. They meet; stop. Index 2 (the middle) is unchanged.
Conclusion: After 2 swaps the array is reversed. The loop runs ⌊5/2⌋ = 2 times.

Question: An array of 10 elements is rotated left by 3 using the reversal algorithm. How many element-swaps occur in total?
Solution:
Step 1: Reverse first 3 elements → ⌊3/2⌋ = 1 swap.
Step 2: Reverse remaining 7 elements → ⌊7/2⌋ = 3 swaps.
Step 3: Reverse all 10 elements → ⌊10/2⌋ = 5 swaps.
Conclusion: Total swaps = 1 + 3 + 5 = 9. Still O(n), as 9 ≤ 3n/2.

A GATE Twist

If a question asks for the value of the loop counter when the loop terminates in C-style:

for (i = 0; i < n/2; i++)
    swap(A[i], A[n-1-i]);

After execution, i = n/2 (with integer division). For n = 5, i = 2. For n = 6, i = 3. This is a favourite micro-question for GATE PYQ MCQs.

:::compare

:::keypoints

• Loop from i = 0 to n/2 − 1, swap A[i] with A[n − 1 − i].
• Use n/2 as the bound, never n — going to n reverses twice.
• Time O(n), space O(1) — the canonical in-place pattern.
• For odd n, the middle element stays put automatically.
• Rotate-left by k = reverse(first k) + reverse(rest) + reverse(whole).
• Recursion is not in-place because of stack-frame overhead.
• Exactly ⌊n/2⌋ swaps are performed.
  :::

:::memory
"Two pointers walking inward — stop when they meet or cross." That single sentence captures the entire algorithm, the loop bound, and the termination condition.
:::

:::recap

• In-place reversal uses the swap A[i] ↔ A[n − 1 − i] for i in [0, n/2).
• It runs in O(n) time and O(1) extra space — exactly ⌊n/2⌋ swaps.
• Three reversals compose into a rotation, the GATE-favourite trick.
• The most common bug is iterating up to n instead of n/2.
  :::

Naive string matching slides the pattern (length m) over the text (length n) one position at a time, re-comparing from scratch on each mismatch: worst case O(nm). KMP (Knuth-Morris-Pratt) precomputes a failure/LPS (Longest Proper Prefix which is also Suffix) array in O(m), then scans the text once without backtracking, giving O(n + m) total. Memory aid: 'KMP never re-reads a text character.' The LPS array tells how far to shift the pattern on a mismatch by reusing already-matched prefix information. KMP space is O(m) for the LPS array. Rabin-Karp uses hashing for average O(n+m) but worst-case O(nm) due to hash collisions.

The Knuth-Morris-Pratt (KMP) algorithm matches a pattern against a long text in linear time, and its whole speed advantage comes from one tiny pre-computed array — the LPS array, also called the failure function. Mastering how to build LPS in O(m) is the single highest-yield investment for any GATE string-matching question.

Definition: For a pattern P of length m, LPS[i] is the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]. "Proper" means the prefix cannot be the entire substring itself.

Definition: A prefix of a string is any substring that starts at index 0; a suffix is any substring that ends at the last index. A border of a string is a substring that is simultaneously a (proper) prefix and a suffix — LPS records the longest border at every position.

Why LPS exists at all

A naïve string match restarts from scratch whenever a mismatch occurs, throwing away the information it has just learned about the pattern. That's why naïve matching runs in O(nm) in the worst case (think pattern "AAAAB" in text "AAAAAAAAAB").

KMP's insight is — if you have matched the first j characters of the pattern against the text and then the (j+1)-th fails, you already know what those first j characters of the text look like (they are exactly P[0..j-1]). So you can ask "what's the longest prefix of the pattern that is also a suffix of the j characters I just matched?" That's LPS[j-1]. By jumping the pattern index back to LPS[j-1] instead of zero, KMP never re-examines a text character — giving you O(n + m) overall.

Building the LPS array for ABABACA

Following the example from the source, pattern = "ABABACA":

• "A" → 0 (a single character has no proper border)
• "AB" → 0 (no character matches the start)
• "ABA" → 1 (prefix "A" equals suffix "A")
• "ABAB" → 2 (prefix "AB" equals suffix "AB")
• "ABABA" → 3 (prefix "ABA" equals suffix "ABA")
• "ABABAC" → 0 (the trailing "C" kills every border — no prefix of the pattern starts with "C")
• "ABABACA" → 1 (only "A" matches as border)

So LPS = [0, 0, 1, 2, 3, 0, 1].

The two-pointer construction

The standard algorithm uses two indices, len (length of the current longest border) and i (current position):

len = 0
LPS[0] = 0
i = 1
while i < m:
    if P[i] == P[len]:
        len = len + 1
        LPS[i] = len
        i = i + 1
    else:
        if len != 0:
            len = LPS[len - 1]   # fall back, do not advance i
        else:
            LPS[i] = 0
            i = i + 1

Even though there is a loop inside a loop, each iteration either advances i or strictly decreases len. Since len cannot fall below zero and i is bounded by m, total work is O(m). This amortised analysis is a favourite GATE pen-and-paper exercise.

Using LPS during the actual match

Now, during text matching, suppose you have matched j characters of the pattern and the next text character does not match P[j]. Instead of restarting at P[0], KMP sets j = LPS[j-1] and tries again with the same text index. The text index never moves backward, which is the whole reason KMP is O(n + m) for a text of length n.

If j = 0 and there is still a mismatch, only then do you advance the text index. This is the second key invariant — the text pointer is monotonically non-decreasing.

Why it matters: KMP, the LPS array, and the closely related Z-array are recurring NAT and MCQ questions in GATE CSE — usually worth 2 marks each and totalling 4 to 6 marks across years. Beyond exams, LPS appears in plagiarism detection, DNA pattern matching, log analysis, and the grep -F family of tools. Understanding LPS gives you a free pass into Z-algorithm, Aho-Corasick, and suffix automaton, which are the basis of many advanced string problems.

Real-world example: Bioinformatics labs at IISc and IIT Delhi use KMP-style matchers to find short motifs (10–30 bp DNA patterns) inside billion-base genomes. A naïve search would take days; KMP brings it down to minutes because the LPS array exploits the heavy repetition that DNA naturally contains — sequences like "ATAT…" or "CGCG…" are exactly the cases where LPS shines.

Common misconception: Students sometimes write that LPS[i] is the longest prefix equal to "any" suffix of the pattern. It must be a suffix of the specific prefix P[0..i], not of the whole pattern. Another frequent error is forgetting the word "proper" — LPS["A"] is 0, not 1, because the only prefix equal to a suffix of "A" is "A" itself, which is not proper.

Question: For pattern "AABAACAABAA", compute the LPS array and use it to count how many times we save work compared to a naïve match.
Solution:
Step 1: Walk through character by character.

• A → 0
• AA → 1 ("A" matches "A")
• AAB → 0 ("B" breaks the border)
• AABA → 1
• AABAA → 2
• AABAAC → 0
• AABAACA → 1
• AABAACAA → 2
• AABAACAAB → 3 ("AAB" prefix = "AAB" suffix)
• AABAACAABA → 4
• AABAACAABAA → 5

Step 2: LPS = [0,1,0,1,2,0,1,2,3,4,5].
Step 3: When matching against a long text, every time KMP falls back from j to LPS[j-1], it skips that many comparisons. For a heavily repetitive pattern like this, the savings are huge.
Conclusion: The LPS array correctly identifies the recurring "AA" and "AAB" borders, letting KMP avoid the O(nm) worst case completely.

:::compare

:::keypoints

• LPS[i] = length of the longest proper prefix of P[0..i] that is also a suffix.
• "Proper" excludes the whole substring itself.
• Built in O(m) using two pointers — i and len.
• On mismatch after matching j characters, jump the pattern index to LPS[j-1].
• Text pointer never moves backward — gives KMP its O(n + m) guarantee.
• LPS["ABABACA"] = [0, 0, 1, 2, 3, 0, 1] — a canonical GATE example.
• LPS is the foundation for Z-algorithm, Aho-Corasick, and palindrome tricks (Manacher).
  :::

:::memory
"Longest Proper Same-side border." L for longest, P for proper, S for suffix matching the prefix. When in doubt, write LPS for "A", "AB", "ABA" — small cases anchor the rule.
:::

:::recap

• LPS records the longest border at every prefix length.
• Build in O(m) with two pointers — amortised analysis is GATE-classic.
• During matching, mismatches send the pattern pointer to LPS[j-1], not to 0.
• KMP achieves linear time because the text pointer is monotone.
  :::

Concatenating two strings of lengths a and b: O(a+b). Comparing two strings: O(min length) worst case. Reversing a string: O(n). Checking palindrome: O(n) two-pointer. Naive substring search: O(n*m). KMP / Z-algorithm: O(n+m). Computing all character frequencies: O(n) with a fixed-size count array (O(1) if alphabet size is constant, e.g., 256 ASCII). Sorting characters of a string: O(n log n) comparison sort, or O(n + k) counting sort for fixed alphabet k. Memory aid: 'linear scans for most one-pass tasks, n log n only when sorting by comparison.' In C, string length via strlen is O(n) because it scans to the null terminator.

A sparse matrix has most entries zero. Storing it fully wastes space, so we use a triplet (3-tuple) representation: each non-zero element is stored as (row, column, value). The table typically has a header row recording (total rows, total columns, number of non-zeros). For a matrix with t non-zero elements, storage is (t+1) rows x 3 columns. Memory aid: 'one row per non-zero, plus one header.' This saves space only when t is small relative to mn; the break-even point is roughly when 3(t+1) < m*n. Other formats include CSR (Compressed Sparse Row) and CSC, which compress further by storing row pointers.

A lower-triangular n x n matrix has only i >= j entries non-zero, totaling n(n+1)/2 elements; storing these in a 1-D array saves ~half the space. Row-major index of A[i][j] (1-based, i>=j) in the packed array = i(i-1)/2 + (j-1). Memory aid: 'rows above contribute 1+2+...+(i-1) = i(i-1)/2 elements.' An upper-triangular matrix is symmetric to this. A symmetric matrix also needs only n(n+1)/2 stored values since A[i][j]=A[j][i]. A tridiagonal (banded) matrix has at most 3n-2 non-zero elements (main diagonal n, plus two adjacent diagonals of n-1 each).

Store a 1-based lower-triangular matrix row by row in a 1-D array. Find the array index (0-based) of A[4][2].

Elements before row 4 = rows 1,2,3 have 1+2+3 = 6 elements = 34/2 using i(i-1)/2 with i=4 -> 43/2 = 6.
Within row 4, A[4][2] is the 2nd element, offset (j-1) = 1.
Index = 6 + 1 = 7 (0-based), i.e., the 8th stored element.

Formula check: i(i-1)/2 + (j-1) = 4*3/2 + (2-1) = 6 + 1 = 7. Memory aid: 'triangular numbers count the rows above, then add the column offset within the current row.'