Sliding Window Technique

LeetCode 209: Find the minimal length of a contiguous subarray of which the sum is at least target.

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLen = INT_MAX;
        int windowSum = 0;
        int left = 0;
        int currentLen = 0;
        for (int right = 0; right < nums.size(); ++right) {
            windowSum += nums[right];
            while (windowSum >= target) {
                currentLen = right - left + 1;
                minLen = min(minLen, currentLen);
                windowSum -= nums[left++];
            }
        }
        return minLen == INT_MAX ? 0 : minLen;
    }
};

• The left pointer i and right pointer j define the window. The algorithm expands the window by moving right until the sum condition is met, then contracts it by moving left.
• Time complexity is O(n) because each element is visited at most twice (once by right and once by left).
• Use INT_MAX to initialize the result for minimum search, and INT_MIN for maximum search.
• Ternary operator (condition ? value_if_true : value_if_false) is concise for conditional assignment.

Spiral Matrix Generation

LeetCode 59: Generate an n x n matrix filled with elements from 1 to n² in spiral order.

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;
        while (top <= bottom && left <= right) {
            // left to right
            for (int j = left; j <= right; ++j) mat[top][j] = num++;
            ++top;
            // top to bottom
            for (int i = top; i <= bottom; ++i) mat[i][right] = num++;
            --right;
            // right to left
            if (top <= bottom) {
                for (int j = right; j >= left; --j) mat[bottom][j] = num++;
                --bottom;
            }
            // bottom to top
            if (left <= right) {
                for (int i = bottom; i >= top; --i) mat[i][left] = num++;
                ++left;
            }
        }
        return mat;
    }
};

• The boundaries (top, bottom, left, right) shrink after each layer.
• For an odd n, the center element is automatically filled when the loop processes the last single element.
• Key point: Use four loops to traverse the perimeter, then adjust boundaries inward. This avoids complex index calculations with offset.

Prefix Sum for Range Sum Queries

Given an array, answer multiple queries of the sum of elements between indices a and b (inclusive).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> prefix(n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
        sum += arr[i];
        prefix[i] = sum;
    }
    int a, b;
    while (~scanf("%d %d", &a, &b)) {
        int result;
        if (a == 0) result = prefix[b];
        else result = prefix[b] - prefix[a - 1];
        printf("%d\n", result);
    }
    return 0;
}

• The prefix array stores cumulative sums, enabling O(1) query time.
• ~scanf is a trick: scanf returns the number of items read, or EOF (typically -1). Bitwise NOT of -1 is 0, which ends the loop.
• Use scanf/printf for faster I/O with large input.

Application: Minimum Difference in Land Division

Divide an n×m grid into two contiguous parts by a horizontal or vertical cut, minimizing the absolute difference between the sums of the two parts.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    int total = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
            total += grid[i][j];
        }
    }

    int minDiff = INT_MAX;

    // Horizontal cuts
    int rowSum = 0;
    for (int i = 0; i < n; ++i) {
        int currentRow = 0;
        for (int j = 0; j < m; ++j) currentRow += grid[i][j];
        rowSum += currentRow;
        minDiff = min(minDiff, abs(total - 2 * rowSum));
    }

    // Vertical cuts
    int colSum = 0;
    for (int j = 0; j < m; ++j) {
        int currentCol = 0;
        for (int i = 0; i < n; ++i) currentCol += grid[i][j];
        colSum += currentCol;
        minDiff = min(minDiff, abs(total - 2 * colSum));
    }

    cout << minDiff << endl;
    return 0;
}

• The same logic can be imlpemented without separate accumulation loops by checking at the end of each row/column during traversal:

int minDiff = INT_MAX;
int running = 0;

// Horizontal
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        running += grid[i][j];
        if (j == m - 1) minDiff = min(minDiff, abs(total - 2 * running));
    }
}

running = 0;
// Vertical
for (int j = 0; j < m; ++j) {
    for (int i = 0; i < n; ++i) {
        running += grid[i][j];
        if (i == n - 1) minDiff = min(minDiff, abs(total - 2 * running));
    }
}

• The key insight is that once total sum is known, any partial sum determines the other part's sum (total - partial), and the difference is abs(total - 2 * partial).
• #include <climits> provides constants like INT_MAX, INT_MIN. #include <algorithm> is needed for min, max, abs.

Memory Layout: Arrays vs. Vectors

• A raw 2D array (int arr[n][m]) occupies a contiguous block of memory. Elements are stored in row-major order.
• A vector<vector<int>> is a vector of vectors. The outer vector holds pointers to inner vectors; each inner vector is a contiguous block, but the inner blocks are not necessarily adjacent in memory. This makes vector<vector<int>> more flexible but potentially slower due to non-contiguous memory access.
• A 1D vector<int> is guaranteed to store its elements contiguously, similar to a raw array.