Learn DSA Part 2: Arrays and Strings - Prefix Sums, Kadane's Algorithm and Matrix Techniques

Arrays and strings are where almost every coding interview starts. They look simple, but most "medium" interview problems are really array problems in disguise: prefix sums, Kadane's algorithm, in-place rearrangement and matrix traversal. If you master the techniques in this article, a big share of interview questions becomes familiar.

This is Part 2 of the Learn DSA series. We cover how arrays work in memory, the cost of each operation, strings in C++ and Java, and the four array techniques you will use again and again. Code is in C++ and Java.

1. How arrays work in memory

An array stores elements of the same type in one contiguous block of memory. Because every element has the same size, the address of element i is simply base + i x size. That is why reading a[i] takes O(1) time no matter how big the array is. Contiguous memory is also cache-friendly, which makes arrays fast in practice.

A static array has a fixed size. A dynamic array (vector in C++, ArrayList in Java) grows automatically by allocating a bigger block, usually about double the size, and copying the elements across.

2. Strings in C++ and Java

A string is an array of characters, so everything above applies. The important difference between the two languages is mutability:

• C++ std::string is mutable. You can change s[i] directly, and s += c is amortized O(1).
• Java String is immutable. Every s = s + c creates a new string and copies all characters, so building a string in a loop this way is O(n^2). Use StringBuilder instead, which appends in amortized O(1).

Most string problems use one of these ideas: count characters with a fixed array of size 26 (for lowercase letters) or a hash map, compare from both ends with two pointers, or use a sliding window over substrings (Part 4).

3. Technique 1: prefix sums

A prefix sum array stores the running total: pre[i] is the sum of the first i elements. After O(n) preprocessing, the sum of any range [l, r] is pre[r + 1] - pre[l] in O(1). Without it, each range query costs O(n).

// Build once in O(n), answer each range sum in O(1)
vector<long long> buildPrefix(const vector<int>& a) {
    vector<long long> pre(a.size() + 1, 0);
    for (size_t i = 0; i < a.size(); i++) pre[i + 1] = pre[i] + a[i];
    return pre;
}
long long rangeSum(const vector<long long>& pre, int l, int r) {
    return pre[r + 1] - pre[l];   // sum of a[l..r]
}

// Build once in O(n), answer each range sum in O(1)
static long[] buildPrefix(int[] a) {
    long[] pre = new long[a.length + 1];
    for (int i = 0; i < a.length; i++) pre[i + 1] = pre[i] + a[i];
    return pre;
}
static long rangeSum(long[] pre, int l, int r) {
    return pre[r + 1] - pre[l];   // sum of a[l..r]
}

Prefix sums combine powerfully with hashing. "Count subarrays with sum k" becomes: for each prefix sum p, how many earlier prefix sums equal p - k? With a hash map that is a single O(n) pass (see Part 3).

4. Technique 2: Kadane's algorithm for maximum subarray

To find the contiguous subarray with the largest sum, the brute force checks every subarray in O(n^2). Kadane's algorithm does it in one pass: at each index, either extend the best subarray ending at the previous index or start fresh here, whichever is larger.

// Maximum subarray sum, O(n) time, O(1) space
long long maxSubarray(const vector<int>& a) {
    long long best = a[0], cur = a[0];
    for (size_t i = 1; i < a.size(); i++) {
        cur = max((long long)a[i], cur + a[i]); // extend or restart
        best = max(best, cur);
    }
    return best;
}

// Maximum subarray sum, O(n) time, O(1) space
static long maxSubarray(int[] a) {
    long best = a[0], cur = a[0];
    for (int i = 1; i < a.length; i++) {
        cur = Math.max(a[i], cur + a[i]);   // extend or restart
        best = Math.max(best, cur);
    }
    return best;
}

This "best answer ending at index i" idea is your first taste of dynamic programming (Part 13). The same pattern solves Best Time to Buy and Sell Stock and maximum product subarray (with a small twist for negative numbers).

5. Technique 3: in-place tricks (reverse and rotate)

Interviewers love asking for O(1) extra space. Two building blocks cover many of these questions:

• Reverse a range by swapping the two ends and moving inward.
• Rotate right by k using three reversals: reverse the whole array, then reverse the first k elements, then reverse the rest. Each element moves once, so it is O(n) time and O(1) space.

// Rotate right by k using three reversals: O(n) time, O(1) space
void rotateRight(vector<int>& a, int k) {
    int n = a.size();
    k %= n;
    reverse(a.begin(), a.end());
    reverse(a.begin(), a.begin() + k);
    reverse(a.begin() + k, a.end());
}

// Rotate right by k using three reversals: O(n) time, O(1) space
static void reverse(int[] a, int l, int r) {
    while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
}
static void rotateRight(int[] a, int k) {
    int n = a.length;
    k %= n;
    reverse(a, 0, n - 1);
    reverse(a, 0, k - 1);
    reverse(a, k, n - 1);
}

Other in-place favourites, such as moving zeroes to the end or the Dutch National Flag sort of 0s, 1s and 2s, use the two-pointer pattern from Part 4.

6. Technique 4: 2D arrays and matrices

A 2D array grid[r][c] is an array of rows. Problems usually ask you to traverse it in an unusual order or treat it as a graph:

• Spiral order: keep four boundaries (top, bottom, left, right) and shrink them after walking each side.
• Rotate 90 degrees clockwise in place: transpose the matrix (swap a[i][j] with a[j][i]), then reverse each row.
• Grid as a graph: each cell is a node connected to its 4 neighbours. Counting islands is a BFS or DFS over the grid (Part 11). Use direction arrays dr = {-1,1,0,0} and dc = {0,0,-1,1} to avoid repeating code.

Always check boundaries (0 <= r < rows and 0 <= c < cols) before reading a neighbour. Missing this check is the most common bug in grid problems.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. Search for them by name on LeetCode or GeeksforGeeks and solve them before moving on.

1. Best Time to Buy and Sell Stock (easy)
2. Move Zeroes (easy)
3. Valid Anagram (easy)
4. Longest Common Prefix (easy)
5. Maximum Subarray (medium, Kadane)
6. Rotate Array (medium)
7. Product of Array Except Self (medium, prefix and suffix products)
8. Subarray Sum Equals K (medium, prefix sum + hash map)
9. Spiral Matrix (medium)
10. Rotate Image (medium)
11. Merge Intervals (medium, sort first)
12. Trapping Rain Water (hard)