Find number of distinct contiguous subarrays with at most k odd elements

user_16882235 0
Viewed 3338

Given an integer array nums, find number of distinct contiguous subarrays with at most k odd elements. Two subarrays are distinct when they have at least one different element.

I was able to do it in O(n^2). But need solution for O(nlogn).

Example 1:

Input: nums = [3, 2, 3, 4], k = 1
Output: 7 
Explanation: [3], [2], [4], [3, 2], [2, 3], [3, 4], [2, 3, 4]
Note we did not count [3, 2, 3] since it has more than k odd elements.

Example 2:

Input: nums = [1, 3, 9, 5], k = 2
Output: 7
Explanation: [1], [3], [9], [5], [1, 3], [3, 9], [9, 5]

Example 3:

Input: nums = [3, 2, 3, 2], k = 1
Output: 5
Explanation: [3], [2], [3, 2], [2, 3], [2, 3, 2]
[3], [2], [3, 2] - duplicates
[3, 2, 3], [3, 2, 3, 2] - more than k odd elements

Example 4:

Input: nums = [2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12], k = 1
Output: 18
sub-array data-structures arrays algorithm
3 Answers

We can solve this in sub quadratic complexity by a two step process. First use two pointers to outline the relevant windows, which we will use to build a generalised suffix tree. We can prove that all the windows together are O(n) length by noting that each overlap will be inserted only twice. The first window is constructed by extending from the first element as far right as we can keep a valid subarray. Subsequent windows are created by (1) extending the left pointer just after the next odd element, and (2) extending the right pointer as far as we can keep a valid subarray.

Example 1:

3, 2, 3, 2
k = 1

windows: [3 2], [2 3 2]


Example 2:

1, 2, 2, 2, 3, 4, 4, 5, 5
k = 2

windows:
[1 2 2 2 3 4 4], [2 2 2 3 4 4 5], [4 4 5 5]

Build a generalised suffix tree. The count of distinct subsets will equal the sum of cumulative lengths of the suffixes stored in the tree. (By "cumulative length" I mean: for example, given suffix "abc", we would add 1 + 2 + 3, each time extending farther from the start of the suffix. Or by formula n * (n + 1) / 2)

As kcsquared noted in the comments, there's no need for a generalised suffix tree. Rather we can use a known way to "count total distinct substrings with a suffix array and the longest common prefix array, but instead of summing over n - suffix_array_elements, ...replace the n with the maximal right boundary for that index."

user_20347870

Consider an array consisting purely of odd elements.

Number of result subarrays is n*k. If k is, say, equal to n then number of subarrays is ~n*n.

So, you want to find ~n*n subarrays using O(nlogn) operations.

I doubt there is an algorithm with requested complexity.

user_8310070

If we just need to output number of subarrays then I believe it can be done using two pointer approach + sliding window in O(n) time complexity.

user_48725550
Related