CODEWITHSUNDEEP
arraysalgorithm
Abdennacer Lachiheb
Abdennacer Lachiheb

Reputation: 4888

Check if all elements of a subarray of an array doesn't exist in the rest of the array

Let's say we have an array a = { ... } and we should answer some queries, each query consist of 2 indices l and r , the answer of the each query is YES or NO :

Yes : if all the elements of the subarray [l,r] doesn't exist in the rest of the array ( segment [1,l-1] and segment [r+1,n] ).

No : otherwise

The best thing I could come with is o(n^3) solution : iterating each segment (i,j) which take O(n^2) and then for each segment check all elements of that segment so it's O(n^3) overall.

I need at least O(n^2) solution or some hint, thanks.

ex : a = [4, 4, 2, 5, 2, 3] queries :

1 2 -> YES

3 5 -> YES

2 3 -> NO

4 6 -> NO

Upvotes: 0

Views: 183

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55609

Preprocessing: Loop over the array and create a hashmap counts of each element to the count of how often it appears in the array.

For each query: Loop over the subarray and create a hashmap queryCounts to store the count of each element. Look up each element of queryCounts in counts and compare the counts - return "yes" if all the counts match, "no" otherwise.

Running time: Expected O(n) preprocessing and O(n) per query.

Pseudo-code:

(Assume elements that don't exist in the map will be initialised to 0 when you try to access them, similar to C++'s std::map)

Preprocessing:

array[n] // the input array

Map<int -> int> counts
for i = 1 to n
   counts[array[i]]++

For a query i j:

Map<int -> int> queryCounts
for x = i to j
   queryCounts[array[x]]++
for each key y in queryCounts
   if queryCounts[y] != counts[y]
      return "no"
return "yes"

Example:

Array: [4, 4, 2, 5, 2, 3]

The hashmap will be:

2 -> 2
3 -> 1
4 -> 2
5 -> 1

If have a query 3 4 (1-based) over the subarray [2, 5], we'll get:

2 -> 1
5 -> 1

We compare this with the first hashmap and see that the counts for 2 don't match, so we return "no".

Alternative approach:

You can also loop over all subarrays during preprocessing and store whether you'll return "yes" or "no" to get O(n2) preprocessing and O(1) per query.

Note that the hashmap for [i,j] can be obtained from [i,j-1]'s hashmap by adding 1 to the count of array[j], thus we only need to do O(1) work per subarray during preprocessing if we keep track of the number of counts which are wrong and only check how changing array[j]'s count will change this number.

Pseudo-code:

Preprocessing:

array[n] // the input array

Map<(int, int) -> String> queryResults
for i = 1 to n
   Map<int -> int> queryCounts // clear on every i iteration
   countsWrong = 0
   for j = i to n
      if queryCounts[array[j]] == counts[array[j]]
         countsWrong++ // the counts match, the below operation will make it not match
      queryCounts[array[j]]++
      if queryCounts[array[j]] == counts[array[j]]
         countsWrong--
      if countsWrong == 0
         queryResults[i,j] = "yes"
      else
         queryResults[i,j] = "no"

For a query i j:

return queryResults[i,j]

Example:

Array: [4, 4, 2]

The hashmap will be:

2 -> 1
4 -> 2

We start with i=1, j=1:

4 -> 1
countsWrong = 1 // since 4's count is wrong (not 2)
queryResults[1,1] = "no"

For i=1, j=2, we add 1 to 4's count:

4 -> 2
countsWrong = 0 // 4's count is now right
queryResults[1,2] = "yes"

For i=1, j=3, we add 1 to 2's count:

4 -> 2
2 -> 1
countsWrong = 1 // 2's count is right
queryResults[1,3] = "yes"

For i=2, j=2, we reset the map and 1 to 4's count:

4 -> 1
countsWrong = 1 // 4's count is wrong (not 2)
queryResults[2,2] = "no"

For i=2, j=3, we add 1 to 2's count:

4 -> 1
2 -> 1
countsWrong = 1 // 2's count is right, 4's is wrong (not 2)
queryResults[2,3] = "no"

For i=3, j=3, we reset the map and 1 to 2's count:

2 -> 1
countsWrong = 0 // 2's count is right
queryResults[1,2] = "yes"

Upvotes: 2

Related Questions