subsets in array. Algorithm (No Linq)

Question

Task:

A subset is a continuous segment of an array.
Two integer arrays are given with elements from 1 to 100: of N and n (N > n).
For every subset of the first array of n length find out the next thing:
Does this subset have the same values as in the second array? Order isn't important.
The method should return bool[]. For clarity, the length of a returning array is equal to the number of subsets.

Main attention to the IsSubArray method

Examples:
in the next examples false - f, true - t

Second array: 4 2 3 First array: 1 2 3 4 5 4 3 2 return array: f t f f f t 

Second array: 1 2 3 5 1 7 6 5 7 1 First array: 6 5 7 1 return array: f f f t t f t 

What have I tried

I've tried to solve this task in different ways and this is the fastest. In this use the second for cycle to initialize the current subset and the third for cycle to remove the same values. I did it with help of List<int> data type.

My question

Is there another faster way to perform this task? Maybe any other ways to write for cycles or use another check instead of currentSubArray.Remove

Code

using System; using System.Collections.Generic; using System.Text; using System.Linq; using ClassLibrary1; namespace ConsoleApp1 { class Program { static void Main(string[] args) { bool err = false; int[] firstArray = {1, 2, 3, 4, 5, 6, 7, 4, 8, 9, 10, 6, 4, 5, 7}; int[] secondArray = { 7, 5, 4, 6 }; bool[] expect = { false, false, false, true, true, false, false, false, false, false, false, true }; var actual = IsSubArray(firstArray, secondArray); Console.Write("Actual Elements : "); Print(actual); Console.Write("Expect Elements : "); Print(expect); Console.ReadKey(); } static void Print(bool[] array) { foreach (var e in array) Console.Write("{0}, ", e); Console.Write("\n"); } internal static bool[] IsSubArray(int[] firstArray, int[] secondArray) { bool[] isSubArray = new bool[firstArray.Length - secondArray.Length + 1]; for (int i = 0; i + secondArray.Length <= firstArray.Length; i++) { var currentSubArray = new List<int>(); for (int j = 0; j < secondArray.Length; j++) { currentSubArray.Add(firstArray[i + j]); } for (int k = 0; k < secondArray.Length; k++) { if (!currentSubArray.Contains(secondArray[k])) { isSubArray[i] = false; break; } else currentSubArray.Remove(secondArray[k]); } if (currentSubArray.Count == 0) { isSubArray[i] = true; } } return isSubArray; } } } 

Answer 1

Is there another faster way to perform this task? Maybe any other ways to write for cycles or use another check instead of currentSubArray.Remove

There are alternatives. How well they do, relative to your current implementation, depends on how annoying the test cases are. The subarray could be large, making a Contains check on a list and subsequent Remove both quite bad. They're fine for small sub arrays though, so this implementation is not necessarily always slow, it's just that it can become slow in some circumstances.

First let me draw your attention to part of the exercise:

with elements from 1 to 100

A range of 1 to 100 is tiny, and with this type of exercise you should usually assume that any limits are chosen deliberately, and are effectively a hint for solutions. Sometimes they may be a red herring, but usually they work as a hint.

What that hint suggests to me, is to build a histogram of how often each value between 1 and 100 occurs in the subarray of both the first array and the second array, then compare whether the histograms are equal (this is not great for tiny subarrays since this comparison is a loop over an array of 100 items, but it's always 100 items, never more).

Bonus: you do not need to create two new histograms for every iteration of the outer loop. You can take both of the existing histograms, decrement the entry of the "leaving value" and increment the entry of the "entering value". That is similar to how rolling hashes work, but there is no hash, it's a histogram. You could actually use a rolling hash as well (an intentionally "poor hash", that is immune to reordering of the values), and avoid always comparing the entire histograms.