a_journey's blog

Number of subarrays with sum exactly = k.
By a_journey, history, 6 years ago, In English

Given an array a[] = {1, 1 ,1 , -1} . you have to find all the subarrays of the given array whose sum is exactly = k.

example : a[] = { 1 , 1 , 1 , -1 } and k = 1

Ans = 4 all 3 one's + range from [2,4]

There is an geeks_article for it but the explanation is not good and clear and also without proof .

Can anyone explain me how to solve this problem with some explanation !

Thanks !

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use prefix sums. Let , then the sum of a subarray in [l, r] is equal to sum[r] - sum[l - 1].

If we iterate over all possible pairs (l, r), we get a complexity of O(n2).

Fix the right boundary, if we maintain the prefix sum of the left boundary in a set, the time complexity is . Note that the possible left boundary is nondecreasing as the right boundary increases, we can handle this with two-pointers technique and thus have a complexity of O(n).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    wait...the elements may be negative.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      OK, my bad. So ignore the nondecreasing thing.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can still get $$$O(n)$$$ if we assume hash tables work in $$$O(1)$$$

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What to do if i need Positions as well. Means left and right pointers of the required subarry.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            use a map<int,vector> to store to maintain the left boundary, this mean that instead of using a count you will maintaing the indices where the prefixes sums of a value ocurred, the complexity changes to $$$O(n log n + S)$$$, where S is the numbers of pairs that sum exactly k. That shoundn't be a problem because if you need all the pairs, you should have the time to at least store all the pairs and print them.

            → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    In this case, ai isn't necessarily non-negative, so the two-pointer solution doesn't work. You could use a hash table instead of a set to achieve expected O(n) time.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes , the elements may be negative , 0 or postitive and we have to device a linear complexity.

      how to do so ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Fix the right bound and store the first r prefixes into a bucket.Then ans should be increased by bucket[k - sum[r]].If we use map the complexity will be .If we use unordered_map(only allowed in C++11 or higher versions) it will be O(n).If we use a hash table then it will be expected O(n).(Sometimes it may be even slower than !)

        → Reply
»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

A simple solution is to traverse all the subarrays and calculate their sum. If sum is equal to the required sum then increment the count of subarrays. Print final count of subarrays.

→ Reply