Arrays & Strings

Arrays store elements contiguously. Strings are character sequences, often treated as specialized arrays. Core ops: declaration, traversal, search, insertion, deletion.

The two-pointer technique efficiently traverses arrays/strings, often from ends or differing speeds, for problems like sum-finding or in-place reversal. Prefix sums optimize range sum queries to O(1) by pre-calculating cumulative totals. Multi-dimensional arrays (matrices) extend this to grids. String manipulation includes detecting palindromes and anagrams, often via character counting or sorting.

Two-Pointer Array Reversal Technique

  pub fn reverse_array(arr: &mut [T]) {
    let mut left = 0;
    let mut right = arr.len() - 1;

    while left < right {
      arr.swap(left, right);
      left += 1;
      right -= 1;
    }
  }
  

Hashing & Hash Maps

Hashing converts arbitrary input into fixed-size hash values via a hash function. Hash Maps (Dictionaries/Hash Tables) map keys to values using hashing for efficient storage and retrieval. Key operations: insertion, deletion, and lookup, typically O(1) average-case time. Worst-case can be O(N) due to collisions. Applications include:

• frequency counting of elements, chars, etc.
• efficient duplicate checking
• two-sum problem variants

Linked Lists

Linked Lists elements/nodes are non-contiguous in memory. Each node holds data, and pointer to next node. This allows efficient insertions and deletions without shifting. Declined in several versions:

• Singly Linked Lists (next pointer)
• Doubly Linked Lists (prev and next pointers)
• Circular Linked Lists (last points to first)

Linked List Node

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) { exit(1); } // mem. alloc fail 
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}