DEV Community

kevin074
kevin074

Posted on

Leetcode diary: 1561 - Maximum Number of Coins You Can Get

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

This is definitely not a medium level question. Below are my thought process immediately

    // first we have 2 cases: 
    //1.) 3n % 2 == 0
    //2.) 3n % 2 != 0 

    // given the 2 cases, we should always work backwards,
    // that is after sorting array, add from largest to smallest
    // we aren't exactly every other number since it's 3-2-1-3-2
    // our loop can run like 
    // while piles.length
    // piles.pop();
    // sum += piles.pop();
    // piles.pop();

Enter fullscreen mode Exit fullscreen mode

which gave me the code:

var maxCoins = function(piles) {    
    piles = piles.sort(function(a,b){
        return a > b ? 1 : -1;
    });
    let sum = 0;
    while(piles.length){
        piles.pop();
        sum += piles.pop();
        piles.pop();
    };

    return sum;
};
Enter fullscreen mode Exit fullscreen mode

This was simple enough! I ran with the given test case and passed. However, I failed my submission. Upon looking at the problem in detail, I noticed that the triplets does not have to be in order. It can be any 3. However, given the problem conditions, two numbers have to be the currently biggest and the third any be anything. Therefore logically it is just the smallest.

Therefore, we just shift the 3rd number instead.

That passed the submission with poor performance.

This is a submission with good performance:

var maxCoins = function(piles) {
        piles = piles.sort(function (a, b) {  return a - b;  });
        let numOfCoins = 0;
        let numOfMyPilesLeft = piles.length / 3;
        i = numOfMyPilesLeft;
        while(numOfMyPilesLeft-- > 0) 
        {
            numOfCoins += piles[i];
            i += 2;            
        }
        return numOfCoins;
};
Enter fullscreen mode Exit fullscreen mode

The lines that improved performance drastically are:
1.) piles.length/3
2.) is i+= 2

So the lesson here is that I should learn to approach the problem more mathematically rather than doing it straight out like a brute. I was kind of blocked by the fact I did not realize it should be shift for the third number though.

So the second lesson is go back to the drawing board after realizing I misunderstood the problem.

Let me know anything on your mind after reading through this, THANKS!

Oldest comments (0)