Day 1: Leetcode | 121. Best Time To Buy And Sell Stock Solution

Difficulty: Easy Language: JavaScript

Problem Description
You have given an array of prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Explanation 1: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6–1 = 5.

Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Explanation 2: In this case, no transactions are done and the max profit =0.

Brute Force Solution — O(n²)
To solve this problem, first, we use a Brute force algorithm approach. we will try all possible profits we can get from the given values and pick the highest one

Failed time complexity: O(n²)
The input size is 10⁵ so that the nested loop will cause TLE(time limit exceed).

Better Solution — O(n)
We can go through all of the prices and we can instead keep track of the minimum price and subtract it from the selling prices like so.

Complexity analysis

Time complexity: O(n)Space complexity: O(1)

This solution works great!