Range Sum Query

📘 Problem Statement

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

---

🔍 Example

Example 1:

Input: nums = [1,1,1], k = 2

Output: 2

Example 2:

Input: nums = [1,2,3], k = 3

Output: 2

---

🛠️ Solution

❌ Brute Force Approach (Inefficient)

Try every possible subarray and check if its sum is k.

Code

def subarray_sum_equals_k(nums, k):
    count = 0
    for i in range(len(nums)):
        sum_ = 0
        for j in range(i, len(nums)):
            sum_ += nums[j]
            if sum_ == k:
                count += 1

⏱️ Time Complexity:

\(O(n^2)\) — not scalable for large arrays.

⚡ Optimized Approach:

🔑 Key Idea:

Let:

• nums be the input array of integers
• k be the target sum

then, prefix_sum[i] is the sum of the first i elements.

\[\large prefix\_sum[i] = \sum_{i=0}^{i}nums[i]\]

Our goal is to count the number of subarrays nums[i..j] such that:

\[\large \sum_{l=i}^{j}nums[l] = k\]

This is equivalent to finding the number of pairs (i,j) such that :

\[\large prefix\_sum[j] - prefix\_sum[i-1] = k\]

Rearranging,

\[\large prefix\_sum[j] - k =prefix\_sum[i-1]\]

This tells us, at each index j, if there exists an earlier prefix sum prefix_sum[i - 1] such that:

\[\large prefix\_sum[j] - k =prefix\_sum[i-1]\]

then the subarray from i to j sums to k.

✅ Why It Works

This approach efficiently counts all previous prefix_sum values that could start a valid subarray ending at the current index. Each valid match contributes to the total number of subarrays that sum to k.

def subarraySum(self, nums: List[int], k: int) -> int:
    # dictionary which keeps track of count of all prefix sum.
    d = {0: 1}  # Initialize with sum 0 having one count. Base case.

    subarray_count = 0
    # accumulate prefix_sum
    sum_so_far = 0
    
    for ix,num in enumerate(nums):
        #prefix sum so far
        sum_so_far += num
        
        find_prev_prefix = sum_so_far - k
        # subarray so far
        subarray_count += d.get(find_prev_prefix, 0)
        d[sum_so_far] = d.get(sum_so_far, 0) + 1

    return subarray_count

⏱️ Time & Space Complexity

Operation	Complexity
Time	\(O(n)\)
Space	\(O(n)\)