Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 we solve it using 1 loop with or with a better time complexity?

Any other nitpicks about my solutions are also welcome.

Below is my solution:

    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;   
}
share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

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;
}
share|improve this answer
    
Isn't the same is being done in my code? –  Anirudh Jun 26 at 10:56
1  
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 at 10:58
    
I meant that in terms of Algo complexity. It's a cleaner code though. –  Anirudh Jun 26 at 11:02
2  
@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 at 11:18
    
Seems about true @rolfl –  Anirudh Jun 26 at 11:19
add comment

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;   
}
share|improve this answer
    
Failing in most cases –  Anirudh Jun 26 at 10:17
1  
like ? give me failing cases array sample data. –  Bhushan Kawadkar Jun 26 at 10:18
    
Think you need to handle the case of the empty array, apart from it it's working after you made the edit, btw you have used Brute force. –  Anirudh Jun 26 at 10:18
    
Updated to handle empty array. –  Bhushan Kawadkar Jun 26 at 10:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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