0
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Welcome to CODE REVIEW. Where did you encounter this problem? different ways and this is the fastest How does it differ from the one most readable? How did you test? \$\endgroup\$
    – greybeard
    Commented Nov 27, 2022 at 7:30
  • \$\begingroup\$ @greybeard, edited. Yes, integer. "Where did you encounter this problem? " This is the task from the online free course. This task is from the collection section. So I should use arrays and collections to solve it. It can be a string or stringBuilder too in theory but I don't believe they will be fast. "How does it differ from the one most readable?" My past variants weren't more readable. They were just slower. "How did you test?" the time check is arrays of 1000 length and of 100 length and repeated the test 1000 times. And then it's compared with their time limit. \$\endgroup\$
    – Sheeba334
    Commented Nov 27, 2022 at 7:58
  • \$\begingroup\$ Is it some sort of coding challenge? If so, could you please link it? \$\endgroup\$ Commented Nov 28, 2022 at 8:41
  • \$\begingroup\$ @PeterCsala, as I said before, it's a task from the online free course. This task is placed after the collections section. But in theory, it can be solved with arrays. what does challenge mean here in code review? \$\endgroup\$
    – Sheeba334
    Commented Nov 28, 2022 at 11:05
  • \$\begingroup\$ @Sheeba334 Please see this tag: programming-challenge \$\endgroup\$ Commented Nov 28, 2022 at 11:07

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ So I need to make a cycle for with 100 iterations. And what is next? In what data type do I need to store histograms? I've never used histograms in this way. should I use int[] or Dictionary? never worked with it this way, so I can't imagine how to do this. Can you clarify some more information? \$\endgroup\$
    – Sheeba334
    Commented Nov 27, 2022 at 6:00
  • \$\begingroup\$ @Sheeba334 int[] and Dictionary<int, int> are both good options, but a bit different - int[] has less overhead when the subarrays are long and contain many different values, but Dictionary<int, int> may be better when subarrays are not that long or if they contain many entries of the same value (since that would let it stay small) \$\endgroup\$
    – user555045
    Commented Nov 27, 2022 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.