Given an array consisting of 1s and 0s and an integer k find the number of alternating sequences of size k in the array. Treat the array as circular meaning the last index of the array follows onto the first index. Example:

array = [1,0,1,0,1,1], k = 4
solution_set = {1010, 0101}
result = 2

array = [1,0,1,0], k = 3
solution_set = {101, 010, 101(starting at 3rd index), 010(starting at 4th index}
result = 4

I did not get the answer fast enough, and had an unnecessarily complicated algorithm does anyone have a good way of doing this. Not even sure if dp is the best way of doing this.

CodePudding user response：

I think you can use a two pointer approach. Basically just shift the second pointer until arr[j] == arr[j-1]. At that point you can determine how many alternating arrays of size k would have occurred in that window by calculating max(j - i - k 1, 0). Then shift the pointers over. Here is an example in Python:

In [65]: def solution(arr, k):
    ...:     ret = []
    ...:     i = 0
    ...:     j = 1
    ...:     num_found = 0
    ...:     # Keep going until either the first pointer rolls over or the second pointer goes too far
    ...:     while j < len(arr)   k and i < len(arr):
    ...:         temp_j = j
    ...:         temp_end = temp_j % len(arr)  # Modular division to allow "circular"
    ...:         # Keep going until there are two consecutive numbers in a row.
    ...:         # Make sure temp_j doesn't go too far.
    ...:         while arr[temp_end] != arr[temp_end - 1] and (temp_j < (len(arr)   k - 1)):
    ...:             temp_j  = 1
    ...:             temp_end = temp_j % len(arr)
    ...:
    ...:         # Calculate the number of arrays of length k that would be there and shift the pointers
    ...:         num_found  = max(temp_j - i - k   1, 0)
    ...:         i = temp_j
    ...:         j = i   1
    ...:
    ...:     return num_found
    ...:

In [66]: solution([1,0,1,0,1,1], 4)
Out[66]: 2

In [67]: solution([1,0,1,0], 3)
Out[67]: 4