In my effort to develop into an Engineer companies want on their engineering team, one of the areas I am devoting time and effort to is improving my problem-solving skills (algorithms). Contrary to the popular belief, algorithms are still very much relevant in the world today and while I am a proponent of it not being a true interview measure of a successful hire or candidate, I believe having good knowledge of solving problems efficiently is an investment an engineer/developer should make.

So here's my first entry of the year.

Domain problem: find the maximum consecutive ones in an array.

If you'd like to jump straight to the solution, please click here

Before I dive into the implementation, let's get a good scenario where you might need to solve such a problem at work.

Say you're working in an ed-tech company and you're working on a feature to display the total amount of fees paid per monthly payment mode sorted based on a student's 4 years study; i.e, your return value is the total amount of the year with the highest monthly payment mode. For example, say a student's payment history is stored in the database like this

[{
id:1,
payment_type:'monthly',
success:true,
amount: 1234567.89
//...et.c
{
id:2,
payment_type:'weekly',
success:true,
amount: 24681012.89
//...et.c
}
}]

Now imagine a student in their final year who has used monthly payment mode 80% of the time (say 100,000 db records). You also can't expect that the data being returned is going to be sorted based on the year the payment was made. How could you write an algorithm that does the job efficiently? That's what we'd be solving.

I challenge you to try this out after completely reading and understanding my solution to the domain problem.

solution

• Define a variable to store the count of 1s found
• Define another variable to hold the max of 1s found (this is needed as encountering a value apart from 1 would need count to be reinitialized. If we don't have a variable to hold the maximum value of the previous 1, our algorithm would be reporting false positives).
• Loop through the records, if the current value is 1, increment count by 1.
• If the current value is not 1, store the maximum value between count and max in max; initialize count back to 0;

Bonus (performance improvement)

• if the current value of max is greater than or equal to the length of our input data divided by 2. Return max as no further step is needed because the total length of items left is lesser than or equal to max.

CODE

Javascript

const maxNoOfConsecutiveOnes = (arr) => {
  let count = 0;
  let max = 0;
  const halfLength = arr.length  / 2;

  for (let value of arr) {
    if (value === 1) {
      count++;
    } else {
      max = Math.max(count, max);
      if (max >= halfLength) {
        return max;
      }
      count = 0;
    }
  }

  return Math.max(count, max);
};

JAVA

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int max = 0;
        int halfLength = nums.length / 2;

        for(int i: nums) {
            if(i == 1){
                count++;
            }else {
               max = Math.max(count,max);
                if(max >= halfLength ){
                    return max;
                }
                count = 0;
            }
        }

        return Math.max(count,max);
    }
}

Conclusion

We've seen how to implement an algorithm to return the maximum consecutive ones found in a given array of input. The time taken for this algorithm to run is given by O(n). This is more efficient than nesting loops.

Over to you young padawan, can you write an algorithm to solve the case scenario I describe? It's quite trickier than this solution but it follows the same concepts. I'd be in the comment section reading. Did you notice a mistake? Is there something I could improve on? Please do not hesitate to let me know in the comments too.

Cheers to learning and growing into world-class engineers.