Arrays & Strings: The Foundation of DSA
Master the most fundamental data structure — arrays and strings. Learn traversal patterns, two-pointer technique, sliding window, and common interview patterns.
Why Arrays Are Everything
Arrays are the backbone of almost every algorithm. They store elements in contiguous memory, giving O(1) random access — a property no other data structure matches. Strings are essentially character arrays with specialized operations. Mastering array manipulation patterns is the single highest-ROI skill in DSA.
Over 40% of coding interview problems involve arrays or strings as the primary data structure. The patterns you learn here apply everywhere.
Core Operations & Complexity
Access by index is O(1). Search is O(n) for unsorted, O(log n) for sorted. Insertion/deletion at the end is O(1) amortized (dynamic arrays), but O(n) at arbitrary positions due to shifting. Understanding these trade-offs guides every algorithm design decision.
Pattern 1: Two Pointers
The two-pointer technique uses two indices moving through the array — either from both ends toward the center, or both from the start at different speeds. It reduces O(n²) brute force to O(n) for many problems like pair sums, palindrome checks, and removing duplicates.
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
"""Find two numbers in a SORTED array that sum to target."""
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return [] # No pair found
def is_palindrome(s: str) -> bool:
"""Check if a string is a palindrome, ignoring non-alphanumeric."""
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return TrueTwo pointers only works directly on sorted arrays for sum problems. For unsorted arrays, sort first (O(n log n)) or use a hash map (O(n) space).
Pattern 2: Sliding Window
The sliding window maintains a window [left, right] over the array, expanding and contracting to find optimal subarrays. It solves problems like maximum sum subarray, longest substring without repeats, and minimum window substring — all in O(n).
def max_sum_subarray(nums: list[int], k: int) -> int:
"""Find maximum sum of any subarray of size k."""
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
def longest_unique_substring(s: str) -> int:
"""Length of longest substring without repeating characters."""
seen = {}
left = 0
max_len = 0
for right, char in enumerate(s):
if char in seen and seen[char] >= left:
left = seen[char] + 1
seen[char] = right
max_len = max(max_len, right - left + 1)
return max_lenPattern 3: Prefix Sums
Prefix sums precompute cumulative sums so any subarray sum can be calculated in O(1). Build the prefix array once in O(n), then answer range sum queries instantly. This technique is essential for subarray sum problems.
def subarray_sum_equals_k(nums: list[int], k: int) -> int:
"""Count subarrays that sum to exactly k."""
prefix_count = {0: 1} # prefix_sum -> count of occurrences
current_sum = 0
count = 0
for num in nums:
current_sum += num
# If (current_sum - k) exists as a prefix, we found a subarray
count += prefix_count.get(current_sum - k, 0)
prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1
return countKey array patterns to master: Two Pointers, Sliding Window, Prefix Sums, Kadane's Algorithm (max subarray), and Dutch National Flag (3-way partition). These cover 80% of array interview problems.