Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

More DSA notes