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.

Contiguous Memory Layout
arr[0]
arr[1]
arr[2]
arr[3]
arr[4]
Each element sits at a fixed offset from the start. Index lookup = O(1).

Operations Big O

OperationTime ComplexityWhy
Access by indexO(1)Direct address calculation
Search (unsorted)O(n)Must check each element
Insert at endO(1) amortizedAppend; occasional resize
Insert at middleO(n)Shift all elements after
DeleteO(n)Shift elements to fill gap
Interview insight:
When the interviewer says "array," think contiguous memory and O(1) access. When they say "linked list," think pointers and O(n) access. Knowing the tradeoff is half the battle.

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.

traversal.py Basic index traversal
OUTPUT
3 -1

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.

Two Pointers — Opposite Direction
L=0
...
middle
...
R=n-1
Move L right, R left. They meet in the middle. O(n) total.

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).

string_ops.py Essential string operations
OUTPUT
!dlroW ,olleH ['Hello', 'World!'] Hello - World! 65 A {'b': 1, 'a': 3, 'n': 2}
Performance tip:
Building a string character by character? Collect into a list, then ''.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.

🔄
Pattern
Two Pointers — Opposite Ends

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.

reverse_string.py Two pointer swap
OUTPUT
['o', 'l', 'l', 'e', 'h']
Step-by-Step: reverse_string(list("hello"))
Step 0: [h, e, l, l, o]   L=0, R=4 → swap h,o
Step 1: [o, e, l, l, h]   L=1, R=3 → swap e,l
Step 2: [o, l, l, e, h]   L=2, R=2 → done (L meets R)

Problem: Check palindrome

Determine if a string is a palindrome, considering only alphanumeric characters and ignoring case. This is LeetCode 125.

🪞
Pattern
Two Pointers — Skip Non-Alphanumeric

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.

palindrome.py Two pointer approach
OUTPUT
True True False
Why not just s == s[::-1]?
That works but creates a reversed copy — O(n) extra space. The two-pointer approach uses O(1) space. Interviewers want to see you can do it without extra allocation. Also, the skip logic for non-alphanumeric characters is hard to do cleanly with slicing.

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.

🎯
Pattern
Two Pointers — Binary Narrowing

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).

two_sum_sorted.py Two pointers on sorted array
OUTPUT
[0, 1] [2, 3]
Walkthrough: two_sum_sorted([2, 7, 11, 15], target=9)
Step 1: L=0(2), R=3(15) → sum=17 > 9 → move R left
Step 2: L=0(2), R=2(11) → sum=13 > 9 → move R left
Step 3: L=0(2), R=1(7)  → sum=9  = 9 → found [0, 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).

sliding_window.py Fixed-size sliding window
OUTPUT
9 16
Sliding Window: [2, 1, 5, 1, 3, 2], k=3
Window [2, 1, 5, 1, 3, 2] → sum = 8
Window [2, 1, 5, 1, 3, 2] → sum = 7  (-2, +1)
Window [2, 1, 5, 1, 3, 2] → sum = 9  (-1, +3) max!
Window [2, 1, 5, 1, 3, 2] → sum = 6  (-5, +2)
Variable-size window:
When the window size isn't fixed (e.g., "smallest subarray with sum >= target"), use a while loop to shrink the window from the left whenever the condition is met. The "Try It Yourself" section below uses a variable-size window.

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.

try_it.py Editable — click Run to execute

Common mistakes

  • Off-by-one in two pointers: Using left <= right instead of left < right can cause an infinite loop or double-count the middle element. Think carefully about the exit condition.
  • String concatenation in a loop: Writing result += char is 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

Container With Most Water
Problem

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.

Start with the widest container (left=0, right=n-1). The area is 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

Question 1 of 5
What is the time complexity of accessing an element by index in a Python list?
Question 2 of 5
Why is s += char in a loop O(n^2) for strings in Python?
Question 3 of 5
In the two-pointer approach for Two Sum on a sorted array, when should you move the left pointer to the right?
Question 4 of 5
What is the key advantage of the sliding window technique over brute force for subarray problems?
Question 5 of 5
What is the time complexity of inserting an element at the middle of a Python list of size n?
0
/5
Great work! You understand arrays, strings, and core interview patterns.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →