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

Question

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.

Answer 1

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

Answer 2

I am writing the algorithm ,you can implement in any language you want

Algorithm:Array A={1,3,1} 1. first of all sort your array i.e array A={1,1,3} 2. make a count dictionary/array of each unique element of array

Count{ 
Element   count
 1          2
 3          1

}

3. then apply formula (n*(n+1))/2 for each value of Count[element] and add all the value.that's your answer for Count[1] count is 2 so (2*(2+1))/2=3 For Count[3] count is 1 so (1*(1+1))/2=1 Adding all of them 3+1=4 reply if you have any doubt
   • If you are using a array then Find the max element of array then make a count array of that size