# Finding the count of all repeats in an array of integers

The problem is about finding the sum of all repeating groups from an integer array as explained below and here.

Problem statement:

Say that a "clump" in an array is a series of 2 or more adjacent elements of the same value. Return the number of clumps in the given array.

countClumps({1, 2, 2, 3, 4, 4}) → 2
countClumps({1, 1, 2, 1, 1}) → 2
countClumps({1, 1, 1, 1, 1}) → 1


Conditions for solving:

1. No other helper methods.
2. Do not use Java.util.Arrays.copyOf or any other utility under Arrays
3. Do not use collections.

Can I solve it using 1 loop with or with a better time complexity?

Any other nitpicks about my solutions are also welcome.

public int countClumps(int[] nums) {
final int len=nums.length;
int  count=0;

for(int i=0;i<len;i++)
{
int j=i+1;
if(nums[i]==nums[j])
{
count++;
while((nums[i]==nums[j]))
{
if(j==len-1)
break;
j++;
}
}
i=j-1;
if(i==len-2)
break;
}

return count;
}


Your code has a for-loop with a nested while-loop. Typically this would indicate an $O(n^2)$ time complexity for your solution.... but, your code is only actually $O(n)$... how does that happen?

Because you do for-loop control variable manipulation outside the for-loop control block. This is a bad practice. A for loop has three control statements: for (initializer, terminator, stepper). A for loop is designed to have those three mechanisms in one place. In your code, you have split the logic of the stepper in to two places, which makes the for-loop hard to read, and unconventional. Your i variable is stepped, and also you have i=j-1; later in your loop.

If you cannot implement a clean for-loop structure because your code demands some other mechanism, then you should instead use a while-loop, or find a different way to express your step-process.

Bhushan has provided an answer which solves the problem, but does not implement a clean break-processing loop. His code implements the logic check when leaving a clump, rather than when entering the clump. If you do the check when the clump starts, the logic becomes much simpler:

public int countClumps(int[] nums) {
boolean inclump = false;
int clumpcnt = 0;
// note the start-from-1 loop
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
// we are in a clump
if (!inclump) {
// this is the first time for this clump.
inclump = true;
clumpcnt++;
}
} else {
inclump = false;
}
}
return clumpcnt;
}

• Isn't the same is being done in my code? – Anirudh Jun 26 '14 at 10:56
• No, OP has two nested loops. This answer performs with one loop and cleaner logic that is easier to follow. Both algorithms perform in $\mathcal{O}(n)$ time complexity. – Emily L. Jun 26 '14 at 10:58
• I meant that in terms of Algo complexity. It's a cleaner code though. – Anirudh Jun 26 '14 at 11:02
• @Anirudh - yes, both have same O(n) complexity, but yours is 'confused' by having the inner while-llop and then the 'skip' afterwards. Most people (including me) look at a nested loop like you have, and assume $O(n^2)$ simply because of the nesting. It is not usual to modify the for-loop variable (i) outside the for-loop control block, like you have done (i=j-1;), which makes the actual complexity hard-to-see. – rolfl Jun 26 '14 at 11:18
• Seems about true @rolfl – Anirudh Jun 26 '14 at 11:19

You can do the same with single loop. see below code :

public int countClumps(int[] nums) {
int  count=0;
if(null!=nums && nums.length > 0)
{
final int len=nums.length;

int currentInt = nums;//this is to store current element in loop, default is first value
int sameNumCount = 0; // this is to store count of same number found consecutely
for(int i=1;i<len;i++)
{
if(currentInt!=nums[i])
{
currentInt = nums[i];
// increment count if same number count is greater than 0
{
count++;
}
sameNumCount = 0; // reset same number count
}
else
{
}

}

// to handle last same number count
// e.g - for countClumps({1, 2, 2, 3, 4, 4}), for last 4 loop will go into
// else part and count will not get increased.