Unit 1: Basic Data Structures

A data structure organizes data in memory so operations run efficiently. This unit builds from the array — a contiguous, index-addressable block — up through matrices, strings, and the stack/queue family, then applies them to competitive patterns.

• Contiguity: elements sit in adjacent memory cells, so address of A[i] = base + i × size, giving O(1) random access.
• Fixed vs dynamic: static arrays fix size at declaration; linked structures grow at runtime via pointers.
• Cost model: access O(1), search O(n), insert/delete O(n) due to shifting.
• LIFO vs FIFO: stacks remove the last inserted item; queues remove the first.

II. Arrays — Storage and In-Place Manipulation

A. Declaring and processing 1D and 2D arrays

• 1D: int a[5]; reserves 5 slots; iterate with for(i=0;i<n;i++).
• 2D: int m[3][4]; stored row-major, so m[i][j] at base+(i×cols+j)×size.

B. Insertion in an array

• Shift right: to insert x at index p, move elements p..n-1 one step right, then set a[p]=x; O(n).

C. Deletion from array

• Shift left: overwrite a[p] by copying a[p+1..n-1] leftward and decrement n; O(n).

D. Array rotations

• Left rotate by d: reversal method — reverse [0,d-1], reverse [d,n-1], reverse whole array; O(n), O(1) space.

rotate(a, d): reverse(0,d-1); reverse(d,n-1); reverse(0,n-1)

E. Array arrangement, rearrangement

• Purpose: reorder elements to meet an ordering rule (sorted, grouped, alternated) using swaps in place, avoiding extra arrays where possible.

III. Matrices — 2D Array Operations

A. Matrix multiplication

• Rule: for A(m×n) and B(n×p), C[i][j] = Σ_k A[i][k]×B[k][j]; triple loop, O(m·n·p).

B. Lower triangular and upper triangular matrix of array

• Lower: entries with j>i are zero (data on/below diagonal).
• Upper: entries with i>j are zero (data on/above diagonal).

C. Different operations on Matrices

• Transpose: swap m[i][j] with m[j][i].
• Addition: C[i][j]=A[i][j]+B[i][j] for equal dimensions.

D. Print a matrix in spiral form

• Boundary walk: maintain top,bottom,left,right; print top row →, right col ↓, bottom row ←, left col ↑, then shrink bounds; O(rows×cols).

E. Find distinct elements common to all rows in a matrix

• Hashing: count each value in row 1, then for each later row mark values seen; elements present in all rows are common. O(rows×cols).

IV. Strings and String-Adjacent Problems

A. String declaration and manipulation

• Declaration: char s[] = "abc"; (null-terminated in C) or string s; operations include length, concat, substring, compare.

B. K maximum sum from two arrays

• Pair sums: from arrays A,B pick pairs A[i]+B[j]; sort descending and use a max-heap seeded with the largest pair, popping K times and pushing neighbours to get the top-K sums.

C. Missing characters to make a string Pangram

• 26-mask: mark each letter present; report the letters of a–z never marked. A pangram needs all 26.

D. Rearrange characters so that no two adjacent characters are same

• Greedy heap: always place the most frequent remaining character that differs from the previous one; feasible only if no char count exceeds ⌈n/2⌉.

E. Remove minimum number of characters so that two strings become anagram

• Frequency diff: removals = Σ_c |count1[c] − count2[c]| over all letters.

V. Stacks, Queues and Their Variants

A. Creation of stack using arrays

• Top index: push → a[++top], pop → a[top--]; overflow when top==size-1. All O(1).

B. Creation of arrays using linked list

• Node chain: each node holds data and next; index access walks the list, O(n), trading random access for dynamic growth.

C. Creation of queue using array

• Two pointers: front and rear; enqueue at rear++, dequeue at front++; risks false-full unless made circular.

D. Creation of queue using linked list

• Head/tail nodes: enqueue by linking a new tail node, dequeue by advancing head; both O(1).

E. Implement two Stacks in an array

• Ends inward: stack1 grows from index 0 up, stack2 from n-1 down; overflow when the two tops meet, maximizing shared space.

F. Implement Stack using Queues

• Push-costly: enqueue new element, then rotate all earlier elements behind it so the queue front is always the newest — making pop O(1) and push O(n).

G. Design a stack with operations on middle element

• Doubly linked list + mid pointer: track a mid node; push/pop update mid by one step, giving O(1) findMiddle and deleteMiddle.

H. Implementation of Deque using circular array

• Both ends wrap: insert/delete at front and rear using modular indices (i+1)%n and (i-1+n)%n; all O(1).

I. Circular Queue

• Wrap-around: rear=(rear+1)%n on enqueue reuses freed front slots; full when (rear+1)%n==front.

J. Reversing a Queue

• Via stack: dequeue all into a stack, then pop back into the queue to invert order; O(n).

VI. Array and Bit Techniques for Competitive Problems

A. Two pointer technique — pair with sum X in unsorted array

• Hash set: scan once; for each a[i] check if X−a[i] was already seen. O(n). (Sorting first also enables a left/right two-pointer sweep.)

B. Count subarrays having an equal sum of elements at even and odd positions

• Signed prefix: treat odd-index values as negative, even as positive; a subarray qualifies when its signed prefix sums are equal at both ends, counted with a hash map.

C. Finding a peak element in array

• Binary search: an element ≥ both neighbours; compare a[mid] with a[mid+1] and move toward the higher side. O(log n).

D. Find subarray of length K with maximum Peak

• Sliding window: slide a window of size K, tracking the window maximum (deque) to report the largest peak among all windows.

E. Replace every element of the array with the previous element

• Back-to-front: set a[i]=a[i-1] moving from i=n-1 down to 1; first element becomes a sentinel (e.g. −1).

F. Rearrange positive and negative numbers

• Partition + interleave: group negatives and positives (partition step), then alternate them so signs come +,−,+,−… in place.

G. Rearrange array such that even index elements are smaller and odd index elements are greater

• Local swap: scan pairs — if an even index holds a value larger than its odd neighbour (or vice versa), swap them; one pass fixes the wave pattern.

H. Find the first non-repeating element in a given array of integers

• Count then scan: build a frequency map, then return the first element whose count is 1. O(n).

I. Find the majority element

• Boyer–Moore voting: hold a candidate and count; increment when it matches, decrement otherwise, resetting on zero. The survivor is the majority (appears > n/2). O(n), O(1) space.

J. Count strings with consecutive ones

• DP: number of binary strings of length n containing consecutive 1s = 2ⁿ − Fib(n+2), since Fibonacci counts strings without adjacent ones.

K. Check if all bits can be made same by single flip

• Uniform test: one flip makes all bits equal only if exactly one bit differs from the rest — i.e. counts of 0s and 1s are n−1 and 1 in some order.

L. Last Moment Before All Ants Fall Out of a Plank

• Pass-through trick: colliding ants reversing direction is equivalent to passing through each other; answer = max(max(left positions), plank − min(right positions)).

M. Move All Zeros to End of Array

• Write pointer: keep index j for the next non-zero slot; copy each non-zero to a[j++], then fill the remainder with zeros. O(n), stable order.