Arrays & Strings: Operations, Patterns & Applications

TAKEAWAYS:

• Arrays store contiguous memory blocks of fixed-size elements, enabling O(1) access but rigid resizing.
• Strings are immutable sequences of Unicode characters, optimized for concatenation and pattern matching.
• Time-space tradeoffs (e.g., O(n²) vs. O(n) sorting) directly impact app performance (e.g., Daraz’s inventory search).
• Pattern matching (KMP, Rabin-Karp) powers eSewa’s fraud detection and Google’s autocomplete.
• Two-dimensional arrays model grids (e.g., Pathao’s route matrices) and sparse matrices (NEPSE stock data).
• String compression (RLE, Huffman) reduces storage in WhatsApp’s media archives.

1. Arrays: Definition and Representation

Arrays are contiguous memory allocations of the same data type, accessed via indices. They support random access (O(1)) but fixed size (unless dynamically resized).

1.1 Static vs. Dynamic Arrays

Visual: Static vs. Dynamic Array Growth

2. Array Operations

2.1 Insertion and Deletion

• Insertion at end: O(1) (static) or amortized O(1) (dynamic).
• Insertion at index i: O(n) (shifts elements).
• Deletion at index i: O(n) (shifts elements).

Worked Example: Insert 7 at index 2 in [1, 3, 5, 7]

Code Trace (Python):

arr = [1, 3, 5, 7]
arr.insert(2, 7)  # Insert 7 at index 2

Step-by-Step State:

2.2 Searching in Arrays

• Linear Search: O(n) (checks each element).
• Binary Search: O(log n) (requires sorted array).

Visual: Binary Search Steps

Code Trace (Binary Search):

def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: left = mid + 1
        else: right = mid - 1
    return -1

Trace for arr = [2, 5, 8, 12, 16], target = 8:

3. Multidimensional Arrays

3.1 Representation

• Row-major order: Elements stored left-to-right, top-to-bottom (e.g., C/Java).
• Column-major order: Elements stored top-to-bottom, left-to-right (e.g., Fortran).

Visual: 2D Array (Row-Major)

Worked Example: Access arr[1][0] in [[1, 2], [3, 4]]

• Address Calculation: base + (1 * cols + 0) * sizeof(int)
• Value: 3

4. Strings: Definition and Operations

Strings are immutable sequences of Unicode characters (e.g., "Nepal").

4.1 String Operations

Visual: String Concatenation (Immutable)

graph TD
    A["str1 = \"Hello\""] --> B["str2 = \"World\""]
    B --> C["str3 = str1 + str2\nstr3 = \"HelloWorld\""]

Code Trace (Python):

s1 = "Hello"
s2 = "World"
s3 = s1 + s2  # Creates new string

Memory Before/After:

Before: s1="Hello", s2="World"
After:  s3="HelloWorld" (new allocation)

5. String Matching Algorithms

5.1 Naive String Matching

• Idea: Slide pattern over text, compare characters.
• Time: O(n*m) (worst case).

Visual: Naive Matching for "abba" in "abababba"

Code Trace:

def naive_match(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i+m] == pattern: return i
    return -1

Trace for text="abababba", pattern="abba":

5.2 Knuth-Morris-Pratt (KMP) Algorithm

• Idea: Preprocess pattern to skip unnecessary comparisons.
• Time: O(n + m).

Visual: KMP Failure Function

Code Trace:

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

Trace for pattern="abba":

6. Applications of Arrays and Strings

6.1 In the Real World

1. eSewa’s Transaction Logs

   • Idea: Arrays store transaction records (e.g., transactions[1000] = {"user": "A", "amount": 500}).
   • Why: Fast random access to verify fraud (O(1) lookup).

2. Daraz’s Order Queue

   • Idea: Queues (arrays) manage order processing (FIFO).
   • Why: Ensures first-order-first-served delivery.

3. Pathao’s Route Matrix

   • Idea: 2D arrays represent distances between stops (e.g., matrix[i][j] = time from stop i to j).
   • Why: Dijkstra’s algorithm (Unit 9) finds shortest routes.

Worked Example: Daraz Order Queue

7. Time-Space Tradeoffs

Visual: Tradeoff Graph

Exam Tip

• Focus Areas:
  • Arrays: Insertion/deletion traces, 2D array indexing.
  • Strings: Naive vs. KMP matching, substring operations.
  • Applications: Link array/string concepts to real apps (eSewa, Daraz).
• Common Mistakes:
  • Off-by-one errors in array indices (e.g., arr[n-1] vs. arr[n]).
  • Forgetting immutability of strings in concatenation.
• Practice:
  • Solve 2-3 problems on array manipulation (e.g., rotate matrix).
  • Implement KMP algorithm from scratch and trace it.

Final Note: Arrays and strings are the building blocks of algorithms. Master their operations, tradeoffs, and real-world uses to ace TU/PU exams and design efficient apps!