0

this is the first time i've asked question on Stackoverflow and my english isn't good so if i make any mistakes please forgive me. This is a problem from leetcode and i can see the solution but i want to know what's wrong with my code. Here is the problem: Given an integer array nums, return the number of subarrays filled with 0. A subarray is a contiguous non-empty sequence of elements within an array.

This is the constraints: 1 <= nums.length <= 105 -109 <= nums[i] <= 109

Some examples: Input: nums = [1,3,0,0,2,0,0,4] Output: 6 Explanation: There are 4 occurrences of [0] as a subarray. There are 2 occurrences of [0,0] as a subarray. There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.

And here is my code:

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
       vector<int> pos;
       long long count = 0;
       for (auto i = 0; i < nums.size(); ++i) {
           if (nums[i] == 0) {
               pos.push_back(i);
               count++;
           }
       } 

        for (auto i = 0; i < pos.size(); ++i) {
            auto j = i + 1;
            while ((pos[j] - pos[j - 1]) == 1 && j < pos.size()) {
                j++;
                count++;
            }
        }

        return count;
    }
};

here is the error:
=================================================================
==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000100 at pc 0x000000345df0 bp 0x7ffc88139d90 sp 0x7ffc88139d88
READ of size 4 at 0x602000000100 thread T0
    #2 0x7f3d7e95c0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000100 is located 0 bytes to the right of 16-byte region [0x6020000000f0,0x602000000100)
allocated by thread T0 here:
    #4 0x7f3d7e95c0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8010: fa fa fd fd fa fa fd fa fa fa fd fa fa fa 00 00
=>0x0c047fff8020:[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==31==ABORTING

i have run the code and it's keep notify runtime error. Please help me fix my code. Thank you for reading my problem

I want to know what wrong with my code and how to fix it

nicole
  • 13
  • 2
  • What runtime error? More details, a failing example and debug information would help. – MrSmith42 Mar 21 '23 at 10:51
  • 1
    The solution looks suboptimal because of the nested loops. Just count the number of zeroes in each maximal contiguous subarray of zeroes. If a maximal contiguous subarray of zeroes has k zeroes, then you have: k times [0]; (k-1) times [0,0]; (k-2) times [0,0,0]; ... up to 1 time [0,0,...0]. So a maximal contiguous subarray of zeroes of length k gives you 1+2+3+...+k = k(k+1)/2 contiguous subarrays of zeroes. And you can use this formula to avoid a nested loop. – Stef Mar 21 '23 at 11:25

1 Answers1

0
      for (auto i = 0; i < pos.size(); ++i) {
            auto j = i + 1;
            while ((pos[j] - pos[j - 1]) == 1 && j < pos.size()) {
              ....

The runtime error is due to accessing beyond the array bounds.

Example:- 1 1 0 3

If the array has only one zero, pos.size() would be equal to 1 and in the first iteration of the loop you'll get a runtime error because of pos[j], here j == 1 but the size of the array is 1, you're indexing outside of the array bounds.

To fix this swap the conditional checking inside while loop.

   while (j < pos.size() && (pos[j] - pos[j - 1] == 1))

In c++, the expression is evaluated from left to right. More info

sharpnife
  • 198
  • 12