Arrays & Strings

// ✅ Row-major access (cache-friendly) — accesses contiguous memory
for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
        process(grid[i][j]);    // grid[i][0], grid[i][1], ... are adjacent
 
// ❌ Column-major access (cache-unfriendly) — causes cache misses
for (int j = 0; j < cols; j++)
    for (int i = 0; i < rows; i++)
        process(grid[i][j]);    // grid[0][j], grid[1][j], ... are far apart

vector<int> arr = {1, 2, 3, 4, 5};
int n = arr.size();
 
// --- Forward ---
for (int i = 0; i < n; i++) process(arr[i]);
 
// --- Backward ---
for (int i = n - 1; i >= 0; i--) process(arr[i]);
 
// --- Two-pointer (from both ends) ---
int l = 0, r = n - 1;
while (l < r) { process(arr[l], arr[r]); l++; r--; }
 
// --- Sliding window (fixed size k) ---
for (int i = k - 1; i < n; i++) {
    // Window: arr[i-k+1] ... arr[i]
}

void reverse(vector<int>& arr, int l, int r) {
    while (l < r) {
        swap(arr[l], arr[r]);
        l++; r--;
    }
}
// Time: O(n), Space: O(1)

void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k %= n;                          // Handle k > n
    reverse(nums.begin(), nums.end());         // Reverse all
    reverse(nums.begin(), nums.begin() + k);   // Reverse first k
    reverse(nums.begin() + k, nums.end());     // Reverse rest
}
// Time: O(n), Space: O(1)

// Sort array of 0s, 1s, and 2s in-place (LC 75)
void sortColors(vector<int>& nums) {
    int lo = 0, mid = 0, hi = nums.size() - 1;
 
    while (mid <= hi) {
        if (nums[mid] == 0) {
            swap(nums[lo++], nums[mid++]);  // 0: put at front
        } else if (nums[mid] == 1) {
            mid++;                          // 1: already in position
        } else {
            swap(nums[mid], nums[hi--]);    // 2: put at back (don't advance mid!)
        }
    }
}
// Time: O(n), Space: O(1)

// Sort nums containing 1 to n (or 0 to n-1)
void cyclicSort(vector<int>& nums) {
    int i = 0;
    while (i < (int)nums.size()) {
        int correct = nums[i] - 1;           // 1-indexed: correct index = val - 1
        if (nums[i] != nums[correct]) {
            swap(nums[i], nums[correct]);    // Put nums[i] at its correct position
        } else {
            i++;
        }
    }
}
// Time: O(n), Space: O(1)

// Using vector of vectors (most common in interviews)
int m = 3, n = 4;
vector<vector<int>> grid(m, vector<int>(n, 0));
 
grid[row][col] = 42;             // Access element
int rows = grid.size();          // Number of rows
int cols = grid[0].size();       // Number of columns
 
// Direction arrays for 4-directional movement (BFS/DFS on grids)
int dx[] = {0, 0,  1, -1};      // Row changes
int dy[] = {1, -1, 0,  0};      // Col changes
 
for (int d = 0; d < 4; d++) {
    int nx = row + dx[d];
    int ny = col + dy[d];
    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
        // Valid neighbor at (nx, ny)
    }
}

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;
 
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
 
    while (top <= bottom && left <= right) {
        // → Traverse top row
        for (int col = left; col <= right; col++)
            result.push_back(matrix[top][col]);
        top++;
 
        // ↓ Traverse right column
        for (int row = top; row <= bottom; row++)
            result.push_back(matrix[row][right]);
        right--;
 
        // ← Traverse bottom row (if still valid)
        if (top <= bottom) {
            for (int col = right; col >= left; col--)
                result.push_back(matrix[bottom][col]);
            bottom--;
        }
 
        // ↑ Traverse left column (if still valid)
        if (left <= right) {
            for (int row = bottom; row >= top; row--)
                result.push_back(matrix[row][left]);
            left++;
        }
    }
    return result;
}
// Time: O(m×n), Space: O(1) extra

// Transpose: swap matrix[i][j] with matrix[j][i]
void transpose(vector<vector<int>>& mat) {
    int n = mat.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            swap(mat[i][j], mat[j][i]);
}
 
// Rotate 90° clockwise (in-place): Transpose + Reverse each row
void rotate90(vector<vector<int>>& mat) {
    transpose(mat);
    for (auto& row : mat) reverse(row.begin(), row.end());
}
 
// Rotate 90° counter-clockwise: Reverse each row + Transpose
void rotate90CCW(vector<vector<int>>& mat) {
    for (auto& row : mat) reverse(row.begin(), row.end());
    transpose(mat);
}
// Time: O(n²), Space: O(1)

// Collect elements on each diagonal (top-left to bottom-right)
// Diagonal d: all cells where row - col == d (constant)
// Anti-diagonal d: all cells where row + col == d (constant)
 
// Anti-diagonal traversal
int m = matrix.size(), n = matrix[0].size();
for (int d = 0; d < m + n - 1; d++) {
    for (int row = 0; row < m; row++) {
        int col = d - row;
        if (col >= 0 && col < n) {
            process(matrix[row][col]);
        }
    }
}

// Build prefix sum array
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
int n = arr.size();
vector<int> prefix(n + 1, 0);        // prefix[0] = 0 (sentinel)
 
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]
 
// Range sum query [l, r] (0-indexed, inclusive) in O(1)
auto rangeSum = [&](int l, int r) {
    return prefix[r + 1] - prefix[l];
};
 
cout << rangeSum(1, 4);  // arr[1]+arr[2]+arr[3]+arr[4] = 1+4+1+5 = 11

// Build 2D prefix sum (sum of rectangle [0,0] to [i,j])
int m = grid.size(), n = grid[0].size();
vector<vector<int>> ps(m + 1, vector<int>(n + 1, 0));
 
for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        ps[i][j] = grid[i-1][j-1]
                 + ps[i-1][j]        // Above
                 + ps[i][j-1]        // Left
                 - ps[i-1][j-1];     // Remove double-counted top-left
 
// Rectangle sum: rows [r1,r2], cols [c1,c2] (0-indexed) in O(1)
auto rectSum = [&](int r1, int c1, int r2, int c2) {
    return ps[r2+1][c2+1]
         - ps[r1][c2+1]
         - ps[r2+1][c1]
         + ps[r1][c1];
};

// Apply +val to all elements in range [l, r]
vector<int> arr = {0, 0, 0, 0, 0};  // Original array (all zeros)
int n = arr.size();
vector<int> diff(n + 1, 0);          // Difference array
 
auto rangeAdd = [&](int l, int r, int val) {
    diff[l]     += val;    // Start adding val from index l
    diff[r + 1] -= val;    // Stop adding val after index r
};
 
rangeAdd(1, 3, 5);         // Add 5 to indices 1, 2, 3
rangeAdd(2, 4, 3);         // Add 3 to indices 2, 3, 4
 
// Reconstruct array with prefix sum of diff
for (int i = 1; i < n; i++) diff[i] += diff[i - 1];
// diff now contains the actual updated values
 
// Example: arr = [0, 5, 8, 8, 3]  (diff applied)

// Count subarrays with sum == k
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    cnt[0] = 1;    // Empty prefix has sum 0
    int prefixSum = 0, result = 0;
 
    for (int x : nums) {
        prefixSum += x;
        // If (prefixSum - k) was seen before, there's a subarray summing to k
        result += cnt[prefixSum - k];
        cnt[prefixSum]++;
    }
    return result;
}
// Time: O(n), Space: O(n)
 
/*
  Visual: prefix[j] - prefix[i] = k
          → prefix[i] = prefix[j] - k
  For each j, count how many i's satisfy this.
*/

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currSum = nums[0];
 
    for (int i = 1; i < (int)nums.size(); i++) {
        currSum = max(nums[i], currSum + nums[i]);  // Extend or restart
        maxSum  = max(maxSum, currSum);             // Track global maximum
    }
    return maxSum;
}
// Time: O(n), Space: O(1)
 
// One-liner version:
int maxSubArray(vector<int>& nums) {
    int cur = nums[0], best = nums[0];
    for (int i = 1; i < (int)nums.size(); i++)
        cur = max(nums[i], cur + nums[i]), best = max(best, cur);
    return best;
}

pair<int, pair<int,int>> maxSubArrayWithIndices(vector<int>& nums) {
    int maxSum = nums[0], currSum = nums[0];
    int start = 0, end = 0, tempStart = 0;
 
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] > currSum + nums[i]) {
            currSum = nums[i];
            tempStart = i;          // Potential new start
        } else {
            currSum += nums[i];
        }
        if (currSum > maxSum) {
            maxSum = currSum;
            start = tempStart;
            end = i;
        }
    }
    return {maxSum, {start, end}};
}

// Just flip max → min and the comparison
int minSubArray(vector<int>& nums) {
    int minSum = nums[0], currSum = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        currSum = min(nums[i], currSum + nums[i]);
        minSum  = min(minSum, currSum);
    }
    return minSum;
}

int maxProduct(vector<int>& nums) {
    int maxProd = nums[0], minProd = nums[0], result = nums[0];
 
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] < 0) swap(maxProd, minProd);  // Negative flips max and min
        maxProd = max(nums[i], maxProd * nums[i]);
        minProd = min(nums[i], minProd * nums[i]);
        result  = max(result, maxProd);
    }
    return result;
}
// Time: O(n), Space: O(1)

// --- Check if palindrome (ignoring non-alphanumeric) ---
bool isPalindrome(string s) {
    int l = 0, r = s.size() - 1;
    while (l < r) {
        while (l < r && !isalnum(s[l])) l++;  // Skip non-alphanumeric
        while (l < r && !isalnum(s[r])) r--;
        if (tolower(s[l]) != tolower(s[r])) return false;
        l++; r--;
    }
    return true;
}
 
// --- Reverse words in a string ---
// "  the sky is   blue  " → "blue is sky the"
string reverseWords(string s) {
    string result, word;
    stringstream ss(s);
    vector<string> words;
    while (ss >> word) words.push_back(word);
    for (int i = words.size() - 1; i >= 0; i--) {
        result += words[i];
        if (i > 0) result += " ";
    }
    return result;
}
 
// --- String compression (run-length encoding) ---
// "aaabbc" → "a3b2c1"
string compress(const string& s) {
    string result;
    int i = 0;
    while (i < (int)s.size()) {
        char c = s[i];
        int count = 0;
        while (i < (int)s.size() && s[i] == c) { count++; i++; }
        result += c;
        result += to_string(count);
    }
    return result;
}
 
// --- Longest Common Prefix ---
string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];
    for (int i = 1; i < (int)strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {  // While prefix not at position 0
            prefix.pop_back();
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}
// Time: O(S) where S = total characters, Space: O(1)

// --- Naive string search: O(n*m) ---
int naiveSearch(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    for (int i = 0; i <= n - m; i++) {
        bool match = true;
        for (int j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) { match = false; break; }
        }
        if (match) return i;
    }
    return -1;
}
 
// --- STL string::find: uses optimized search internally ---
size_t pos = text.find(pattern);  // npos if not found
if (pos != string::npos) cout << "Found at " << pos;
 
// --- KMP Concept (for reference): O(n + m) ---
// KMP builds a "failure function" (lps array) that avoids re-comparing
// characters we already know match. Critical for pattern-matching problems.
// Full implementation in Chapter 6 (Hashing).

// Split by single character delimiter
vector<string> split(const string& s, char delim) {
    vector<string> tokens;
    string token;
    istringstream stream(s);
    while (getline(stream, token, delim)) {
        if (!token.empty()) tokens.push_back(token);
    }
    return tokens;
}
 
// Split by whitespace (handles multiple spaces)
vector<string> splitBySpace(const string& s) {
    vector<string> tokens;
    string token;
    istringstream stream(s);
    while (stream >> token) tokens.push_back(token);
    return tokens;
}
 
// Join vector of strings
string join(const vector<string>& v, const string& sep) {
    string result;
    for (int i = 0; i < (int)v.size(); i++) {
        result += v[i];
        if (i < (int)v.size() - 1) result += sep;
    }
    return result;
}

// Count character frequency
string s = "interview";
int freq[26] = {};                  // Zero-initialized
for (char c : s) freq[c - 'a']++;  // 'a'=0, 'b'=1, ..., 'z'=25
 
// Check if all characters appear the same number of times
bool allSameFreq = true;
int expected = freq['a' - 'a'];
for (int i = 0; i < 26; i++) {
    if (freq[i] != 0 && freq[i] != expected) { allSameFreq = false; break; }
}
 
// --- Anagram check using frequency array ---
bool isAnagram(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int freq[26] = {};
    for (char c : s) freq[c - 'a']++;
    for (char c : t) {
        if (--freq[c - 'a'] < 0) return false;
    }
    return true;
}
// Time: O(n), Space: O(1) — the freq array is always size 26
 
// --- For uppercase + lowercase ---
int freq128[128] = {};  // All ASCII characters
for (char c : s) freq128[(int)c]++;

// Count distinct characters in every window of size k
string s = "aababcabcd";
int k = 3;
int freq[26] = {};
int distinct = 0;
 
// Initialize first window
for (int i = 0; i < k; i++) {
    if (freq[s[i] - 'a']++ == 0) distinct++;
}
cout << distinct << " ";  // Window [0, k-1]
 
// Slide the window
for (int i = k; i < (int)s.size(); i++) {
    // Add new character
    if (freq[s[i] - 'a']++ == 0) distinct++;
    // Remove old character
    if (--freq[s[i - k] - 'a'] == 0) distinct--;
    cout << distinct << " ";
}

// SUBARRAY problems: usually use sliding window, prefix sum, or Kadane's
// Example: "Find maximum subarray sum" → Kadane's O(n)
 
// SUBSEQUENCE problems: usually use DP (2D table for two sequences)
// Example: "Find length of longest common subsequence" → DP O(n*m)
 
// SUBSTRING problems: sliding window, two pointers, or hashing
// Example: "Find longest substring without repeating chars" → Sliding window O(n)
 
// Quick identification:
// "contiguous" or "subarray" → sliding window / prefix sum
// "not necessarily contiguous" or "subsequence" → DP

// Total subarrays of an array of size n = n*(n+1)/2
// Subarrays starting at i: n-i (from i to i, i to i+1, ..., i to n-1)
// Total = sum from i=0 to n-1 of (n-i) = n + (n-1) + ... + 1 = n(n+1)/2
 
int n = 5;
long long totalSubarrays = (long long)n * (n + 1) / 2;  // 15 for n=5
 
// Enumerate all subarrays
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // Process subarray arr[i..j]
    }
}

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
 
    for (int price : prices) {
        minPrice  = min(minPrice, price);       // Best day to buy (so far)
        maxProfit = max(maxProfit, price - minPrice); // Best profit selling today
    }
    return maxProfit;
}
 
/*
  prices = [7, 1, 5, 3, 6, 4]
  minPrice: 7  1  1  1  1  1
  profit:   0  0  4  2  5  3
  Answer: 5 (buy at 1, sell at 6)
*/
// Time: O(n), Space: O(1)

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (!seen.insert(x).second)  // insert returns {iterator, bool}
            return true;
    }
    return false;
}
// Time: O(n) average, Space: O(n)
 
// Alternative using sort: O(n log n) time, O(1) extra space
bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 1; i < (int)nums.size(); i++)
        if (nums[i] == nums[i - 1]) return true;
    return false;
}

int maxSubArray(vector<int>& nums) {
    int currSum = nums[0];
    int maxSum  = nums[0];
 
    for (int i = 1; i < (int)nums.size(); i++) {
        // Should I extend the current subarray, or start fresh at nums[i]?
        currSum = max(nums[i], currSum + nums[i]);
        maxSum  = max(maxSum, currSum);
    }
    return maxSum;
}
 
/*
  nums    = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  currSum = -2  1  -2  4   3  5  6   1  5
  maxSum  = -2  1   1  4   4  5  6   6  6
  Answer: 6 (subarray [4,-1,2,1])
*/
// Time: O(n), Space: O(1)

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, 1);
 
    // Pass 1: result[i] = product of all elements to the LEFT of i
    int left = 1;
    for (int i = 0; i < n; i++) {
        result[i] = left;
        left *= nums[i];
    }
 
    // Pass 2: multiply result[i] by product of all elements to the RIGHT of i
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= right;
        right *= nums[i];
    }
    return result;
}
 
/*
  nums   =  [1,  2,  3,  4]
  left   =  [1,  1,  2,  6]  (prefix products, shifted by 1)
  right  =  [24, 12, 4,  1]  (suffix products, shifted by 1)
  result =  [24, 12, 8,  6]
*/
// Time: O(n), Space: O(1) extra (output array doesn't count)

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1;   // Empty prefix (sum = 0) appears once
 
    int prefixSum = 0, count = 0;
 
    for (int x : nums) {
        prefixSum += x;
        // How many past prefix sums equal (prefixSum - k)?
        count += prefixCount[prefixSum - k];
        prefixCount[prefixSum]++;
    }
    return count;
}
 
/*
  nums = [1, 1, 1], k = 2
  Step 1: prefixSum=1, look for (1-2)=-1 → 0, count=0, map={0:1, 1:1}
  Step 2: prefixSum=2, look for (2-2)=0  → 1, count=1, map={0:1, 1:1, 2:1}
  Step 3: prefixSum=3, look for (3-2)=1  → 1, count=2, map={0:1, 1:1, 2:1, 3:1}
  Answer: 2  (subarrays [1,1] at positions 0-1 and 1-2)
*/
// Time: O(n), Space: O(n)

void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k %= n;  // k could be larger than n
 
    // Helper: reverse in-place from l to r
    auto rev = [&](int l, int r) {
        while (l < r) swap(nums[l++], nums[r--]);
    };
 
    rev(0, n - 1);     // Reverse all:   [5,6,7,1,2,3,4] → [4,3,2,1,7,6,5]
    rev(0, k - 1);     // Reverse [0,k): [5,6,7,1,2,3,4]
    rev(k, n - 1);     // Reverse [k,n): [5,6,7,1,2,3,4]
}
 
/*
  nums = [1,2,3,4,5,6,7], k = 3
  After rev(0,6): [7,6,5,4,3,2,1]
  After rev(0,2): [5,6,7,4,3,2,1]
  After rev(3,6): [5,6,7,1,2,3,4]  ✅
*/
// Time: O(n), Space: O(1)

int trap(vector<int>& height) {
    int n = height.size();
    vector<int> maxLeft(n), maxRight(n);
 
    // maxLeft[i]: tallest bar to the LEFT of and including i
    maxLeft[0] = height[0];
    for (int i = 1; i < n; i++)
        maxLeft[i] = max(maxLeft[i-1], height[i]);
 
    // maxRight[i]: tallest bar to the RIGHT of and including i
    maxRight[n-1] = height[n-1];
    for (int i = n - 2; i >= 0; i--)
        maxRight[i] = max(maxRight[i+1], height[i]);
 
    // Water at position i = min(maxLeft, maxRight) - height[i]
    int water = 0;
    for (int i = 0; i < n; i++)
        water += min(maxLeft[i], maxRight[i]) - height[i];
 
    return water;
}
 
/*
  height =   [0,1,0,2,1,0,1,3,2,1,2,1]
  maxLeft =  [0,1,1,2,2,2,2,3,3,3,3,3]
  maxRight = [3,3,3,3,3,3,3,3,2,2,2,1]
  water at each: 0,0,1,0,1,2,1,0,0,1,0,0 → total = 6
*/
// Time: O(n), Space: O(n)
 
// ─── Two-Pointer Optimization: O(1) Space ───────────────────────────────────
int trap_twoPointer(vector<int>& height) {
    int l = 0, r = height.size() - 1;
    int maxL = 0, maxR = 0, water = 0;
 
    while (l < r) {
        if (height[l] < height[r]) {
            maxL = max(maxL, height[l]);
            water += maxL - height[l];
            l++;
        } else {
            maxR = max(maxR, height[r]);
            water += maxR - height[r];
            r--;
        }
    }
    return water;
}
// Time: O(n), Space: O(1)

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> result;
 
    for (int i = 0; i < (int)nums.size(); i++) {
        int idx = abs(nums[i]) - 1;    // Map value to index (1-indexed → 0-indexed)
 
        if (nums[idx] < 0) {
            result.push_back(abs(nums[i]));  // Already visited → duplicate!
        } else {
            nums[idx] = -nums[idx];          // Mark as visited by negating
        }
    }
    return result;
}
 
/*
  nums = [4,3,2,7,8,2,3,1]
  i=0: idx=3, nums[3]=7>0, negate → nums=[4,3,2,-7,8,2,3,1]
  i=1: idx=2, nums[2]=2>0, negate → nums=[4,3,-2,-7,8,2,3,1]
  i=2: idx=1, nums[1]=3>0, negate → nums=[4,-3,-2,-7,8,2,3,1]
  i=3: idx=6, nums[6]=3>0, negate → nums=[4,-3,-2,-7,8,2,-3,1]
  i=4: idx=7, nums[7]=1>0, negate → nums=[4,-3,-2,-7,8,2,-3,-1]
  i=5: idx=1, nums[1]=-3<0, DUPLICATE: 2 ✅
  i=6: idx=2, nums[2]=-2<0, DUPLICATE: 3 ✅
*/
// Time: O(n), Space: O(1) extra

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
 
    int freq[26] = {};
    for (char c : s) freq[c - 'a']++;
    for (char c : t) {
        if (--freq[c - 'a'] < 0) return false;  // t has more of this char
    }
    return true;
}
// Time: O(n), Space: O(1) — fixed 26-element array
 
// For Unicode / any characters: use unordered_map instead

int maxProduct(vector<int>& nums) {
    int maxProd = nums[0];
    int minProd = nums[0];
    int result  = nums[0];
 
    for (int i = 1; i < (int)nums.size(); i++) {
        // If nums[i] < 0, max and min swap roles
        if (nums[i] < 0) swap(maxProd, minProd);
 
        maxProd = max(nums[i], maxProd * nums[i]);
        minProd = min(nums[i], minProd * nums[i]);
        result  = max(result, maxProd);
    }
    return result;
}
 
/*
  nums     = [2, 3, -2, 4]
  maxProd  = 2  6  -2  4
  minProd  = 2  3 -12  -8  (tracks minimum for future negatives)
  result   = 2  6   6   6
  Answer: 6 (subarray [2, 3])
*/
// Time: O(n), Space: O(1)

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
 
    while (top <= bottom && left <= right) {
        for (int col = left;   col <= right;  col++) result.push_back(matrix[top][col]);
        top++;
        for (int row = top;    row <= bottom; row++) result.push_back(matrix[row][right]);
        right--;
        if (top <= bottom) {
            for (int col = right; col >= left;  col--) result.push_back(matrix[bottom][col]);
            bottom--;
        }
        if (left <= right) {
            for (int row = bottom; row >= top;  row--) result.push_back(matrix[row][left]);
            left++;
        }
    }
    return result;
}
// Time: O(m×n), Space: O(1) extra

class NumMatrix {
    vector<vector<int>> ps;  // ps[i][j] = sum of rectangle [0,0] to [i-1,j-1]
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        ps.assign(m + 1, vector<int>(n + 1, 0));
 
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                ps[i][j] = matrix[i-1][j-1]
                         + ps[i-1][j]
                         + ps[i][j-1]
                         - ps[i-1][j-1];
    }
 
    // Sum of rectangle: rows [r1..r2], cols [c1..c2] (0-indexed)
    int sumRegion(int r1, int c1, int r2, int c2) {
        return ps[r2+1][c2+1]
             - ps[r1][c2+1]
             - ps[r2+1][c1]
             + ps[r1][c1];
    }
};
// Build: O(m×n), Query: O(1), Space: O(m×n)