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) |
// 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 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:
// 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;
}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.
// 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;
}