Arrays & Strings

beginner5 problems· Prerequisites: Big O & Complexity

Array Basics

Arrays store elements in contiguous memory with O(1) index-based access. Arrays are fixed-size. Use a dynamic array for dynamic sizing.

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

Two pointers iterate from different positions toward each other (or in the same direction at different speeds). Useful for sorted arrays, palindromes, and in-place reversal.

Common patterns:

Opposite ends - one at start, one at end, move toward each other
Same direction - slow and fast pointer (also used in linked lists)
Sliding window - maintain a window that expands/contracts

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

A window (subarray) slides across the array. Used for subarray problems like max sum subarray of size k or longest substring without repeating characters.

Fixed window: Window size is constant. Variable window: Window expands and contracts based on a condition.

Complexity: O(n) - each element enters and leaves the window at most once.

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 to Use Arrays

Arrays are the right choice when:

You need O(1) access by index (random access)
You process elements in sequential order (iterating once)
The size is known ahead of time (or bounded)
You need contiguous memory for cache-friendly access

Arrays are NOT the right choice when:

You frequently insert or delete at the beginning (use linked list)
The size changes unpredictably and you can't pre-allocate (use dynamic array, still fine)
You need fast membership lookup (use a hash set)

Decision guide:

Signal	Best choice
"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 (from arrays)

Common Mistakes / Gotchas

Off-by-one: forgetting arrays are 0-indexed for (int i = 0; i <= arr.Length; i++) accesses arr[arr.Length] which is out of bounds.

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

String immutability in loops s = s + c in a loop creates a new string each time - O(n²). Use StringBuilder / join / list append instead.

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

"Two-pointer only works on sorted arrays" Two-pointer can also work on unsorted arrays for problems like "move zeros" or "remove duplicates in-place" using slow/fast pointers.

Common Interview Patterns

Two Sum variant - use a hash map for O(n) lookup
In-place array manipulation - maintain a "write index"
Prefix sum - precompute cumulative sums for O(1) range sum queries
String builder - anytime you need to build/modify a string in a loop
Character counting - use int[26] for lowercase letters, Dictionary<char,int> for general

Off-by-one: forgetting arrays are 0-indexed for (int i = 0; i <= arr.Length; i++) accesses arr[arr.Length] which is out of bounds.

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

String immutability in loops s = s + c in a loop creates a new string each time - O(n²). Use StringBuilder / join / list append instead.

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

"Two-pointer only works on sorted arrays" Two-pointer can also work on unsorted arrays for problems like "move zeros" or "remove duplicates in-place" using slow/fast pointers.