LeetCode 209: Minimum Size Subarray Sum
Problem Statement
Given an array of n positive integers and a positive integer target, find the minimum length of a contiguous subaray whose sum is greater than or equal to target. Return 0 if no such subarray exists.
Sliding Window Solution
The sliding window technique provides an elegant O(n) solution. The key insight is that both window boundaries can move only forward, ensuring linear time complexity.
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int windowStart = 0;
int currentSum = 0;
int minLen = INT_MAX;
for (int windowEnd = 0; windowEnd < nums.size(); windowEnd++) {
currentSum += nums[windowEnd];
while (currentSum >= target) {
int currentLen = windowEnd - windowStart + 1;
minLen = min(minLen, currentLen);
currentSum -= nums[windowStart];
windowStart++;
}
}
return minLen == INT_MAX ? 0 : minLen;
}
};
Alternative Implementation
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, right = 0;
int sum = nums[0];
int result = nums.size() + 1;
while (right < nums.size()) {
if (sum < target) {
right++;
if (right == nums.size()) break;
sum += nums[right];
} else {
result = min(result, right - left + 1);
sum -= nums[left];
left++;
}
}
return result == nums.size() + 1 ? 0 : result;
}
};
The sliding window approach differs from simple two-pointer techniques by maintaining a dynamic window that expands and contracts based on the sum condition.
LeetCode 59: Spiral Matrix II
Problem Statement
Generate an n x n matrix containing integers from 1 to n² in clockwise spiral order.
Solution
The problem can be solved by processing the matrix layer by layer, from outermost to innermost.
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> matrix(n, vector<int>(n, 0));
int startRow = 0, startCol = 0;
int endRow = n - 1, endCol = n - 1;
int counter = 1;
while (startRow <= endRow && startCol <= endCol) {
// Top row (left to right)
for (int col = startCol; col <= endCol; col++)
matrix[startRow][col] = counter++;
startRow++;
// Right column (top to bottom)
for (int row = startRow; row <= endRow; row++)
matrix[row][endCol] = counter++;
endCol--;
// Bottom row (right to left)
if (startRow <= endRow) {
for (int col = endCol; col >= startCol; col--)
matrix[endRow][col] = counter++;
endRow--;
}
// Left column (bottom to top)
if (startCol <= endCol) {
for (int row = endRow; row >= startRow; row--)
matrix[row][startCol] = counter++;
startCol++;
}
}
return matrix;
}
};
Alternative Layer-Based Approach
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> matrix(n, vector<int>(n));
int num = 1;
for (int side = n; side > 0; side -= 2) {
int start = (n - side) / 2;
fillLayer(matrix, start, num, side);
num += side * 4 - 4;
}
return matrix;
}
private:
void fillLayer(vector<vector<int>>& matrix, int start, int num, int side) {
if (side == 1) {
matrix[start][start] = num;
return;
}
int end = start + side - 1;
// Fill top row
for (int j = start; j < end; j++)
matrix[start][j] = num++;
// Fill right column
for (int i = start; i < end; i++)
matrix[i][end] = num++;
// Fill bottom row
for (int j = end; j > start; j--)
matrix[end][j] = num++;
// Fill left column
for (int i = end; i > start; i--)
matrix[i][start] = num++;
}
};
Prefix Sum: Range Query
Problem Statement
Given a integer array, compute the sum of elements within specified index ranges.
Solution with Prefix Sum
The prefix sum technique enables O(1) range sum queries after O(n) preprocessing.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> array(n);
for (int i = 0; i < n; i++)
cin >> array[i];
vector<int> prefix(n);
prefix[0] = array[0];
for (int i = 1; i < n; i++)
prefix[i] = prefix[i - 1] + array[i];
int left, right;
while (cin >> left >> right) {
if (left == 0)
cout << prefix[right] << endl;
else
cout << prefix[right] - prefix[left - 1] << endl;
}
return 0;
}
The key formula: sum(array[l..r]) = prefix[r] - prefix[l-1], with special handling when l = 0.
Land Division Problem
Problem Statement
Divide an n x m grid into two parts (either horizontally or vertically) such that the difference between total values of the two parts is minimized.
Solution Using Prefix Sums
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> grid[i][j];
// Row-wise prefix sums
vector<vector<int>> rowPrefix(n, vector<int>(m));
for (int i = 0; i < n; i++) {
rowPrefix[i][0] = grid[i][0];
for (int j = 1; j < m; j++)
rowPrefix[i][j] = rowPrefix[i][j - 1] + grid[i][j];
}
// Column-wise prefix sums
vector<vector<int>> colPrefix(n, vector<int>(m));
for (int j = 0; j < m; j++) {
colPrefix[0][j] = grid[0][j];
for (int i = 1; i < n; i++)
colPrefix[i][j] = colPrefix[i - 1][j] + grid[i][j];
}
int minDiff = INT_MAX;
// Horizontal cuts
for (int i = 0; i < n - 1; i++) {
int upper = colPrefix[i][m - 1];
int lower = colPrefix[n - 1][m - 1] - colPrefix[i][m - 1];
minDiff = min(minDiff, abs(upper - lower));
}
// Vertical cuts
for (int j = 0; j < m - 1; j++) {
int left = rowPrefix[n - 1][j];
int right = rowPrefix[n - 1][m - 1] - rowPrefix[n - 1][j];
minDiff = min(minDiff, abs(left - right));
}
cout << minDiff << endl;
return 0;
}
The solution computes prefix sums in both dimensions, allowing O(1) calculation of any rectangular region's total value.
Key Takeaways
Interval Definition Consistency: Whether using [left, right] or [left, right) intervals, consistency throughout the code prevents off-by-one errors.
Common Array Algorithm Patterns:
- Binary search for sorted arrays
- Two-pointer techniques for subarray problems
- Sliding window for continuous subarray optimization
- Prefix sum for range queries
Vector Operations in C++:
- 2D vector initialization:
vector<vector<int>> matrix(rows, vector<int>(cols)) - Dynamic resizing with
push_back() - Access patterns and bounds checking