Array internals
An array is a contiguous block of memory where each element lives right next to the previous one. Because the starting address and element size are known, jumping to any index is a single arithmetic operation: address = start + index * size. That's O(1) access — instant.
Python list is a dynamic array. Under the hood it stores an array of pointers. When you append past the current capacity, Python allocates a bigger chunk (roughly 1.125x the old size) and copies everything over. That's why .append() is O(1) amortized — the occasional resize is spread across many appends.
Operations Big O
| Operation | Time Complexity | Why |
|---|---|---|
| Access by index | O(1) | Direct address calculation |
| Search (unsorted) | O(n) | Must check each element |
| Insert at end | O(1) amortized | Append; occasional resize |
| Insert at middle | O(n) | Shift all elements after |
| Delete | O(n) | Shift elements to fill gap |
Common array patterns
Four patterns cover the vast majority of array problems you'll see in interviews. Master these, and you'll recognize the approach within seconds of reading a problem.
1. Traversal with index
The most basic pattern: iterate through every element, using the index for comparisons or position-based logic.
2. Two pointers (opposite ends)
Place one pointer at the start, another at the end, and move them inward. Works on sorted arrays or when you need to compare elements from both ends.
3. Two pointers (same direction)
Fast and slow pointers — both start at the beginning. The fast pointer explores ahead, the slow pointer tracks a condition. Used for removing duplicates, detecting cycles, and partitioning.
4. Sliding window
Maintain a "window" of elements as you slide through the array. Fixed-size windows find things like "max sum of k consecutive elements." Variable-size windows handle "smallest subarray with sum >= target." We'll see a full example later.
String operations in Python
Strings in Python are immutable. Every concatenation creates a new string. That's why s += char in a loop is O(n^2) — each step copies the entire string. Use ''.join(list) instead for O(n).
''.join(result) at the end. This converts an O(n^2) operation to O(n). Interviewers notice this.
Problem: Reverse a string in-place
Given a list of characters, reverse it in-place using two pointers. This is LeetCode 344 — a classic warm-up that tests your two-pointer fundamentals.
Approach: Place left at index 0 and right at the last index. Swap, then move both inward. Repeat until they meet.
Time: O(n) — each element visited once. Space: O(1) — swap in-place, no extra array.
Problem: Check palindrome
Determine if a string is a palindrome, considering only alphanumeric characters and ignoring case. This is LeetCode 125.
Approach: Two pointers from opposite ends. Skip non-alphanumeric characters. Compare characters (case-insensitive). If any mismatch, return False.
Time: O(n). Space: O(1) — no extra string allocation.
s == s[::-1]?Problem: Two Sum (sorted array)
Given a sorted array and a target, find two numbers that add up to the target. Return their indices. This is LeetCode 167.
Approach: Start with left=0 and right=len-1. If sum is too small, move left up (bigger number). If too large, move right down (smaller number). Because the array is sorted, each move eliminates one candidate.
Time: O(n). Space: O(1).
Sliding window: max sum subarray
The sliding window pattern avoids recomputing sums from scratch. Instead of summing k elements for every position (O(n*k)), you subtract the element leaving the window and add the one entering. One pass, O(n).
Try it yourself
Longest Substring Without Repeating Characters
Use a sliding window with a set to find the length of the longest substring without repeating characters. This is LeetCode 3 — a top 5 most-asked interview question.
Common mistakes
- Off-by-one in two pointers: Using
left <= rightinstead ofleft < rightcan cause an infinite loop or double-count the middle element. Think carefully about the exit condition. - String concatenation in a loop: Writing
result += charis O(n^2). Use a list and''.join()at the end for O(n). - Forgetting strings are immutable: You cannot swap characters in a string. Convert to
list(s)first, then join back. - Not handling edge cases: Empty arrays, single-element arrays, all-same-element arrays. Always test with
[],[1], and[5, 5, 5]. - Using wrong window update order: In sliding window, subtract the outgoing element before adding the incoming one, or use the formula
sum += arr[i] - arr[i-k]atomically.
Key takeaways
- Arrays give O(1) access by index because of contiguous memory. Python lists are dynamic arrays with O(1) amortized append.
- Two pointers (opposite ends) solve sorted-array problems in O(n) time, O(1) space — reverse, palindrome, two sum.
- Sliding window converts O(n*k) brute force to O(n) for subarray problems. Fixed-size and variable-size are the two variants.
- Strings are immutable in Python. Use
list()+''.join()for in-place-style manipulation. - Always analyze time AND space complexity. Interviewers value O(1) space solutions when they exist.
Challenge
Given an array of heights where height[i] is the height of a vertical line at position i, find two lines that together with the x-axis form a container that holds the most water. Return the maximum water area.
Example: height = [1,8,6,2,5,4,8,3,7] → Output: 49 (between indices 1 and 8).
Constraint: Solve in O(n) time, O(1) space using two pointers.
min(height[left], height[right]) * (right - left). To potentially find a taller container, move the pointer pointing to the shorter line inward. Why? Moving the taller pointer can only decrease the area (width shrinks, height can't improve the min).Quiz
s += char in a loop O(n^2) for strings in Python?You've mastered two pointers and sliding windows.
Now crack the full interview.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →