C# get index method implementation

private List<int> GetIndicesForGivenBound(int[] targetArray, int bound)
        {
            //Assume array exist and length > 0.
            //It returns the indices, a valid return index must point to the first cluster element and the sum of cluster of 4 array values <=bound
            List<int> outputlist = new List<int> ();
            int total = 0;

            for (int i = 0; i <= targetArray.Length - 4; i++)
            {
                for (int j = i; j <= i + 4 && j < targetArray.Length; j++)
                {
                    total += targetArray[j];
                    if (total > bound)
                        break;
                    if (j == i + 3) //all four numbers are added
                    {
                        outputlist.Add(i);
                        i += 3; //skip the items included in the current cluster
                    }
                }
                total = 0;
            }
            return outputlist;
        }

Select allOpen in new window

Almost there. This code(line 18) is skipping the found cluster numbers, we still have to identify if we have intersecting clusters like:
4,2,3,2,6,1,5
we have two clusters:
4,2,3,2 and 3,2,6,1
Thanks
Note: One inefficient way to adress this could be to remove line 18, but it will make a discredit to your posted code as your idea to skip processed items make a lot of sense

Requirement is yours. I just provided the outline. You can remove line 18, if you want overlapping clusters. This was there in my mind when I wrote this line, but forgot to mention in the post.

-Harish

Any ideas on how to skip overlapping clusters?  Sliding window approach?

Hello,

Considering the example in your previous comment, if your target array is 4,2,3,2,6,1,5 and bound is 12, there are two clusters 4,2,3,2 and 3,2,6,1 which adds upto <12. But they are overlapping (intersecting) in the sense the first 2 elements of second cluster (3,2) are the last two elements of first cluster. So there are two scenarios here:

1. If your requirement is to skip the elements included in one cluster while identifying the second cluster, you could keep line 18 in my code:
i += 3; //skip the items included in the current cluster

In this case, you will get only one cluster (4,2,3,2).

2. If your requirement is to include overlapping (intersecting) clusters, you can remove line 18, and you will get 2 clusters (4,2,3,2 and 3,2,6,1).

Or do you mean any scenario other than the above two (first cluster always start at first position, second cluster at 5th and so on) scenarios?

-Harish

I mean how to avoid recalculating the sums all over again in the case of overlapping (intersecting) clusters, in the example 4,2,3,2 and 3,2,6,1). you already added 3+2, thus no need to recalculate this sum. One suggestion will be to reverse the second loop(j).
Note:Array sizes are around 100 to 10000s and there will be a lot of sums that do not need repetition not only in this scenario but during normal scan as well, but I only need the scenario above, the other I can do it easily based on your solution.