The problem I am trying to solve is this. Apples fall at various offsets relative to an apple tree at position a, and oranges fall at various given offsets relative to an orange tree at position b. How many of each kind of fruit lie between positions s and t?

I pass 8 from the 11 test cases, I fail 3 tests due to timeout error.

I spent the last hour or so trying to refactor my code to make it faster but I am out of ideas now. Can someone give an advice what should I do in order to make it faster?

function countApplesAndOranges(s, t, a, b, apples, oranges) {
    let house = [];
    let applesCount = 0;
    let orangesCount = 0;
    for(let i = s; i <= t; i++){
        house.push(i);
    };
    const applesPositions = apples.map(val=> val + a);
    const orangesPositions = oranges.map(val=> val + b);

    for(let j = 0; j < house.length; j++){
        for(let k = 0; k < applesPositions.length; k++){
            if(house[j] === applesPositions[k]) applesCount++;
        };
        for(let m = 0; m < orangesPositions.length; m++){
            if(house[j] === orangesPositions[m]) orangesCount++;
        };
    };
    console.log(`${applesCount}${'\n'}${orangesCount}`);

};
up vote 3 down vote accepted

Just a few if statements will do.

Your answer to the problem is rather strange.

To find out if an apple or orange is between s and t is just a simple if statement.

if(apple[index] + appleTreePos >= s && apple[index] + appleTreePos <= t){ 
    // Apple is on the house.

// Same for the orange.

So you only need to loop over the apples and oranges once. Best is to have a single loop that does both the apples and oranges at the same time, then a second loop to do the remaining (if any) fruit.

There is no need to create any arrays. Your solutions is exponentially lots more work than is needed. For speed aim to reduce the number of times your code loops. Note that Array.map is the same as doing a for loop over each item, but much slower in this case.

NOTE I struck out exponentially and added "lots" as some have complained, I used it in the common vernacular (increasing rate of change) and not as in CS time complexity.

Your code loops over the length of the house, then the number of apples and oranges, and then you loop the length of the house times the number of apples plus oranges.

If the house is 5 units wide and there are 5 of each fruit you iterate over them a total of (house pos to array) 5 + (map each fruit array) 5 + 5, (counting) 5 * (5 + 5) for a total of 65 iterations. This is 60 times too many.

Example

I have not run this code so there could be a few typos, but the general structure is as described above.

This is faster than your solution, If it is fast enough to pass the test I do not know.

function countApplesAndOranges(houseLeft, houseRight, appleTreePos, orangeTreePos, apples, oranges) {
    var appleCount = 0;
    var orangeCount = 0;
    var i = 0;

    // find smallest group
    const len = Math.min(apples.length, oranges.length);

    // do apples and oranges
    while (i < len) {
        let pos = apples[i] + appleTreePos;
        appleCount += pos >= houseLeft && pos <= houseRight ? 1 : 0;
        pos = oranges[i++] + orangeTreePos;
        orangeCount += pos >= houseLeft && pos <= houseRight ? 1 : 0;
    }

    // if same number of fallen then return result
    if (apples.length === oranges.length) {
        console.log(`${appleCount}${'\n'}${orangeCount}`);
        return;
    }

    // if more apples have fallen the do remaining apples 
    if (apples.length > len) {
        while (i < apples.length) {
            const pos = apples[i++] + appleTreePos;
            appleCount += pos >= houseLeft && pos <= houseRight ? 1 : 0;
        }
        // all done return result
        console.log(`${appleCount}${'\n'}${orangeCount}`);
        return;
    }    

    // must be more oranges so do the rest of them and return result
    while (i < oranges.length) {
        const pos = oranges[i++] + orangeTreePos;
        orangeCount += pos >= houseLeft && pos <= houseRight ? 1 : 0;
    }
    console.log(`${appleCount}${'\n'}${orangeCount}`);
 }
  • You're right that the solution was inefficient, but in no way was it exponentially more work. It's still definitely polynomial complexity. – 200_success May 18 at 3:48
  • @200_success ?? Is it not call exponential if its n*n? The OP solution is n * m (n the fruit count and the m introduced by creating an array of home positions) thus the amount of work to complete the solution would grow exponentially because the OP had a nested loop {iterate m {iterate n}} – Blindman67 May 18 at 5:30
  • Multiplication is not exponentiation. – 200_success May 18 at 6:05
  • 1
    You should really test your code. You are not adding to the count, just assigning 1 or 0. You also use the wrong variable names e.g. appleCount / applesCount, and the function is missing a start bracket. But besides that, I disagree with doing both in one loop. You are not doing less operations, and just complicating things when they are different lengths. You are repeating a lot of code, and it could be done a lot shorter, see this example. – Kruga May 18 at 9:46
  • 1
    @Blindman67 The main performance issue was the nested loops. After removing those, the performance is fine. I still don't think it's worth complicating the code for an almost negligible performance increase. Btw, n^2 is polynomial, 2^n is exponential. – Kruga May 18 at 12:34
  • Calculate relative distances up front, avoiding calculations in the loops.
  • Use absolute values to simplify
  • Dismiss wrong-sided fruit up front to avoid calculations.

.

function countApplesAndOranges( s, t, a, b, fallenApples, fallenOranges ) {
     debugger;  // for stepping thru with chrome dev tools
     let appleTree            = a,
          orangeTree           = b,
          houseLeft            = s,
          houseRight           = t,
          houseWidth           = Math.abs( houseRight - houseLeft ),
          appleHouseLeftDist   = Math.abs( houseLeft - appleTree ),
          appleHouseRightDist  = Math.abs( houseRight - appleTree ),
          orangeHouseLeftDist  = Math.abs( orangeTree - houseLeft ),
          orangeHouseRightDist = Math.abs( orangeTree - houseRight );

     let appleHits = 0, orangeHits = 0;

     for ( let i = 0; i < fallenApples.length; i++ ) {
         if( fallenApples[ i ] <= 0 ) continue;

         if( fallenApples[ i ] >= appleHouseLeftDist && fallenApples[ i ] <= appleHouseRightDist ) {
             appleHits++;
         }
     }

     for ( let i = 0; i < fallenOranges.length; i++ ) {
         if( fallenOranges[ i ] >= 0 ) continue;

         if( -fallenOranges[ i ] <= orangeHouseLeftDist && -fallenOranges[ i ] >= orangeHouseRightDist ) {
             orangeHits++;
         }
     }

     console.log(`Apple Count: ${appleHits}   ::   Orange Count: ${orangeHits}`);
 }

you can check if the apples and orange in the house range

function countApplesAndOranges(s, t, a, b, apples, oranges) {

    // create 2 variables for in range frutes 
    let applesInRange = 0;
    let orangesInRange = 0;

    // get the max length of both arrays to use it in the for loop
    let length = Math.max(apples.length, oranges.length)


    for(let i=0; i<length;i++){
        //check if this index exist in apples
        if(typeof apples[i] !== 'undefined'){
            if(a+apples[i]>=s && a+apples[i] <= t){
                applesInRange++;
            }
        }

        //check if this index exist in oranges
        if(typeof oranges[i] !== 'undefined'){
           if(b+oranges[i]>=s && b+oranges[i] <= t){
                orangesInRange++;
            } 
        }

    }

    console.log(applesInRange);
    console.log(orangesInRange);
}

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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