Java – Finding total number of subarrays from given array of numbers with equal elements. Better approach

algorithmsjavapython

Given an array of numbers, count the total number of subarrays (consecutive elements) where all elements are equal.

Example: For below array

[1,1,3]

Ans: 4

Below are desired subarrays:

[1], [1], [3], [1,1]

So I first wrote a Java program whose efficiency is bad:

import java.util.*;


public class EqualSubarrays {

    public static void main(String[] args) {

        int count = 0;

        Integer[] arr = {1,1,3};
        List<Integer> list = new ArrayList<Integer>(Arrays.asList(arr));
        for(int i=1; i<=arr.length; i++) {
            for(int j=0; j<=arr.length-i; j++) {
                if(areAllElementsEqual(list.subList(j, j+i)))
                    count++;
            }
        }

        System.out.println(count);
    }

    static boolean areAllElementsEqual(List<Integer> list) {
        if (list.size()==1)
            return true;
        if (Collections.frequency(list, list.get(0))==list.size())
            return true;
        else
            return false;
    }

}

And then, I thought of it with more simplicity and wrote a program in Python (can be written in any language though). Here it is:

def count_equal_subarrays(nums):
    n = len(nums)
    total = 0
    i = 0
    while i < n:
        count = 1
        while i+1 < n and nums[i] == nums[i+1]:
            i += 1
            count += 1
        i += 1
        total += count * (count + 1) / 2

    return int(total)

num_arr = [1, 1, 1, 1]
print(count_equal_subarrays(num_arr))

I wanted to know if there is a more efficient method or interesting approach. If you know, please explain as well if its complicated.

Best Answer

Firstly your way of wording the question is strange, min and max are the same. This obviously just means all the elements in the subarray are the same.

Once you have an array of all elements that are the same, if this has length n then it can have n(n+1)/2 subarrays.

For example [1,1,1] can have [1],[1],[1],[1,1],[1,1],[1,1,1] and 3(3+1)/=6

So all your algorithm should be is go through the array keeping memory of what the previous element was and how many in a row of that element there has been. If it is the same again put the amount up and continue. Once it's different the amount you had you put into the n(n+1)/2 formula and add it to the total.

The whole thing then can be done in O(n), there is no need for a double loop

Related Solutions

Algorithms – Finding Longest Subsequence with Sum Less Than or Equal to a Fixed Number

Now you've fixed the post, it is rarely a good idea trying to understand an algorithm from the implementation. It is much easier to develop the algorithm and the code.

Let's start with a simple thing: Given a start position in an array, how many array elements can we add from the starting position so that the sum is not greater than t? That is, given an index 'start', find an index 'end' ≤ n, so that array [start] + array [start + 1] + ... + array [end - 1] ≤ t, and either end = n or adding array [end] would make the sum > t.

That's quite simple. Given start, we write

end = start; 
sum = 0; 
while (end < n && sum + array [end] <= t) {
    sum += array [end];
    end += 1;
}

Simple, but it can be slow. Say we have n = 1,000,000, t = 1,000,000 and all the array elements are 1 or 2, we will always add up at least half a million values, and that for a million possible values of start.

When we check the next value start+1, we know that the sum of array elements from array [start] to array [end - 1] is ≤ t, therefore since array [start] ≥ 0 we also know that the sum array [start+1] to array [end - 1] is ≤ t. And we calculate that sum in one operation by subtracting array [start] from the current sum. So to calculate "end" for each of the values of start, we use this code:

end = 0;
sum = 0;
for (start = 0; start < n; ++start) {
    while (end < n && sum + array [end] <= t) {
        sum += array [end];
        end += 1;
    }
    /* Do something with start, end, sum */
    sum -= array [start];
}

When start = 0, we do the same thing as in the first version. For larger n, we start the inner loop with a value for end that isn't too large, and the sum up to that point correctly added up. Obviously you can now easily do things like finding the largest sum, finding the sum with the largest or smallest number of elements and so on.

The execution time is O (n), because both start and end are increased by 1 exactly n times.

Given an array of number, how to calculate to a target value

The easiest way is brute force. Generate all the ways to order the numbers and apply the operators, then see if any matches the target value. This will scale very badly, but can be improved with heuristics.

Using your example, we can notice that we only need to try division when it will come out to an integer (assuming you don't mean / as truncating integer division). So when we start with 3, we don't need to try dividing by anything but 1.

Memoization could also help, but unless you're planning on a large list of targets or expensive operations it probably won't be worth it. If you do go with memoization, I would recommend thinking carefully about what you expect to repeat. If the same target can come up many times, memoizing target => (numbers, operators) would make sense. If the numbers can be repeated, you could try memoizing each operator, (operator, operands) => value. Either way, I would profile any options here before making a decision.

Also, if your language has any way to reference functions (closures, function pointers, functors) it will probably be clearest to use those for the operators. Definitely avoid string parsing or evaling expressions.

Some ruby-ish pseudocode:

numbers = [1, 2, 3, 4]
operators = [+, -, *, /]
target = 2

numbers.permutation(4).each do |p|
  operators.permutation(3).each do |o|
    x = o[0](p[0], p[1])
    x = o[1](x, p[2])
    x = o[2](x, p[3])
    if (x == target)
      return p, o
    end
  end
end

Best Answer

Related Solutions

Algorithms – Finding Longest Subsequence with Sum Less Than or Equal to a Fixed Number

Given an array of number, how to calculate to a target value

Related Topic