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

Example: For below array


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)))


    static boolean areAllElementsEqual(List<Integer> list) {
        if (list.size()==1)
            return true;
        if (Collections.frequency(list, list.get(0))==list.size())
            return true;
            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]

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, 2016 at 12:15
  • 1
    1 if count == 1 else (count * (count + 1) / 2) is equal to count * (count + 1) / 2
    – Giorgio
    Aug 9, 2016 at 18:04
  • right, forgot to edit.
    – xploreraj
    Aug 9, 2016 at 18:19
  • Are you looking for an algorithm that is more efficient than O(n)?
    – Giorgio
    Aug 9, 2016 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, 2016 at 5:43

2 Answers 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, 2016 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 Aug 9, 2016 at 17:21
  • 1
    (count * (count + 1) / 2) its there, see python code.
    – xploreraj
    Aug 9, 2016 at 17:48

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

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, 2016 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, 2016 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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