Arrays & Strings

beginner5 problems

Prerequisites:Big O & Complexity

Why Arrays?

In the last module, you learned to analyze code speed with Big O. Now you get to apply it.

Arrays are the simplest and most fundamental data structure. Almost everything else in computer science builds on them. A string is just an array of characters. A matrix is an array of arrays. Hash maps, heaps, and graphs all use arrays under the hood.

Think of an array as a row of lockers. Each locker has a number (its index), and you can walk straight to locker #42 without checking lockers #1 through #41. That instant access by position is what makes arrays special.

But arrays aren't perfect for everything. You'll see why in this module - and that's what will motivate the data structures in the modules ahead.

Array Basics

Arrays store elements in contiguous memory - meaning the elements are placed right next to each other in memory. This is why index-based access is O(1): the computer can calculate the exact memory address of arr[42] instantly.

Two flavors:

Fixed-size array - the size is set at creation and can't change
Dynamic array (called List in C#, ArrayList in Java, vector in C++, list in Python/JS) - automatically grows when you add elements

Here's how they compare:

Operation	Array	Dynamic Array
Access by index	O(1)	O(1)
Search (unsorted)	O(n)	O(n)
Insert at end	N/A (fixed)	O(1) amortized
Insert at middle	O(n) (shift)	O(n)
Remove at end	N/A	O(1)
Remove at middle	O(n)	O(n)

Array vs List declarationsC#

// Fixed-size array
int[] arr = new int[5] { 1, 2, 3, 4, 5 };

// Dynamic list
List<int> list = new List<int> { 1, 2, 3 };
list.Add(4);                    // O(1) amortized
list.Insert(0, 0);              // O(n) - shifts elements
list.RemoveAt(1);               // O(n) - shifts elements

// Array utilities
Array.Sort(arr);                // O(n log n)
Array.Reverse(arr);             // O(n)
int index = Array.IndexOf(arr, 3); // O(n)

Two-Pointer Technique

Here's your first array pattern. The two-pointer technique uses two indices to traverse the array - often from opposite ends moving toward each other, or at different speeds in the same direction.

This is useful for:

Opposite ends - palindrome checking, reversing an array in-place
Same direction (slow/fast) - finding cycles, removing duplicates (we'll revisit this with Linked Lists)
Sliding window - the next section

The beauty? These are all O(n) time with O(1) extra space.

Two pointers from opposite endsC#

// Reverse an array in-place - O(n), O(1) space
void Reverse(int[] arr) {
    int left = 0, right = arr.Length - 1;
    while (left < right) {
        (arr[left], arr[right]) = (arr[right], arr[left]);
        left++;
        right--;
    }
}

// Check if a string is a palindrome - O(n), 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;
}

Sliding Window

The sliding window is a two-pointer variant where you maintain a window (a subarray) that slides across the array. Each element enters the window once and leaves it once - O(n) total.

Fixed window: the window stays the same size (e.g., "maximum sum of any 3 consecutive elements")
Variable window: the window grows and shrinks based on a condition (e.g., "shortest subarray that sums to at least k")

This pattern shows up constantly in interview problems. Once you see it, you won't unsee it.

Fixed-size sliding windowC#

// Max sum of any subarray of size k - O(n)
int MaxSumSubarray(int[] arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++)
        windowSum += arr[i];

    int maxSum = windowSum;
    for (int i = k; i < arr.Length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.Max(maxSum, windowSum);
    }
    return maxSum;
}

When Arrays Shine (and When They Don't)

Arrays are the right choice when:

You need O(1) access by index - jump to any position instantly
You process elements in sequential order (a single pass)
The size is known ahead of time (or bounded and predictable)
You want cache-friendly access - contiguous memory means faster reads

Arrays are NOT the right choice when:

You frequently insert or delete at the beginning - every element has to shift (O(n) each time). A linked list handles this better.
You need fast membership lookup - scanning an unsorted array is O(n). A hash set handles this in O(1).
The size is completely unknown - though dynamic arrays handle this pretty well.

Quick guide:

What you need	Best tool
"Find element by position"	Array (O(1) index)
"Frequent insert/remove at front"	Linked List
"Check if something exists"	Hash Set
"Process in order, one pass"	Array
"Pair elements by key"	Hash Map

Common Mistakes

Off-by-one: forgetting arrays are 0-indexed for (int i = 0; i <= arr.Length; i++) - this tries to access arr[arr.Length] on the last iteration, which is out of bounds. Always use i < length, not i <= length.

Mutating an array while iterating Removing elements during a forward loop messes up indices. Either iterate backward or build a new list.

String immutability in loops In most languages, s = s + c in a loop creates a new string every iteration - O(n²) total. Use StringBuilder / ''.join() / array append instead.

Confusing "length" with "last index" If an array has length n, the last valid index is n-1, not n.

"Two-pointer only works on sorted arrays" Not true! Two-pointer also works on unsorted arrays for problems like "move zeros to the end" or "remove duplicates in-place" using slow/fast pointers.

Key Patterns to Remember

Two Sum - use a hash map for O(n) lookup (see the next module)
In-place manipulation - maintain a "write index" for O(1) space
Prefix sum - precompute cumulative sums for O(1) range queries
String builder - any time you're building a string in a loop, use the right tool
Character counting - use int[26] for lowercase letters, or a dictionary for general unicode

What's Next?

You now know the most basic data structure - and you've already seen its limits. Scanning an array for a specific value takes O(n) time. What if you need to answer "does this exist?" a million times?

That's where HashMaps & Sets come in. They trade away ordering (you can't ask "what's at position 42?") for O(1) lookups. If arrays are a row of lockers, hash maps are a coat check - you hand over your ticket and get your coat instantly, but you can't ask "what's in the 42nd coat slot?"

Next up: HashMaps & Sets

Mutating an array while iterating Removing elements during a forward loop messes up indices. Either iterate backward or build a new list.

String immutability in loops In most languages, s = s + c in a loop creates a new string every iteration - O(n²) total. Use StringBuilder / ''.join() / array append instead.

Confusing "length" with "last index" If an array has length n, the last valid index is n-1, not n.

"Two-pointer only works on sorted arrays" Not true! Two-pointer also works on unsorted arrays for problems like "move zeros to the end" or "remove duplicates in-place" using slow/fast pointers.