2

I am new to Two Pointer patters and in particular the Sliding Window technique. I encountered this problem on leetcode - Count Nice Subarrays. I have seen many solutions that change the array to 0's and 1's and then it becomes an entirely different question of finding the number of subarrays that sum to K. But how does one apply a Sliding Window technique without manipulating the input array?

I have found one solution with a "truly" brief explanation but what is the proof that taking the difference of the low and high bounds will give the right answer? What does the lowBound signify? Any help or explanation of the intuition used is greatly appreciated. The solution is below and the link to the solution is here: Link to Discussion page

PS: I have tried reaching out to the author of the post but haven't received any advice

  public int numberOfSubarrays(int[] nums, int k) {
    int ans = 0, indexOfLeftMostOddInWin = 0, lowBound = -1;
    for (int num : nums) {
        k -= num % 2;
        if (nums[indexOfLeftMostOddInWin] % 2 == 0) // move to the index of first odd.
            ++indexOfLeftMostOddInWin;
        if (k < 0) { // more than k odds in window, need to shrink from low bound.
            lowBound = indexOfLeftMostOddInWin; // update the low bound value.
        }
        while (k < 0) {
            k += nums[++indexOfLeftMostOddInWin] % 2; // move to the index of next odd.
        }
        if (k == 0) { // accumulated k odd numbers in window.
            ans += indexOfLeftMostOddInWin - lowBound; // update result.
        }
    }
    return ans;
}
Spindoctor
  • 434
  • 3
  • 17

1 Answers1

2

In my answer, I have mentioned few lemmas. I have proved the first three in simple manners and provided only visual representation for the last 2. I have done so to avoid complexity and also because they seem trivial.

I have changed the variable names used in the algorithm. Throughout this discussion, I have assumed that k=2.

 N: numbers array
 n: an element of N
 l: lower boundary
 f: index of the first odd number after l
 c: count of the number of sub-arrays having k odds

 1: c = 0
 2: f = 0
 3: l = 0
 4: 
 5: for n in N
 6:     k -= n % 2
 7:     if N[f] % 2 == 0: f++ 
 8:     if k < 0: l = f+1               // Found kth+1 odd starting from l, hence update l    
 9:     while k < 0: k += N[++f] % 2  // Set f to the index of next 1st odd after l        
10:     if k == 0: c += (f-l+1)    
11:
12: return c

Note: I have the changed the initial value of l to 0. This does not make any difference in the answer since I have added an extra 1 to c in step 10.

Lemma

Let r be the index of k-th odd number starting from l.

L1: We only decrement k by 1 when we encounter an odd n.

This is easy to proof from step 6. We decrease k by n%2 in each iteration.

L2: f always points to the index of 1st odd after l.

Initially, l=0. We update f in each iteration in step 7 which ensures that f points to the 1st odd index starting from l.

On updation, steps 8-9 ensure that whenever we change l to f+1. We also change f to the next odd, which becomes the first odd from the new l.

Hence, the role of f is preserved in each iteration.

L3: There can never be more than k odds in [l,i].

Initially, l=0. We keep on decrementing k as we encounter new odd numbers.

Upon arrival of k-th+1 odd at index i, k becomes -1. From step-8 and L2, we then update l to f+1.

Hence, there are now k odds in [l, i]. We again update k in step 9 to 0 to ensure the idea of k odds in [l, i] is reflected in the algorithm.

L4: Each index in [l,f] acts an starting point for a sub-array having k odds in [l,i].

Here k=2. All the indices which can act as starting point of sub-arrays having k-odds are marked with *.

* * *
l   f   r   i
E E O E O E E

L5: Each index in [r,i] acts an ending point for a sub-array having k odds in [l,i].

Here k=2. All the indices which can act as ending point of sub-arrays having k-odds are marked with '.

        ' ' '
l   f   r   i
E E O E O E E

Discussion

In the start, we look for the first odd. We keep on decrementing k as we find new odd numbers. Let k=2.

l   f   i
E E O E O

Here at iteration i, when the value of k becomes 0, we have found k odds. Now, using L4, we know all the indices in [l, f] are starting point of sub-arrays having k odds. Number of such sub-arrays = (f-l+1). This is the number added to c.

Now, either the next element can be even or odd. Suppose the next element is even.

l   f   r i
E E O E O E

Now using L5, we know all the indices in [r, i] are ending point of sub-arrays having k odds. However, we have already considered sub-arrays that have index (i-1) as their ending point in the last step. Thus, we only need to consider sub-arrays that have i as their ending point, which are again (f-l+1). We again again add this number to c.

Now, suppose the next element after this is odd.

      l f   i
E E O E O E O

All the variables here are updated according to L3 to ensure that the new sub-arrays have k odds in them. The value of k is 0 again and we add these new found sub-array to c.

Comparision

In the original algorithm, lowBound is always 1 less than the actual lower boundary. Hence, it is initialized with -1 and we set lowBound = indexOfLeftMostOddInWin whereas in the updated algorithm we set l = f+1. This also means that we do not need to add that extra 1 in the answer.

AKSingh
  • 1,535
  • 1
  • 8
  • 17