3.5 Strings

3.1 Functions Basics

A function is a named, reusable block of code that performs one specific task. Instead of repeating the same logic everywhere it's needed, you write it once and "call" it whenever you need it.

A function has:

A return type (the kind of value it hands back, or void if none)
A name
Parameters (its inputs, listed in parentheses)
A body (the code between { })

int add(int a, int b) { // declaration + definition
    return a + b;
}

int result = add(3, 4); // calling it -> 7

3.2 Function Overloading & Default Arguments

C++ allows several functions to share the exact same name as long as their parameter lists differ in number or type — this is called function overloading, and the compiler automatically picks the correct version based on the arguments you actually pass in.

Default arguments give a parameter a fallback value, so callers may omit it entirely if the default is good enough.

// Function Overloading
int add(int a, int b) { return a + b; }
double add(double a, double b) { return a + b; }

// Default Arguments
void greet(string name = "Guest") {
    cout << "Hello " << name;
}

greet();       // "Hello Guest"
greet("Sam");  // "Hello Sam"

3.3 The Call Stack

Every time a function is called, the program pushes a new "stack frame" (activation record) onto the call stack — a region of memory holding that call's local variables, its parameters, and the address to return to once it finishes.

When the function completes, its frame is popped off and execution resumes exactly where it left off. This mechanism is also why deep or infinite recursion eventually causes a "stack overflow": each call adds another frame, and the stack has a fixed, limited size (typically 1–8 MB).

Figure 3.1 — main() calling add() pushes a new frame onto the stack

3.4 Arrays

An array stores a fixed number of elements of the same type in one contiguous block of memory. Because the elements sit back-to-back, the computer can jump straight to any element using its index — arr[i] — in constant O(1) time, with no searching required.

The physical memory address is calculated in a single CPU cycle using the Base Address Formula:

Address(arr[i]) = Base Address + i × sizeof(DataType)

Indexing always starts at 0, so the last valid index of an array of size n is n - 1.

int scores[5] = {90, 85, 77, 92, 60};
cout << scores[0]; // 90
scores[2] = 100;   // update third element (address 1008)

Figure 3.2 — Array elements sit next to each other in memory

Insertion & Deletion: Shifting Mechanics

Because array elements are tightly packed, inserting a new element in the middle requires physically shifting every subsequent element one position to the right to make room — and deleting an element requires shifting everything after it one position to the left. Hence, insertion and deletion in the middle of an array are O(n) operations, even though reading an element is O(1).

// Insert 99 at index 2 in {10, 20, 30, 40}
// shift 30, 40 right -> {10, 20, 99, 30, 40}
for (int i = n; i > 2; i--) {
    arr[i] = arr[i - 1];
}
arr[2] = 99;

Figure 3.3 — Insertion requires shifting subsequent elements

Classic Array Pattern: The Two-Pointer Technique

Whenever an array is sorted, the two-pointer technique uses two indices moving toward or away from each other to solve search and pair problems in O(n) linear time instead of brute-force O(n²):

int left = 0, right = n - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) { /* found pair */ break; }
    else if (sum < target) left++;
    else right--;
}

A string is, at its core, an array of characters — which is why array techniques (traversal, two-pointer, reversal) apply directly to strings too. C++ offers two ways to work with text:

C-style strings: Are simply arrays of char ending in a special null terminator ('\0') that marks where the text stops, inherited directly from C.
std::string: The much friendlier class from the standard library (#include <string>) manages its own memory automatically and provides built-in operations like concatenation (+), length (.length()), and searching (.find()).

#include <string>
using namespace std;

string name = "Claude";
string greeting = "Hi, " + name; // concatenation
cout << name.length();            // 6

Two-Pointer Palindrome Verification

A string is a palindrome if it reads identically forwards and backwards (e.g., "madam"). Using two pointers moving inward allows verification in O(n) time and O(1) space:

bool isPalindrome(string s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}

Figure 3.4 — Checking a palindrome with two pointers

Pattern Matching: Naive vs KMP

Pattern matching checks if a smaller string ("pattern") appears inside a larger string ("text"):

Naive Approach: Checks every starting position, comparing character by character: O(n × m) worst-case time.
KMP (Knuth-Morris-Pratt): Uses an LPS (Longest Prefix which is Suffix) lookup table to skip redundant character comparisons, achieving strictly O(n + m) linear time.

// Naive pattern search
for (int i = 0; i <= n - m; i++) {
    int j = 0;
    while (j < m && text[i + j] == pattern[j]) j++;
    if (j == m) cout << "Found at index " << i << "\n";
}

3.6 Multidimensional Arrays

A multidimensional array is simply an array of arrays — most commonly a 2D array used to represent a grid or table of rows and columns, like a chessboard, a spreadsheet matrix, or an image bitmap.

int grid[2][3] = {
    {1, 2, 3}, // Row 0
    {4, 5, 6}  // Row 1
};

cout << grid[1][2]; // 6 (row 1, column 2)

Module 3: Functions & Arrays