[AlgoMastery]
Topics›Array›Subarray Problems
📖

Subarray Problems

Array
~20 min read
5 practice problems

Overview

Subarray Problems involve finding contiguous subarrays (slices) of an array that satisfy specific conditions. Unlike subsequences, subarrays must be contiguous, making them ideal for techniques like sliding window, prefix sum, and Kadane's algorithm.

Subarray problems typically ask for:

  • Maximum/minimum sum subarray
  • Subarrays with specific sum/product
  • Longest/shortest subarray with property
  • Count of subarrays satisfying condition
  • Subarray with specific elements

Subarray problems are particularly useful for:

  • Range queries
  • Optimization problems
  • Pattern matching
  • Constraint satisfaction
  • Dynamic programming

Pattern 1: Maximum Sum Subarray (Kadane)

Find contiguous subarray with maximum sum.

function maxSubArray(nums: number[]): number {
  let maxSum = nums[0];
  let currentSum = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  
  return maxSum;
}

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

With indices:

function maxSubArrayWithIndices(nums: number[]): [number, number, number] {
  let maxSum = nums[0];
  let currentSum = nums[0];
  let start = 0, end = 0, tempStart = 0;
  
  for (let i = 1; i < nums.length; i++) {
    if (currentSum < 0) {
      currentSum = nums[i];
      tempStart = i;
    } else {
      currentSum += nums[i];
    }
    
    if (currentSum > maxSum) {
      maxSum = currentSum;
      start = tempStart;
      end = i;
    }
  }
  
  return [maxSum, start, end];
}

Pattern 2: Subarray Sum Equals K

Count subarrays with sum exactly K.

function subarraySum(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, 1); // Empty subarray
  
  let sum = 0;
  let count = 0;
  
  for (const num of nums) {
    sum += num;
    
    if (prefixSum.has(sum - k)) {
      count += prefixSum.get(sum - k)!;
    }
    
    prefixSum.set(sum, (prefixSum.get(sum) || 0) + 1);
  }
  
  return count;
}

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

Explanation: If prefix sum at i is S and we've seen prefix sum S - k before, subarray between has sum k.

Pattern 3: Maximum Size Subarray Sum Equals K

Find maximum length subarray with sum K.

function maxSubArrayLen(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, -1);
  
  let sum = 0;
  let maxLen = 0;
  
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    
    if (prefixSum.has(sum - k)) {
      maxLen = Math.max(maxLen, i - prefixSum.get(sum - k)!);
    }
    
    if (!prefixSum.has(sum)) {
      prefixSum.set(sum, i);
    }
  }
  
  return maxLen;
}

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

Pattern 4: Minimum Size Subarray Sum

Find minimum length subarray with sum >= target.

function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0;
  let sum = 0;
  let minLen = Infinity;
  
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  
  return minLen === Infinity ? 0 : minLen;
}

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

Sliding window approach.

Pattern 5: Subarray Product Less Than K

Count subarrays with product less than K.

function numSubarrayProductLessThanK(nums: number[], k: number): number {
  if (k <= 1) return 0;
  
  let left = 0;
  let product = 1;
  let count = 0;
  
  for (let right = 0; right < nums.length; right++) {
    product *= nums[right];
    
    while (product >= k) {
      product /= nums[left];
      left++;
    }
    
    // All subarrays ending at right are valid
    count += right - left + 1;
  }
  
  return count;
}

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

Key insight: If product from left to right < k, all subarrays ending at right are valid.

Pattern 6: Longest Subarray with At Most K Distinct Elements

Find longest subarray with at most K distinct elements.

function longestSubarrayKDistinct(nums: number[], k: number): number {
  const freq = new Map<number, number>();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < nums.length; right++) {
    freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
    
    while (freq.size > k) {
      freq.set(nums[left], freq.get(nums[left])! - 1);
      if (freq.get(nums[left]) === 0) {
        freq.delete(nums[left]);
      }
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

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

Pattern 7: Subarray with Bounded Maximum

Count subarrays where max element is in range [left, right].

function numSubarrayBoundedMax(nums: number[], left: number, right: number): number {
  return countSubarrays(nums, right) - countSubarrays(nums, left - 1);
}

function countSubarrays(nums: number[], bound: number): number {
  let count = 0;
  let current = 0;
  
  for (const num of nums) {
    if (num <= bound) {
      current++;
    } else {
      current = 0;
    }
    count += current;
  }
  
  return count;
}

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

Explanation: Count subarrays with max <= right, subtract those with max < left.

Pattern 8: Maximum Average Subarray

Find subarray of length K with maximum average.

function findMaxAverage(nums: number[], k: number): number {
  let windowSum = 0;
  
  // Initialize window
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
  
  let maxSum = windowSum;
  
  // Slide window
  for (let i = k; i < nums.length; i++) {
    windowSum = windowSum - nums[i - k] + nums[i];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum / k;
}

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

Fixed-size sliding window.

Pattern 9: Count Subarrays with Sum Divisible by K

Count subarrays with sum divisible by K.

function subarraysDivByK(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, 1);
  
  let sum = 0;
  let count = 0;
  
  for (const num of nums) {
    sum += num;
    const remainder = ((sum % k) + k) % k; // Handle negative
    
    if (prefixSum.has(remainder)) {
      count += prefixSum.get(remainder)!;
    }
    
    prefixSum.set(remainder, (prefixSum.get(remainder) || 0) + 1);
  }
  
  return count;
}

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

Key insight: Two prefix sums with same remainder mod K have difference divisible by K.

Pattern 10: Longest Subarray with Same Elements After K Replacements

Find longest subarray where you can replace at most K elements to make all same.

function longestSubarray(nums: number[], k: number): number {
  const freq = new Map<number, number>();
  let left = 0;
  let maxFreq = 0;
  let maxLen = 0;
  
  for (let right = 0; right < nums.length; right++) {
    freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
    maxFreq = Math.max(maxFreq, freq.get(nums[right])!);
    
    // Shrink if replacements needed > k
    while ((right - left + 1) - maxFreq > k) {
      freq.set(nums[left], freq.get(nums[left])! - 1);
      left++;
      // Recalculate maxFreq (simplified - may need optimization)
      maxFreq = Math.max(...Array.from(freq.values()));
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

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

Optimized: Track max frequency efficiently.

Pattern 11: Maximum Sum of Two Non-Overlapping Subarrays

Find maximum sum of two non-overlapping subarrays of given lengths.

function maxSumTwoNoOverlap(nums: number[], firstLen: number, secondLen: number): number {
  const prefix = buildPrefixSum(nums);
  const n = nums.length;
  
  // Precompute max subarray sum ending at each position
  const maxFirst = new Array(n).fill(0);
  const maxSecond = new Array(n).fill(0);
  
  // Max firstLen subarray ending at i
  for (let i = firstLen - 1; i < n; i++) {
    const sum = prefix[i + 1] - prefix[i - firstLen + 1];
    maxFirst[i] = Math.max(i > 0 ? maxFirst[i - 1] : 0, sum);
  }
  
  // Max secondLen subarray ending at i
  for (let i = secondLen - 1; i < n; i++) {
    const sum = prefix[i + 1] - prefix[i - secondLen + 1];
    maxSecond[i] = Math.max(i > 0 ? maxSecond[i - 1] : 0, sum);
  }
  
  let maxSum = 0;
  
  // Try firstLen before secondLen
  for (let i = firstLen - 1; i < n - secondLen; i++) {
    const firstSum = prefix[i + 1] - prefix[i - firstLen + 1];
    const secondSum = maxSecond[n - 1] - (i >= secondLen - 1 ? maxSecond[i] : 0);
    maxSum = Math.max(maxSum, firstSum + secondSum);
  }
  
  // Try secondLen before firstLen
  for (let i = secondLen - 1; i < n - firstLen; i++) {
    const secondSum = prefix[i + 1] - prefix[i - secondLen + 1];
    const firstSum = maxFirst[n - 1] - (i >= firstLen - 1 ? maxFirst[i] : 0);
    maxSum = Math.max(maxSum, firstSum + secondSum);
  }
  
  return maxSum;
}

function buildPrefixSum(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  return prefix;
}

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

Pattern 12: Subarray with Maximum Absolute Sum

Find subarray with maximum absolute sum.

function maxAbsoluteSum(nums: number[]): number {
  let maxPositive = 0;
  let minNegative = 0;
  let prefixSum = 0;
  
  for (const num of nums) {
    prefixSum += num;
    maxPositive = Math.max(maxPositive, prefixSum);
    minNegative = Math.min(minNegative, prefixSum);
  }
  
  return maxPositive - minNegative;
}

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

Explanation: Maximum absolute sum = max prefix sum - min prefix sum.

When to Use Subarray Techniques

Use subarray techniques when:

  • Problem asks for contiguous subarray
  • Need maximum/minimum sum subarray
  • Count subarrays with property
  • Longest/shortest subarray satisfying condition
  • Range queries on subarrays
  • Sliding window applicable

Key distinction: Subarray = contiguous, Subsequence = non-contiguous.

Template (Prefix Sum + Hash Map)

function subarraySumTemplate(nums: number[], target: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, 1);
  
  let sum = 0;
  let count = 0;
  
  for (const num of nums) {
    sum += num;
    
    if (prefixSum.has(sum - target)) {
      count += prefixSum.get(sum - target)!;
    }
    
    prefixSum.set(sum, (prefixSum.get(sum) || 0) + 1);
  }
  
  return count;
}

Template (Sliding Window)

function slidingWindowTemplate(nums: number[], condition: number): number {
  let left = 0;
  let windowSum = 0;
  let result = 0;
  
  for (let right = 0; right < nums.length; right++) {
    windowSum += nums[right];
    
    while (/* window invalid */) {
      windowSum -= nums[left];
      left++;
    }
    
    // Update result (window is valid)
    result = Math.max(result, right - left + 1);
  }
  
  return result;
}

Time and Space Complexity Summary

  • Kadane's algorithm: O(n) time, O(1) space
  • Subarray sum count: O(n) time, O(n) space
  • Sliding window: O(n) time, O(1) or O(k) space
  • Prefix sum queries: O(n) preprocessing, O(1) query
  • Two non-overlapping: O(n) time, O(n) space

Practice Tips

  1. Identify technique - Kadane, sliding window, or prefix sum?
  2. Contiguous vs non-contiguous - Subarray vs subsequence
  3. Hash map for counting - Track prefix sum frequencies
  4. Two pointers - For sliding window problems
  5. Edge cases - Empty array, all negative, single element

Common Mistakes

  1. Confusing subarray with subsequence - Subarray must be contiguous
  2. Wrong prefix sum initialization - Forgetting prefixSum[0] = 1
  3. Index errors - Off-by-one in sliding window
  4. Not handling negatives - In mod arithmetic or prefix sums
  5. Overlapping subarrays - Not checking non-overlap condition

Related Concepts

  • Kadane's Algorithm - For maximum sum subarray
  • Sliding Window - For fixed/variable size windows
  • Prefix Sum - For range sum queries
  • Two Pointers - For window management
  • Hash Map - For counting subarrays

Subarray problems are fundamental in array algorithms. Master these patterns, and you'll efficiently solve a wide range of contiguous subarray problems in coding interviews.

← PreviousMerge IntervalsNext →Array Sorting