3
\$\begingroup\$

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example one: Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.

Example two: Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.

My solution:

walked the array grabbing the initial price and continued to swap it with the smallest value. Between the current smallest value < and only the proceeding larger peaks. With the solution being the largest chasms (difference) between the lowest peak and highest summit in value within an interval. TimeComplexity is O(n) space complexity is O(1) only using one object.

const perfectPrice = (prices, peak = {
  buy: null,
  buy_day: null,
  sell_day: null,
  sell: null,
  profit: 0,
  profitable: {}
}) => {
  const week = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
  prices.forEach((price, day, all) => {
    if (peak['buy'] === null) {
      peak['buy_day'] = day
      peak['buy'] = price

    } else if (price < peak['buy']) {
      peak['buy'] = price
      peak['buy_day'] = day
    }
    if (peak['profit'] < (price - peak['buy'])) {
      peak.profitable = {
        buy: week[peak.buy_day],
        buy_at: peak['buy'],
        sell: week[day],
        sell_at: price,
        profit: price - peak['buy']
      }
      peak['profit'] = price - peak['buy']
    }
  });
  return ((peak || {}).profitable || {}).profit ? peak.profitable : 'not profitable to sell';
}


console.log("(test 1):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 2):", perfectPrice([7, 6, 4, 3, 1]))
console.log("(test 3):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 4):", perfectPrice([1, 2]))
console.log("(test 5):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 6):", perfectPrice([2, 9, 5, 3, 1, 4]))
.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}

\$\endgroup\$
  • 1
    \$\begingroup\$ Still looks broken as there are only two days in test case 4, yet Monday and Wednesday aren't one night apart. \$\endgroup\$ – Gerrit0 Aug 1 '18 at 2:37
  • \$\begingroup\$ @Gerrit0 added days of the week last min forgot to remove the offset. fixed. thanks for pointing that out. \$\endgroup\$ – Rick Aug 1 '18 at 2:45
  • 1
    \$\begingroup\$ I think this is not working correctly. Take this test case: [2, 9, 5, 3, 1, 4] . It should say: buy on Monday, sell on Tuesday, get 7. But instead it says: buy on Friday, sell on Tuesday, get 7. Where the amount looks correct but not the day. \$\endgroup\$ – insertusernamehere Aug 1 '18 at 13:25
  • \$\begingroup\$ @insertusernamehere thanks for pointing that out. Where I was collecting the days and prices were incorrect. I needed to collect them only in the profitability section. thanks for pointing that out. \$\endgroup\$ – Rick Aug 1 '18 at 17:19
2
\$\begingroup\$

Readability

  • The way you've named your variables makes the code more difficult to read for example peak just doesn't make sense to me. Another consideration would be to rename buy_day to cheapest_day
  • Don't overcomplicate things: I found the return statement at the end of your forEach confusing

General syntax improvement that would make the code easier to read:

  • Use camelCase over snake_case
  • Use dot notation when accessing an objects properties where possible

Remove unnecessary/unused code

  • You have an if/elseif that does the same thing this can be simplified using an or statement if (this || that)
  • peak.sell and peak.sell_day are never used, same for all in your prices.forEach

Misc

There may be some reasoning you had which I'm missing but I did't see the point in accepting the second argument peak.

Rewrite

const perfectPrice = (prices) => {
    const week = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday'];
    
    let profit = 0;
    let profitable;
    
    const cheapest = {
        day: null,
        price: null,
    };

    prices.forEach((price, day) => {
        if (day === 0 || price < cheapest.price) {
            cheapest.price = price;
            cheapest.day = day;
        }
        
        const potential = price - cheapest.price;

        if (!(potential > profit)) {
            return;
        }
          
        profit = potential;
        
        profitable = {
            buy: week[cheapest.day],
            buyAt: cheapest.price,
            sell: week[day],
            sellAt: price,
            profit,
        };
    });

    return profitable || 'not profitable to sell';
};


console.log("(test 1):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 2):", perfectPrice([7, 6, 4, 3, 1]))
console.log("(test 3):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 4):", perfectPrice([1, 2]))
console.log("(test 5):", perfectPrice([7, 1, 5, 3, 6, 4]))
console.log("(test 6):", perfectPrice([2, 9, 5, 3, 1, 4]))

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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