tomatocream/cpp-flashcards
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
master
cpp-flashcards/org/questions/qn_00.org
T

27 KiB
Raw Permalink Blame History

Subarrays with Sum Equal to K

Subarray Sum Equals K - Brute Force [algorithm:array]

Front

See LC 560. Find the total number of continuous subarrays whose sum equals k. Solve using the brute force approach. Example: nums = [1,2,3], k = 3 → Output: 2 ([1,2] and [3])

Back 

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        int sum = 0;
        for (int j = i; j < nums.size(); j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

Time: O(n^2), Space: O(1)

Subarray Sum Equals K - Prefix Sum + Hash Map [algorithm:array]

Front

See LC 560. Find the total number of continuous subarrays whose sum equals k. Solve optimally using prefix sum with a hash map. Example: nums = [1,2,3], k = 3 → Output: 2

Back 

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int,int> prefixCount;
    prefixCount[0] = 1;  // base case: sum of 0 appears once
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        // If (sum - k) exists, those prefixes form valid subarrays
        count += prefixCount[sum - k];
        prefixCount[sum]++;
    }
    return count;
}

Time: O(n), Space: O(n)

Subarray Sum Equals K - Why prefixCount[0] = 1 [algorithm:interview]

Front

See LC 560. In the optimal subarray sum solution (prefix sum + hash map), why is `prefixCount[0] = 1` initialized?

Back

It handles the case where a subarray starts from index 0 and its sum equals k.

When sum == k at some index, we look up prefixCount[sum - k] = prefixCount[0]. Without the initialization, this lookup would return 0, missing valid subarrays like [3] where k = 3.

The base case means: "a prefix sum of 0 exists once (before any element)" — conceptually the empty prefix.

Subarray Sum Divisible by K [algorithm:array]

Front

See LC 974. Find the total number of continuous subarrays whose sum is divisible by k. Example: nums = [23,2,4,6,7], k = 6 → Output: 2 ([2,4] and [7])

Back 

int subarraysDivByK(vector<int>& nums, int k) {
    unordered_map<int,int> prefixCount;
    prefixCount[0] = 1;
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        // Modulo can be negative in C++, fix with ((sum % k) + k) % k
        int remainder = ((sum % k) + k) % k;
        count += prefixCount[remainder];
        prefixCount[remainder]++;
    }
    return count;
}

Key insight: If two prefix sums have the same remainder mod k, their subarray sum is divisible by k.

Time: O(n), Space: O(min(n, k))

Longest Subarray Sum Equals K [algorithm:array]

Front

See LC 325. Find the maximum length of a contiguous subarray that sums to k. Example: nums = [1,-1,5,-2,3], k = 3 → Output: 4 ([1,-1,5,-2])

Back 

int maxSubArrayLen(vector<int>& nums, int k) {
    unordered_map<int,int> firstOccurrence;
    firstOccurrence[0] = 0;  // sum 0 at index 0 (1-based)
    int sum = 0, maxLen = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        // Check if subarray ending here sums to k
        if (firstOccurrence.count(sum - k)) {
            maxLen = max(maxLen, i + 1 - firstOccurrence[sum - k]);
        }
        // Store first occurrence only (for longest)
        if (!firstOccurrence.count(sum)) {
            firstOccurrence[sum] = i + 1;
        }
    }
    return maxLen;
}

Key difference from counting: store only the first occurrence of each prefix sum to maximize length.

Time: O(n), Space: O(n)

Subarray Sum Equals K - Negative Numbers? [algorithm:interview]

Front

See LC 560. Does the prefix sum + hash map approach for "subarray sum equals k" work when the array contains negative numbers? Why?

Back

Yes, it works with negative numbers.

The prefix sum approach does NOT require positive-only elements. It works for any integer array because:

  • prefix[j] - prefix[i] = sum[i+1..j] is always true regardless of sign
  • The hash map tracks ALL prefix sums seen, positive or negative
  • We only need (sum - k) to exist in the map

This makes it superior to the sliding window approach, which only works for non-negative arrays.

Subarray Sum Equals K - Sliding Window Limitation [algorithm:interview]

Front

See LC 560. Can you use the sliding window technique to solve "subarray sum equals k"? When does it work?

Back

Sliding window ONLY works when all elements are non-negative (positive or zero).

When all elements >= 0:

  • Expanding the window increases the sum
  • Shrinking the window decreases the sum
  • This monotonicity lets us adjust the window

Sliding window fails with negative numbers because adding/removing elements doesn't monotonically change the sum.

Prefer prefix sum + hash map — it works for all cases (positive, negative, zero).

Subarray Sum Variations — Master Table [algorithm:array]

Front

What's the master table of subarray sum variations and their approaches?

Back

Question Constraint Approach Key Data Structure Time
Count subarrays sum = K Any integers Prefix sum unordered_map<sum, frequency> O(n)
Longest subarray sum = K Any integers Prefix sum unordered_map<sum, first_index> O(n)
Shortest subarray sum ≥ K Any integers Prefix sum + monotonic deque deque of indices O(n)
Shortest subarray sum = K Any integers Prefix sum + ordered map map<sum, last_index> O(n log n)
Divisible by K Any integers Prefix sum + modulo unordered_map<remainder, freq> O(n)
Sum in range [lower, upper] Any integers Prefix sum + BST multiset / Fenwick / segment tree O(n log n)
Max circular subarray sum Any integers Kadane's + total - min_subarray 2x Kadane O(n)
Subarray sum with only positives Positives only Sliding window Two pointers O(n)
2D matrix subarray sum = K 2D grid Fix rows, compress to 1D Prefix sum on compressed row O(n^3)
At most K distinct elements Frequency constraint Sliding window + freq map Hash map of counts O(n)
Subarray with exactly K ones Binary array Store indices of 1s Vector of positions O(n)
Two non-overlapping subarrays each = K Any integers Prefix sum + track both sides 2 pass with prefix map O(n)

Core pattern: prefix[j] - prefix[i] = subarray(i+1..j). The variation changes what you store and query.

Subarray Shortest Sum ≥ K — Monotonic Deque [algorithm:array]

Front

See LC 862. Find the length of the shortest contiguous subarray with sum ≥ K. Works with negative numbers. Example: nums = [84,-37,32,40,95], K = 167 → Output: 3

Back 

int shortestSubarray(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    
    deque<int> dq;  // stores indices, prefix[dq[j]] is increasing
    int minLen = INT_MAX;
    
    for (int i = 0; i <= n; i++) {
        // If prefix[i] - prefix[dq.front()] >= K, pop front and record length
        while (!dq.empty() && prefix[i] - prefix[dq.front()] >= k) {
            minLen = min(minLen, i - dq.front());
            dq.pop_front();
        }
        // Maintain monotonic increasing order of prefix values in deque
        while (!dq.empty() && prefix[i] < prefix[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    return minLen == INT_MAX ? -1 : minLen;
}

Time: O(n), Space: O(n)

Key insight: Maintain a deque of indices where prefix sums are increasing. If prefix[i] - prefix[dq.front()] ≥ K, then any index after dq.front() gives a shorter valid subarray.

Subarray Sum in Range [lower, upper] [algorithm:array]

Front

See LC 327. Count the number of subarrays whose sum lies in range [lower, upper]. Example: nums = [-2,5,-1], lower = -2, upper = 2 → Output: 3 ([-2], [-1], [5,-1])

Back 

int countRangeSum(vector<int>& nums, int lower, int upper) {
    int n = nums.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    
    // Use merge sort to count valid pairs
    return mergeCount(prefix, 0, n, lower, upper);
}

int mergeCount(vector<long long>& P, int lo, int hi, int lower, int upper) {
    if (lo >= hi - 1) return 0;
    int mid = lo + (hi - lo) / 2;
    int count = mergeCount(P, lo, mid, lower, upper)
              + mergeCount(P, mid, hi, lower, upper);
    
    // Count valid (i, j) pairs where P[j] - P[i] in [lower, upper]
    int j = mid, k = mid, t = mid;
    for (int i = lo; i < mid; i++) {
        while (k <= hi && P[k] - P[i] < lower) k++;
        while (t <= hi && P[t] - P[i] <= upper) t++;
        count += (t - k);
    }
    
    // Merge step
    vector<long long> temp;
    int p1 = lo, p2 = mid;
    while (p1 < mid && p2 < hi) {
        if (P[p1] <= P[p2]) temp.push_back(P[p1++]);
        else temp.push_back(P[p2++]);
    }
    while (p1 < mid) temp.push_back(P[p1++]);
    while (p2 < hi) temp.push_back(P[p2++]);
    for (int i = 0; i < (int)temp.size(); i++) P[lo + i] = temp[i];
    
    return count;
}

Time: O(n log n), Space: O(n)

Why not hash map? Hash map can't count how many prefix sums fall in a range. Merge sort counts (i, j) pairs where P[j] - P[i] ∈ [lower, upper] during the merge step.

Max Circular Subarray Sum [algorithm:array]

Front

See LC 918. Find the maximum sum of a non-empty subarray in a circular array. Example: nums = [1,-2,3,-2] → Output: 3 Example: nums = [5,-3,5] → Output: 10 (wraps around: [5, 5])

Back 

int maxSubarraySumCircular(vector<int>& nums) {
    int total = 0, maxSum = nums[0], curMax = 0;
    int minSum = nums[0], curMin = 0;
    
    for (int num : nums) {
        curMax = max(curMax + num, num);
        maxSum = max(maxSum, curMax);
        curMin = min(curMin + num, num);
        minSum = min(minSum, curMin);
        total += num;
    }
    
    // If all numbers are negative, maxSum is the answer (total - minSum = 0)
    return maxSum < 0 ? maxSum : max(maxSum, total - minSum);
}

Time: O(n), Space: O(1)

Two cases:

  1. Maximum subarray does NOT wrap — standard Kadane's (maxSum)
  2. Maximum subarray DOES wrap — total - minSubarray (remove the minimum subarray from the middle)

Edge case: all negative → total - minSum = 0, which is wrong. Return maxSum instead.

2D Matrix Subarray Sum = K [algorithm:array]

Front

See Submatrices Sum to Target. Given a 2D matrix, find the number of submatrices whose sum equals K. Example: matrix = 0,1,0],[1,1,1],[0,1,0, K = 0 → Output: 4

Back 

int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int count = 0;
    
    // Fix top and bottom rows, compress to 1D array
    for (int r1 = 0; r1 < m; r1++) {
        vector<int> colSum(n, 0);
        for (int r2 = r1; r2 < m; r2++) {
            // Add row r2 to the compressed column sums
            for (int c = 0; c < n; c++) {
                colSum[c] += matrix[r2][c];
            }
            // Now solve 1D subarray sum = target
            unordered_map<int,int> prefixCount;
            prefixCount[0] = 1;
            int sum = 0;
            for (int val : colSum) {
                sum += val;
                count += prefixCount[sum - target];
                prefixCount[sum]++;
            }
        }
    }
    return count;
}

Time: O(m^2 * n), Space: O(n)

Key idea: Fix two rows (r1, r2), compress columns between them into a 1D array. Then the problem reduces to 1D subarray sum = K.

Exactly K Distinct Elements with Sum = K [algorithm:array]

Front

Find the length of the longest subarray with at most K distinct elements and sum = K.

Back 

int longestSubarray(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    int sum = 0, distinct = 0, maxLen = 0;
    int left = 0;
    
    for (int right = 0; right < nums.size(); right++) {
        if (freq[nums[right]] == 0) distinct++;
        freq[nums[right]]++;
        sum += nums[right];
        
        // Shrink while distinct > K or sum > k
        while (distinct > k || sum > k) {
            freq[nums[left]]--;
            if (freq[nums[left]] == 0) distinct--;
            sum -= nums[left];
            left++;
        }
        
        if (sum == k) maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

Time: O(n), Space: O(min(n, K))

This combines sliding window (distinct elements constraint) with sum check. The two constraints (distinct count + sum) make it trickier than simple sliding window.

Binary Array — Exactly K Ones [algorithm:array]

Front

See LC 1004. Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's. Example: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 → Output: 6

Back 

int longestOnes(vector<int>& nums, int k) {
    int left = 0, maxLen = 0;
    for (int right = 0; right < nums.size(); right++) {
        if (nums[right] == 0) k--;
        while (k < 0) {
            if (nums[left] == 0) k++;
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

Time: O(n), Space: O(1)

Sliding window: expand right, count zeros. When zeros exceed k, shrink from left.

Two Non-Overlapping Subarrays Each Sum = K [algorithm:array]

Front

Find the maximum sum of two non-overlapping subarrays with lengths L and M. Example: nums = [0,6,5,2,2,5,1,9,4], L = 1, M = 2 → Output: 20 ([9] and [6,5])

Back 

int maxSumTwoNoOverlap(vector<int>& nums, int L, int M) {
    int n = nums.size();
    // Prefix sums for O(1) subarray sum queries
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    
    auto sum = [&](int i, int j) { return prefix[j + 1] - prefix[i]; };
    
    int maxL = 0, maxM = 0, result = 0;
    
    // Case 1: L comes before M
    for (int i = L + M; i <= n; i++) {
        maxL = max(maxL, sum(i - L - M, i - M - 1));
        maxM = max(maxM, sum(i - M, i - 1));
        result = max(result, maxL + maxM);
    }
    
    // Case 2: M comes before L
    maxL = 0; maxM = 0; result = 0;
    for (int i = L + M; i <= n; i++) {
        maxM = max(maxM, sum(i - L - M, i - L - 1));
        maxL = max(maxL, sum(i - L, i - 1));
        result = max(result, maxL + maxM);
    }
    
    return result;
}

Time: O(n), Space: O(n)

Two cases: L before M, or M before L. Track the running maximum of the first subarray while computing the second.

Subarray Sum — All Relationships Diagram [algorithm:interview]

Front

What's the decision tree for choosing the right subarray sum approach?

Back

  1. Are there negative numbers? → YES: Prefix sum approach (hash map, BST, or merge sort) → NO: Sliding window is possible
  2. What are you counting? → Count all: hash_map<sum, frequency> → Longest: hash_map<sum, first_index> → Shortest: hash_map<sum, last_index> or monotonic deque
  3. Is the target a range [lower, upper]? → YES: Merge sort (count pairs in range) or Fenwick tree / BST
  4. Is it divisible by K? → YES: hash_map<remainder, frequency> with modulo
  5. Is the array circular? → YES: Kadane's twice — max(max_subarray, total - min_subarray)
  6. Is it 2D? → YES: Fix 2 rows, compress to 1D, then prefix sum
  7. Are elements only 0/1? → YES: Store indices of 1s, or sliding window counting zeros
  8. Are there constraints on distinct elements? → YES: Sliding window + frequency map
  9. Are there multiple non-overlapping subarrays? → YES: 2-pass — track running max of first while computing second

The fundamental identity: subarray(i,j) = prefix[j+1] - prefix[i]. Everything else is about what you do with the prefix array.

Subarray Sum — Core Trigger Heuristic [algorithm:interview]

Front

What is the most reliable heuristic for recognizing when to use Prefix Sums?

Back

When you see "subarray" and "sum" in the same problem description, Prefix Sums should be your immediate first thought.

The core formula: Sum(i..j) = PrefixSum[j] - PrefixSum[i-1]

This turns a range query into a difference between two points, eliminating the need to re-scan the array.

The mental trigger is simple: subarray + sum → prefix sums. Always.

Subarray Sum — When to Use Sliding Window vs Prefix Sum [algorithm:interview]

Front

When should you use Sliding Window vs Prefix Sum + Hash Map for subarray sum problems?

Back

Condition Use Why
All numbers ≥ 0, need target sum or max length Sliding Window Monotonic: expanding always increases sum, shrinking always decreases. O(1) space vs O(n).
Numbers can be negative, need exact target sum Prefix Sum + Hash Map Monotonicity broken. Adding an element could make sum smaller. Must remember past states.
Frequent updates between queries Fenwick Tree / Segment Tree Prefix sum array takes O(n) to update. Trees give O(log n) update + query.

Rule of thumb: check for negative numbers first. If none exist, sliding window wins.

Subarray Product — Prefix Product Pattern [algorithm:array]

Front

How does the prefix sum pattern translate to subarray product problems?

Back

The prefix sum pattern translates directly into a Prefix Product:

Product(i..j) = PrefixProduct[j] / PrefixProduct[i-1]

Instead of subtracting, you divide.

Edge case: zeros break division. Handle by:

  1. Segmentation — split the array at zeros, solve each segment independently
  2. Track position of last seen zero to reset boundaries

Example: count subarrays with product < K (all positive):

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k == 0) return 0;
    int count = 0, product = 1, left = 0;
    for (int right = 0; right < nums.size(); right++) {
        product *= nums[right];
        while (left <= right && product >= k) product /= nums[left++];
        count += right - left + 1;
    }
    return count;
}

Subarray with Equal 0s and 1s — Value Mapping [algorithm:array]

Front

Find the maximum length of a contiguous subarray with equal number of 0s and 1s. Example: nums = [1,0,1] → Output: 2 ([1,0] or [0,1])

Back

Treat 0 as -1 and 1 as +1. The problem becomes: "Find the longest subarray whose sum equals 0."

int findMaxLength(vector<int>& nums) {
    unordered_map<int,int> firstOccurrence;
    firstOccurrence[0] = 0;  // sum 0 at index 0 (1-based)
    int sum = 0, maxLen = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += (nums[i] == 1) ? 1 : -1;
        if (firstOccurrence.count(sum)) {
            maxLen = max(maxLen, i + 1 - firstOccurrence[sum]);
        } else {
            firstOccurrence[sum] = i + 1;
        }
    }
    return maxLen;
}

Time: O(n), Space: O(n)

This is the "prefix state" generalization: map values to +1/-1, then it's just prefix sum = 0.

Subarray with Equal Odd and Even Numbers [algorithm:array]

Front

Find the longest subarray with equal number of odd and even numbers.

Back

Map every even number to +1 and every odd number to -1 (or vice versa). The problem becomes: "Find the longest subarray whose sum equals 0."

Same approach as equal 0s and 1s: prefix sum + hash map storing first occurrence.

This is the same "prefix state" generalization applied to a different domain.

Multi-Category Balance — (A, B, C) Equal Counts [algorithm:array]

Front

Find the longest subarray with equal number of 'A's, 'B's, and 'C's.

Back

You can't use a single scalar (+1/-1) for three categories. Instead, track relative differences between counts.

Maintain running counts: c_A, c_B, c_C. At each step, compute the tuple of differences: (c_A - c_B, c_B - c_C).

If this tuple repeats later in the array, the elements between those indices have perfectly balanced A, B, C counts.

Data structure: hash map where the key is the state tuple: map<pair<int,int>, int> firstOccurrence;

The tuple (diff_AB, diff_BC) captures the full relative state. If two positions share the same tuple, the subarray between them has zero net change in all three relative differences → equal counts.

Time: O(n), Space: O(n)

Subarray Product Is Positive / Negative [algorithm:array]

Front

Find the maximum length of a subarray with a positive (or negative) product.

Back

Map: positive → +1, negative → -1, zero → resets the window.

A subarray has positive product if it contains an even number of negatives. A subarray has negative product if it contains an odd number of negatives.

Track the parity (odd/even count) of negative numbers as you traverse:

  • If parity is even at index i and was even at index j (j < i), the subarray (j+1..i) has positive product.
  • If parity is odd at index i and was even at index j, the subarray (j+1..i) has negative product.

Data structure: two hash maps (or arrays) — first occurrence of even-parity index and first occurrence of odd-parity index.

Time: O(n), Space: O(n)

Bitwise Subarray — OR / AND / XOR [algorithm:array]

Front

Can you use prefix sums for subarray problems with Bitwise OR, AND, or XOR?

Back

XOR: YES — XOR is invertible (XOR is its own inverse). XOR(i..j) = PrefixXOR[j] ^ PrefixXOR[i-1] Same hash map pattern as prefix sum.

OR / AND: NO — not invertible. You cannot "undo" an OR or AND operation.

For OR/AND, exploit the key property: as you expand a subarray, the OR/AND result can only change at most 32 times (for 32-bit integers) because bits only transition 0→1 (OR) or 1→0 (AND).

Strategy: maintain a set of all possible OR results ending at the current index. The set never exceeds size 32.

int subarrayBitwiseORs(vector<int>& arr) {
    unordered_set<int> result, current;
    for (int x : arr) {
        unordered_set<int> next;
        next.insert(x);
        for (int val : current) {
            next.insert(val | x);
        }
        current = next;
        for (int val : current) result.insert(val);
    }
    return result.size();
}

Time: O(n * 32), Space: O(32) per step

Subarray Sum — Keyword-to-Algorithm Mapping [algorithm:interview]

Front

What is the master keyword-to-algorithm mapping for subarray problems?

Back

Problem Phrase Array Property Algorithm
"Continuous subarray + Sum = K" Only positive numbers Sliding Window (O(1) space)
"Continuous subarray + Sum = K" Positive & negative Prefix Sum + Hash Map (O(n) space)
"Divisible by K" or "Multiple of X" Any numbers Prefix Remainder + Hash Map (sum % K)
"Equal number of X and Y" Any numbers Value Mapping (X→1, Y→-1) + Prefix Sum Map
"Maximum / Minimum Sum" Any numbers Kadane's Algorithm (DP)
"Subarray Sum + Frequent Updates" Element mutations Fenwick Tree / Segment Tree
"Subarray product = K" No zeros Prefix Product (division)
"Subarray product positive/negative" Any numbers Parity tracking of negative count
"Subarray XOR = K" Any numbers Prefix XOR + Hash Map
"Subarray OR / AND" Any numbers Set of results (bounded by 32 changes)

Subarray Sum — Modular Arithmetic Insight [algorithm:interview]

Front

Why does "subarray sum divisible by K" work with prefix remainders? Prove it.

Back

If Sum(i..j) mod K = 0, then: (Prefix[j] - Prefix[i-1]) mod K = 0

By modular arithmetic: Prefix[j] mod K = Prefix[i-1] mod K

Proof: Prefix[j] - Prefix[i-1] = m * K (for some integer m) Prefix[j] = Prefix[i-1] + m * K Prefix[j] mod K = (Prefix[i-1] + m * K) mod K Prefix[j] mod K = Prefix[i-1] mod K (since m*K mod K = 0)

So we just need to find pairs of indices with the same prefix remainder.

Caveat: In C++/Java, % can return negative values for negative operands. Fix: remainder = ((prefix_sum % K) + K) % K

In Python, % always returns non-negative, so no fix needed.

Subarray Sum — Prefix State Generalization [algorithm:concept]

Front

What is the "prefix state" generalization, and how does it extend beyond addition?

Back

The core philosophy of prefix sums is: accumulate history as you traverse linearly, and use a hash map to track state.

This generalizes far beyond addition:

Problem Mapping Reduces To
Equal 0s and 1s 0→-1, 1→+1 Subarray sum = 0
Equal odd/even even→+1, odd→-1 Subarray sum = 0
Equal vowels/consonants vowel→+1, consonant→-1 Subarray sum = 0
Equal A/B/C counts Track (c_A-c_B, c_B-c_C) Prefix state tuple repeats
Subarray product Prefix product Division (handle zeros)
Subarray XOR Prefix XOR XOR is invertible
Subarray sum Prefix sum Subtraction

The pattern:

  1. Define a state that accumulates as you traverse
  2. Find a way to "undo" or compare states (subtract, XOR, divide, compare tuples)
  3. Use a hash map to find when the same state (or target difference) appears
Reference in New Issue View Git Blame Copy Permalink