Unit 1: Basic Data Structures

1. Architectural Foundations of Arrays and Memory Layouts

Contiguous Memory Allocation and Addressing

An array is a linear collection of elements of homogeneous data type placed in contiguous memory locations. Because memory addresses are contiguous, random access to any element by its index executes in strictly $O(1)$ time.
For a one-dimensional array starting at base memory address $\text{Base}(A)$ where each element occupies $S$ bytes, the physical memory address of the element at 0-indexed position $i$ is calculated as:
$\text{Address}(A[i]) = \text{Base}(A) + i \times S$

If the array is 1-indexed (with lower bound $L = 1$):
$\text{Address}(A[i]) = \text{Base}(A) + (i - L) \times S$

Multidimensional Arrays: Row-Major and Column-Major Mapping

Higher-dimensional arrays must be flattened into linear physical RAM addresses:

• Row-Major Order (Standard in C/C++, Python, Java): Consecutive elements of a row reside in consecutive memory addresses. For a 2D array $M[R][C]$ with row dimension $R$ and column dimension $C$:
  $\text{Address}(M[i][j]) = \text{Base}(M) + (i \times C + j) \times S$
• Column-Major Order (Standard in Fortran, MATLAB, R): Consecutive elements of a column reside in consecutive memory addresses:
  $\text{Address}(M[i][j]) = \text{Base}(M) + (j \times R + i) \times S$

Cache locality (spatial locality) heavily impacts execution runtime in competitive programming. Iterating through a row-major 2D array row-by-row (for i: for j: sum += M[i][j]) leverages CPU cache lines (typically 64 bytes), whereas column-by-column iteration induces frequent cache misses, slowing runtime by factors of $5\times$ to $10\times$ on large grids ($1000 \times 1000$).

Static vs. Dynamic Arrays and Amortized Analysis

• Static Arrays: Allocated on the call stack (or static/global memory segment) with fixed size determined at compile time (e.g., int arr[100005];). Global allocation avoids stack overflow when handling competitive problem constraints up to $10^7$ elements.
• Dynamic Arrays (e.g., std::vector in C++, ArrayList in Java): Reside in heap memory. When capacity is exhausted upon an insertion, the dynamic array allocates a new block of double capacity ($2\times$ geometric progression), copies existing $n$ elements, and deallocates the old buffer.
• Amortized Analysis: While a single reallocation takes $O(n)$ time, inserting $N$ items requires $N + N/2 + N/4 + \dots \approx 2N$ total copies. The amortized time per insertion remains $O(1)$. If the capacity increased by a constant additive term $+K$ instead of geometrically, insertion would degrade to $O(n)$ amortized.

2. Array Manipulation and In-Place Algorithmic Patterns

In-Place Array Reversal and Cyclic Rotation

Shifting or rotating an array of size $n$ by $k$ positions can be executed without auxiliary memory ($O(1)$ extra space):

1. The Reversal Algorithm:
   To left-rotate $A[0 \dots n-1]$ by $k$ steps ($k = k \pmod n$):
   • Reverse the prefix sub-array: $\text{reverse}(A, 0, k - 1)$
   • Reverse the suffix sub-array: $\text{reverse}(A, k, n - 1)$
   • Reverse the entire array: $\text{reverse}(A, 0, n - 1)$
     Total time complexity: $O(n)$, space complexity: $O(1)$.
2. The Juggling Algorithm (Cyclic Permutation via GCD):
   The array is partitioned into $\gcd(n, k)$ independent disjoint cycles. In each cycle, elements are shifted along modular indices $i \to (i + k) \pmod n$ until the cycle closes. Each element is read and moved exactly once, executing in $O(n)$ time and $O(1)$ auxiliary space.

Block-Swap Algorithm

Divides the array into two sub-blocks $A = arr[0 \dots k-1]$ and $B = arr[k \dots n-1]$. It recursively swaps blocks of equal size until the remaining segments align. Time complexity: $O(n)$, Auxiliary space: $O(1)$.

Prefix Sums and Difference Arrays

• Prefix Sum Array: Constructed as $P[i] = P[i-1] + A[i]$ with $P[0] = A[0]$. Enables constant-time $O(1)$ range sum queries over $[L, R]$ via:
  $\sum_{k=L}^{R} A[k] = P[R] - P[L-1] \quad (\text{with } P[-1] = 0)$
• Difference Array: Defined as $D[0] = A[0]$ and $D[i] = A[i] - A[i-1]$. To increment all elements in range $[L, R]$ by a value $V$ in $O(1)$ time:
  $D[L] \leftarrow D[L] + V, \quad D[R+1] \leftarrow D[R+1] - V$
  The modified array is reconstructed by taking prefix sums of $D$ in $O(n)$ time after processing $Q$ batch updates.

3. Multidimensional Arrays and Matrix Mechanics

In-Place Matrix Rotation

Rotating an $N \times N$ square matrix clockwise by $90^\circ$ in-place ($O(1)$ auxiliary space):

1. Compute the Transpose of the matrix: swap $M[i][j]$ with $M[j][i]$ for all $i < j$.
2. Reverse each row horizontally: swap $M[i][j]$ with $M[i][N - 1 - j]$ for $0 \le j < N/2$.
   To rotate counter-clockwise by $90^\circ$, either transpose then reverse each column, or reverse each row then transpose.

Spiral Traversal of a 2D Matrix

Traversing an $R \times C$ matrix in spiral order requires maintaining four boundary boundaries: top, bottom, left, and right:

1. Traverse from left to right along top row; increment top.
2. Traverse from top to bottom along right column; decrement right.
3. If top <= bottom, traverse from right to left along bottom row; decrement bottom.
4. If left <= right, traverse from bottom to top along left column; increment left.
   This executes in $O(R \times C)$ time touching each element exactly once.

4. Strings in Competitive Programming

Memory Representation and Encodings

Strings in C/C++ are represented either as null-terminated character arrays (char str[], where \0 designates end-of-string) or dynamically sized objects (std::string).
In Java and Python, string objects are immutable; repeated concatenation using + inside a loop takes $O(n^2)$ time due to reallocation and copying. StringBuilder (in Java) or list joins (in Python) should be utilized to achieve $O(n)$ linear aggregation.

Frequency Arrays and Hashing Primitives

For lowercase English alphabet strings ($|\Sigma| = 26$), a frequency vector int freq[26] = {0} tracks character occurrences in $O(n)$ time and $O(1)$ space. This primitive underpins anagram detection, permutation matching, and palindromic rearrangements (a permutation of a string can form a palindrome if and only if at most one character has an odd frequency count).

5. Stack Data Structure: Principles and Applications

LIFO Principle and Implementation Mechanics

A stack enforces Last-In, First-Out (LIFO) semantics. Key primitives include:

• push(x): Inserts element $x$ onto the top of the stack ($O(1)$).
• pop(): Removes the topmost element ($O(1)$).
• top() / peek(): Inspects the topmost element without removal ($O(1)$).
• empty() / isEmpty(): Checks if the stack contains zero elements ($O(1)$).

When implemented using fixed arrays, inserting beyond the stack capacity triggers a Stack Overflow. Attempting to pop from an empty stack causes a Stack Underflow.

Monotonic Stacks

A monotonic stack maintains its elements in strictly increasing or strictly decreasing order.

• Next Greater Element (NGE): To find the first element to the right greater than $A[i]$ for all $i \in [0, n-1]$:
  Iterate from right to left; while the stack is non-empty and top() <= A[i], pop. If stack is empty, $\text{NGE}[i] = -1$; otherwise $\text{NGE}[i] = \text{top}()$. Push $A[i]$.
• Each element is pushed and popped at most once, achieving $O(n)$ total time across the array compared to $O(n^2)$ brute-force searches.
• Similar patterns solve the Largest Rectangle in Histogram and Stock Span Problem in optimal $O(n)$ time.

Expression Parsing and Evaluation

1. Infix to Postfix (Reverse Polish Notation) via Shunting Yard Algorithm:
   • Operands are directly appended to the output token list.
   • Operators are pushed to an operator stack after popping operators of greater or equal precedence (or strictly greater for right-associative operators like exponentiation ^).
   • Left parenthesis ( is pushed onto the operator stack; right parenthesis ) causes popping until ( is encountered.
2. Postfix Evaluation:
   • Scan tokens left to right.
   • Operands are pushed onto an evaluation stack.
   • Upon encountering an operator $\odot$, pop the right operand $b = \text{pop}()$, pop the left operand $a = \text{pop}()$, compute $res = a \odot b$, and push $res$ back onto the stack.

6. Queues and Deque Structures

FIFO Principle and Ring Buffer (Circular Queue) Implementation

A queue follows First-In, First-Out (FIFO) semantics with enqueue at the rear and dequeue at the front.
In a linear array, successive dequeues waste memory at the front. A Circular Queue wraps pointers modulo capacity $N$:

• Initial state: front = -1, rear = -1.
• enqueue(x): rear = (rear + 1) % N, arr[rear] = x.
• dequeue(): front = (front + 1) % N.
• Full condition: (rear + 1) % N == front.
• Empty condition: front == -1.

Double-Ended Queue (Deque) and Sliding Window Extrema

A Deque allows $O(1)$ insertion and deletion at both ends (push_front, push_back, pop_front, pop_back).

• Sliding Window Maximum (in an array of size $n$ with window size $k$):
  Maintain a monotonic deque of indices storing values in monotonically decreasing order.
  For each index $i$:
  1. Remove indices from the front if they fall outside the current window ($index \le i - k$).
  2. Pop indices from the back while $A[\text{back}] \le A[i]$.
  3. Push current index $i$ to the back.
  4. The front index $A[\text{deque.front()}]$ represents the maximum element in the window $[i - k + 1, i]$.
     Overall complexity: $O(n)$ time and $O(k)$ space.