Finding the count of all repeats in an array of integers

Question

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;   
}

Answer 1

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;
}

Answer 2

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[0];//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
           if(sameNumCount > 0)
           {
            count++;
           }
            sameNumCount = 0; // reset same number count
         }
         else
         {
          sameNumCount++;
         }

    }

    // 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.
   if(sameNumCount > 0)
   {
      count++;
    }
  } 
    return count;   
}