BestTimetoBuyStocks/ ContainsDuplicate

BestTimetoBuyStocks

Given an array prices where prices[i] represent the price of a stock in a given day, return the maximum profit you can achieve in one transaction. If you cannot achieve any profit, simply return zero.

Consider only buying stocks, there will be no option to short, or leverage.

Example

Input: prices = [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. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Approach 1:

I knew a simple brute-force algorithm where you iterate the list with a for loop and a nested for loop inside would check every pairs within the list. However, I would find that to be O(N^^2) and comparing too many unnecessary pairs.

The trick in this question to compute using one-pass is to keep track of the lowest price. This way, we can iterate through the list looking for the greatest difference between the pairs in which the larger number within the pair comes later.

Implementation:

class Solution:
    

    def maxProfit(self, prices):
        profit = 0
        start = prices[0]
        for i in range(1, len(prices)):
            if prices[i] < start:
                start = prices[i]
             if prices[i] - start > profit:
                 profit = prices[i] - start
        
        return profit
        

Complexity Analysis:

Time Complexity:O(n) where n is the lenght of the list prices

Space Complexity: O(1)

ContainsDuplicate

Given an integer array nums, return true if any value appears at least twice in the array, and false otherwise.

Example

Input: nums = [1,2,3,1] Output: true

Approach 1:

This can be easily implemented by using sets which gets rid of all the duplicates. I could check if each items in the list are already in the set and immediately return false if so, otherwise keep adding items and return false once reacching the end of the list.

While it might not be time-efficient, I could also write a one line code that returns a boolean whether the len(nums) != len(set(nums))

Implementation:

class Solution:
    

    def containsDuplicate(self, nums):
        unique = set()
        for i in range(len(nums)):
            if nums[i] in unique:
                return True
            unique.add(nums[i])
        return False
        # return len(set(nums)) != len(nums)
        

Complexity Analysis:

Time Complexity:O(n) where n is the lenght of the list prices

Space Complexity: O(n) since I make use of a set

Reflection

I am glad that I can solve these “easy” array questions!