Notes › DSA
Arrays & Two Pointers
An array stores elements of the same type in contiguous memory. Because every element has the same size, the address of a[i] is base + i × size — that's why access by index is O(1).
Operation costs
| Operation | Cost | Why |
|---|---|---|
Access a[i] |
O(1) | address arithmetic |
Update a[i] = x |
O(1) | |
| Search (unsorted) | O(n) | check each element |
| Search (sorted) | O(log n) | binary search |
| Insert / delete at the end (dynamic array) | O(1) amortised | |
| Insert / delete in the middle | O(n) | shift the elements after it |
In C++ use vector, in Java ArrayList (or int[]), in Python list.
Basic patterns
// reverse in place
int i = 0, j = n - 1;
while (i < j) swap(a[i++], a[j--]);
// second largest in one pass
int first = INT_MIN, second = INT_MIN;
for (int x : a) {
if (x > first) { second = first; first = x; }
else if (x > second && x != first) second = x;
}
The two-pointer technique
Use two indices instead of nested loops — often turning O(n²) into O(n).
1. Opposite ends (sorted array)
Pair with a given sum:
int l = 0, r = n - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) return true;
if (s < target) l++; // need a bigger sum
else r--; // need a smaller sum
}
return false;
Why it works: when the sum is too small, a[l] can't form the answer with any element (they're all ≤ a[r]), so we can drop it safely.
2. Slow and fast (same direction)
Remove duplicates from a sorted array in place:
int k = 0; // a[0..k] holds the unique values
for (int i = 1; i < n; i++)
if (a[i] != a[k]) a[++k] = a[i];
return k + 1; // new length
Move zeroes to the end works the same way: k points to where the next non-zero goes.
3. Two arrays
Merge two sorted arrays: one pointer in each, take the smaller element — O(n + m).
3Sum (find all unique triplets with sum 0)
Sort, fix one element, then two pointers on the rest:
def three_sum(a):
a.sort(); res = []
for i in range(len(a) - 2):
if i and a[i] == a[i - 1]: continue # skip duplicate first values
l, r = i + 1, len(a) - 1
while l < r:
s = a[i] + a[l] + a[r]
if s < 0: l += 1
elif s > 0: r -= 1
else:
res.append([a[i], a[l], a[r]]); l += 1; r -= 1
while l < r and a[l] == a[l - 1]: l += 1 # skip duplicates
return res
O(n²) instead of the brute-force O(n³).
Container with most water
Area = min(h[l], h[r]) × (r − l). Start at both ends and move the shorter line inward — moving the taller one can never give more water.
Prefix sums — range sums in O(1)
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
// sum of a[l..r] = pre[r + 1] - pre[l]
Subarray sum equals k (with negatives): count how many earlier prefix sums equal current − k using a hash map — O(n).
Kadane's algorithm — maximum subarray sum
long long best = a[0], cur = a[0];
for (int i = 1; i < n; i++) {
cur = max((long long)a[i], cur + a[i]); // extend the current subarray or start fresh
best = max(best, cur);
}
O(n) time, O(1) space. Works when all numbers are negative too.
Dutch national flag (sort 0s, 1s and 2s in one pass)
int lo = 0, mid = 0, hi = n - 1;
while (mid <= hi) {
if (a[mid] == 0) swap(a[lo++], a[mid++]);
else if (a[mid] == 1) mid++;
else swap(a[mid], a[hi--]); // don't move mid: the swapped value is unchecked
}
Rotate an array by k (in place)
Reverse the whole array, then reverse the first k and the rest. O(n) time, O(1) space.
2-D arrays
a[i][j] in row-major order. Common tasks: transpose (swap a[i][j] and a[j][i] for j > i), rotate 90° (transpose + reverse each row), spiral traversal (four boundaries shrinking inward).
Common mistakes
- Off-by-one errors with
<vs<=. - Integer overflow when summing — use
long long/long. - Modifying an array while iterating over it in Python.
- Forgetting to skip duplicates in 3Sum-style problems.
Practice
Arrays problems · Hashing & Two Pointers problems. Classic list: Two Sum II, 3Sum, Container With Most Water, Move Zeroes, Sort Colors, Maximum Subarray, Rotate Array, Merge Sorted Array, Trapping Rain Water.
Interview one-liners
- Arrays give O(1) access because memory is contiguous.
- Two pointers replace a nested loop when the data is sorted or the window moves one way.
- Prefix sums answer range-sum queries in O(1) after O(n) setup.
- Kadane: keep the best subarray ending here; restart when it goes below the current element.
- Related: Sliding Window, Hashing.