Home
Algorithms to Count Subarray (Contiguous) Sum That Equals k
Tags:, , , , ,

Algorithms to Count Subarray (Contiguous) Sum That Equals k

June 8, 2019 No Comments algorithms, c / c++, coding exercise, hash

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

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

Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

This is actually very similar to Algorithms to Find Maximum Size Subarray (Contiguous) Sum That Equals k however, this task is to count the number of subarrays instead of getting the maximum length of the sub array.

Bruteforce Algorithm to Search and Sum

Bruteforce algorithm takes O(N^2) for each possible pair of subarrays. Then we need O(N) to sum them. Thus O(N^3).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

The space complexity is O(1) constant.

Bruteforce with Prefix Sum

If we keep prefix sum P[n] which equals the sum from P[1] to P[n] (index starts at one). Then the sum of the subarray [i, j] should be equal to P[j] – P[i – 1]. We need O(N) to pre-process the Prefix sum array, however, the entire algorithm complexity is dominated by bruteforcing the pairs of sub arrays O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> prefix(n, 0);
        int s = 0;
        for (int i = 0; i < n; ++ i) {
            s += nums[i];
            prefix[i] = s;
        }
        int r = 0;
        for (int i = 0; i < n; ++ i) {
            for (int j = i; j &Ylt; n; ++ j) {
                int sum = prefix[j];
                if (i > 0) sum -= prefix[i - 1];
                if (sum == k) r ++;
            }
        }
        return r;
    }
};
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> prefix(n, 0);
        int s = 0;
        for (int i = 0; i < n; ++ i) {
            s += nums[i];
            prefix[i] = s;
        }
        int r = 0;
        for (int i = 0; i < n; ++ i) {
            for (int j = i; j &Ylt; n; ++ j) {
                int sum = prefix[j];
                if (i > 0) sum -= prefix[i - 1];
                if (sum == k) r ++;
            }
        }
        return r;
    }
};

The space complexity is O(N) for allocating the prefix sum array that is linear to the size of the problem.

Bruteforce with Accumulated Sum

In fact, we can accumulate the sum without need for the prefix sum. This is O(N^2) time and O(1) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int r = 0;
        for (int i = 0; i < n; ++ i) {
            int sum = 0;
            for (int j = i; j < n; ++ j) {
                sum += nums[j];
                if (sum == k) r ++;
            }
        }
        return r;
    }
};
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int r = 0;
        for (int i = 0; i < n; ++ i) {
            int sum = 0;
            for (int j = i; j < n; ++ j) {
                sum += nums[j];
                if (sum == k) r ++;
            }
        }
        return r;
    }
};

Prefix Sum and HashTable

Based on the same principle of prefix-sum equations, we can use hash table to remember the number of the same prefix sum in the form of [sum, counter]. As we are iterating the array, we update the hash table for the accumulated sum up to the current index. And, we check if the sum-k is in the hash table, if yes, we need to increment the result by the counter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int r = 0, sum = 0;
        unordered_map<int, int> count;
        count[0] = 1;
        for (int i = 0; i < n; ++ i) {
            sum += nums[i];
            if (count.find(sum - k) != count.end()) {
                r += count[sum - k];
            }
            if (count.find(sum) == count.end()) {
                count[sum] = 1;
            } else {
                count[sum] ++;
            }
        }
        return r;
    }
};
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int r = 0, sum = 0;
        unordered_map<int, int> count;
        count[0] = 1;
        for (int i = 0; i < n; ++ i) {
            sum += nums[i];
            if (count.find(sum - k) != count.end()) {
                r += count[sum - k];
            }
            if (count.find(sum) == count.end()) {
                count[sum] = 1;
            } else {
                count[sum] ++;
            }
        }
        return r;
    }
};

The intelligent algorithm takes O(N) in both time and space. Using the same algorithm, we probably can apply it to other similar problems such as: The Contiguous Binary Array with Equal Numbers of Ones and Zeros

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
699 words
Last Post: Algorithms to Find the Missing Element in Sorted Array
Next Post: Design a Container with O(1) Add, Remove and GetRandomElement

The Permanent URL is: Algorithms to Count Subarray (Contiguous) Sum That Equals k

Related posts:

  1. WordPress Hosting Services You Can’t DIY If you happen to be using WordPress for your website, there’s no doubt that you’re...
  2. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  3. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  4. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  5. Recursive Depth First Search Algorithm to Compute the Sum of Nodes with Even-Valued Grandparent in a Binary Tree Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A...
  6. Depth First Search Algorithm to Check If Two Expression Trees are Equivalent A binary expression tree is a kind of binary tree used to represent arithmetic expressions....
  7. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...
  8. Teaching Kids Programming – High Accuracy Multiplication Algorithm (Multiply Strings) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two non-negative integers num1 and...

Leave a Reply