2

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.

  • The second solution, I think, is O(n) since both loops share the iteration count. – xploreraj Aug 9 '16 at 12:15
  • 1
    1 if count == 1 else (count * (count + 1) / 2) is equal to count * (count + 1) / 2 – Giorgio Aug 9 '16 at 18:04
  • right, forgot to edit. – xploreraj Aug 9 '16 at 18:19
  • Are you looking for an algorithm that is more efficient than O(n)? – Giorgio Aug 9 '16 at 19:51
  • Not in that sense. I was looking for any other compact or interesting way to solve it. Or even, rewriting any of above implementation. Or if its fine, than thats it. I wrote this because in some interview test, I was asked same question, and I wrote first implementation, and all but one test cases timed out. The later, I figured out the O(n). So is it efficient enough? – xploreraj Aug 10 '16 at 5:43
2

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

  • I think what you told is already given in the second solution. Even with two loops, its O(n) since inner loop increments the iteration counter for outer loop. – xploreraj Aug 9 '16 at 12:11
  • If it is a double loop then it is going to be O(n^2). The formula n(n+1/2 you are not using which you should. This will replace the second loop – user2802557 Aug 9 '16 at 17:21
  • 1
    (count * (count + 1) / 2) its there, see python code. – xploreraj Aug 9 '16 at 17:48
0

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

}

  1. 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
  • if you have problem in writing the program for the above logic – Kousei Aug 9 '16 at 18:29
  • 1
    this is wrong logic. [1,3,1] should yield 3 only. [1], [3], [1] but your process will give 4. – xploreraj Aug 9 '16 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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