- Understand insert/delete are O(n) due to shifting, unless at the end
- See why string concatenation in loops is O(k²)—use join instead
- Learn two-pointer and sliding window patterns for efficient solutions
Operations on Arrays and Strings
You have an array of scores: [85, 92, 78, 96, 88]. What can you do with it?
Accessing Elements
scores = [85, 92, 78, 96, 88]
scores[0] # 85 (first)
scores[2] # 78 (third)
scores[4] # 88 (last)
O(1). Direct memory access. base_address + index × element_size.
Modifying Elements
scores[1] = 95 # Change second score from 92 to 95
Also O(1). Same address calculation, write instead of read.
Traversing (Looping)
for score in scores:
print(score)
# Or with indices
for i in range(len(scores)):
print(f"Score {i}: {scores[i]}")
O(n). Visit each element once.
Searching
Linear search (unsorted): Check each element until you find it (or reach the end).
def find(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Found at index i
return -1 # Not found
O(n). Worst case: target is last element or absent.
Binary search (sorted): Split the array in half repeatedly.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # Search right half
else:
right = mid - 1 # Search left half
return -1
O(log n). Each step halves the search space. For 1 million elements, ~20 steps.
Inserting Elements
At the end (if space available):
arr = [1, 2, 3, None, None] # Capacity 5, size 3
arr[3] = 4 # Add 4
# Now [1, 2, 3, 4, None]
O(1). Just write to the next position.
In the middle (shifting required):
arr = [1, 2, 4, 5]
# Insert 3 at index 2
# Shift 4 and 5 to the right
arr = [1, 2, None, 4, 5]
arr[2] = 3
# Result: [1, 2, 3, 4, 5]
O(n). Must shift all elements from insertion point onward.
For an array of size n, inserting at index 0 shifts n elements. Inserting at the end shifts 0. Average: n/2 shifts = O(n).
Deleting Elements
From the end:
arr = [1, 2, 3, 4, 5]
arr.pop() # Remove last element
# Now [1, 2, 3, 4]
O(1). Just decrement the size (or overwrite with None/null).
From the middle (shifting required):
arr = [1, 2, 3, 4, 5]
# Delete index 2 (value 3)
# Shift 4 and 5 to the left
arr[2] = arr[3] # 4 moves to index 2
arr[3] = arr[4] # 5 moves to index 3
# Now [1, 2, 4, 5, ...]
O(n). Must shift elements to fill the gap.
Finding Min/Max
def find_max(arr):
if not arr:
return None
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
O(n). Check every element.
Reversing
def reverse(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
O(n). Swap first with last, second with second-to-last, etc. n/2 swaps.
String Operations
Strings are arrays of characters with extra operations.
Accessing characters:
s = "hello"
s[0] # 'h'
s[4] # 'o'
O(1).
Concatenation:
s1 = "hello"
s2 = "world"
s3 = s1 + " " + s2 # "hello world"
O(n+m) where n and m are lengths. Must create a new string and copy both.
In a loop, this is expensive:
result = ""
for word in words:
result += word # O(current length of result)
For k words of average length n, this is O(k² × n). Each concat copies the entire result so far.
Better: use a list and join:
parts = []
for word in words:
parts.append(word) # O(1) amortized
result = "".join(parts) # O(total length)
O(k × n) total.
Substring:
s = "hello"
s[1:4] # "ell" (indices 1, 2, 3)
O(length of substring). Must create a new string and copy characters.
Searching:
s = "hello world"
s.find("world") # 6 (index where "world" starts)
s.find("xyz") # -1 (not found)
O(n × m) naive (check every position in s for the pattern). Better algorithms (KMP, Rabin-Karp) are O(n+m).
Replacing:
s = "hello world"
s.replace("world", "Python") # "hello Python"
O(n). Scan the string, copy to new string with replacements.
Splitting:
s = "apple,banana,cherry"
fruits = s.split(",") # ["apple", "banana", "cherry"]
O(n). Scan for delimiters, create substrings.
Joining:
fruits = ["apple", "banana", "cherry"]
s = ",".join(fruits) # "apple,banana,cherry"
O(total length of all strings + separators).
Two-Pointer Technique
Common pattern for array/string problems: two pointers moving through the data.
Checking if a string is a palindrome:
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
O(n). Compare characters from both ends moving inward.
Removing duplicates from sorted array:
def remove_duplicates(arr):
if len(arr) <= 1:
return len(arr)
write = 1 # Position to write next unique element
for read in range(1, len(arr)):
if arr[read] != arr[read - 1]:
arr[write] = arr[read]
write += 1
return write # New length
O(n). One pass with two pointers.
Sliding Window
Another common pattern: maintain a window of elements and slide it.
Maximum sum of k consecutive elements:
def max_sum_k(arr, k):
if len(arr) < k:
return None
# Initial window sum
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide the window
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # Add new, remove old
max_sum = max(max_sum, window_sum)
return max_sum
O(n). Each element is added once and removed once.
Common Mistakes
Off-by-one errors:
arr = [1, 2, 3, 4, 5]
# arr[5] → Error! Valid indices are 0-4
Modifying array while iterating:
arr = [1, 2, 3, 4, 5]
for i in range(len(arr)):
if arr[i] % 2 == 0:
arr.pop(i) # Messes up indices!
Solution: iterate backward or create a new array.
String immutability (in Python/Java):
s = "hello"
# s[0] = 'H' # Error! Strings are immutable
Must create a new string:
s = 'H' + s[1:] # "Hello"
The Pattern
Most array/string operations fall into categories:
- Access/modify: O(1)
- Search (unsorted): O(n)
- Search (sorted): O(log n) with binary search
- Insert/delete: O(n) due to shifting (unless at the end)
- Traverse: O(n)
Strings add:
- Concat: O(n+m)
- Substring: O(length)
- Search: O(n×m) naive, O(n+m) with KMP
Understanding these complexities tells you when arrays/strings are the right choice—and when to reach for other structures.