Search code examples
arrayscmemory-management

Memory limit exceeding in sub array problem

I'm trying to solve a problem, but I'm exceeding the memory limit.

Problem Description

Given an integer array A and two integers B and C.

You need to find the number of subarrays in which the number of occurrences of B is equal to number of occurrences of C.

NOTE: Don't count empty subarrays.

Input Format First argument is an integer array A.

Second argument is an integer B.

Third argument is an integer C.

Output Format Return an integer denoting the number of subarrays in which the number of occurrences of B is equal to number of occurrences of C.

/**
 * @input A : Integer array
 * @input n1 : Integer array's ( A ) length
 * @input B : Integer
 * @input C : Integer
 * 
 * @Output Integer
 */
int SubArrays(int* arr, int start, int end, int size, int B, int C)
{
   
    int countB = 0,countC = 0;
    // Stop if we have reached the end of the array
    if (end == size)
        return 0;
    
    // Increment the end point and start from 0
    else if (start > end)
        SubArrays(arr, 0, end + 1, size, B, C);
   
    // Print the subarray and increment the starting point
    else {
        int A[end-start+1];
        int i, j;
        for ( i = start; i < end; i++){
            for(j =0; j<(end-start+1);j++){
                A[j] = arr[i];
            }
        }
        for(j =0; j<(end-start+1);j++){
            if(A[j]==B) countB ++;
            if(A[j]==C) countC ++;
        }
        // cout << arr[end] << "]" << endl;
        SubArrays(arr, start + 1, end, size, B, C);
    }
    if(countB == countC)
        return 1;
    else
        return 0;
}
int solve(int* A, int n1, int B, int C) {
    int count = 0;
    count = count + SubArrays(A,0,0,n1,B,C);
    return count;
}
Solution

  • In the general case, your routine creates an array int A[end-start+1] and then calls itself recursively. This uses a lot of space, and there is no need for it.

    Many of the challenge or online judge problems are intended to be solved creatively, using a “greater” view of the problem and not “brute force” such as examining all possible combinations.

    In this case, a solution is:

    • Create an auxiliary array T and set each element Ti to the number of times that B appears in the elements of A from A0 to Ai minus the number of times that C appears in the elements of A from A0 to Ai, inclusive. For example, with B = 3 and C = 4 and A as shown below:
    i 0 1 2 3 4 5 6 7 8
    A 1 3 3 5 4 0 4 4 4
    T 0 +1 +2 +2 +1 +1 0 −1 −2
    • Then use T to find subarrays. For any i and j such that Ti = Tj, the subarray of A from Ai to Aj, inclusive, will contain equal numbers of B values and C values.
    • You can count these by simply iterating through all i and j values in bounds with i ≤ j.

    For example, with the above, (0, 6) (meaning i=0, j=6) forms a subarray with equal numbers of B values and C values, and so do (1, 4), (1, 5), (2, 3), and (4, 5). So the desired number of subarrays is 5.

    (If it modifying the original array is allowed, this auxiliary information can be computed in-place in the array, replacing its original contents.)

    That will give you a solution that takes time roughly proportional to n2, where n is the number of elements in A. However, there is a better solution:

    • Sort T. This puts all identical values together. Then you can iterate through T and easily count how many times each value occurs. For a value that occurs m times, m•(m−1)/2 pairs of i and j values can be formed from it, so add m•(m−1)/2 to a running total. At the end of iterating through T, the total is the desired number of subarrays.

    That gives you an solution with a running time roughly proportional to n log n.

    It can be implemented in one function with seven lines of C code (taking advantage of some C notations that an experienced programmer might use, but reasonable) and an auxiliary function (for the sort comparison) that is one or two lines.

    Hint for counting the pairs: You do not need to wait until the end of a sequence of repetitions to add to the running total. If the current value in T has been seen m times so far, add m−1 to the running total. When the value has been seen m times, m•(m−1) will have been added for them. For example, if a value is seen four times, we will add 0 the first time it is seen, then 1, then 2, then 3, and 1+2+3 = 4•(4−1)/2.