DEV Community: Yaz

Best Time to Buy and Sell Stock II - Leetcode 122 - TypeScript

Yaz — Wed, 07 Feb 2024 19:05:54 +0000

Here's the Leetcode 122 solution using TypeScript.

Leetcode 122 - Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Approach

Your goal is to find the maximum profit that can be obtained by multiple buy-and-sell transactions on a given stock.

You can use a one-pass algorithm with two pointers, l and r, to track the buying and selling days.

Initialize l and r to the first and second days, respectively.

Then iterate through the array using a while loop.

In each iteration, check if the price on day l is less than the price on day r.

If true, then calculate the profit by subtracting the buying price (prices[l]) from the selling price (prices[r]).

The calculated profit is added to the total profit (max), and the l pointer is moved to the current selling day (r).

If the buying price is not less than the selling price, it means a better buying opportunity is found, so the l pointer is moved to the current selling day (r) without adding any profit.

This ensures that your algorithm considers multiple transactions for optimal profit.

The final result is the maximum profit obtained by multiple buy-and-sell transactions on the stock.

Code Implementation

function maxProfit(prices: number[]): number {
  let l = 0,
    r = 1,
    max = 0

  while (r < prices.length) {
    if (prices[l] < prices[r]) {
      const profit = prices[r] - prices[l]
      max += profit
      l++
    } else l = r
    r++
  }

  return max
}

Time Complexity

Time complexity is O(n), where n is the length of the input array prices. The algorithm iterates through the array once, and each iteration involves constant-time operations.

Space Complexity

Space complexity is O(1) or constant. The algorithm uses only a constant amount of extra space for variables.

It doesn't require additional memory that grows with the size of the input array.

My thoughts on building startups, inspired by Sam Altman.

Yaz — Wed, 07 Feb 2024 02:45:48 +0000

These are my notes and thoughts on Sam Altman's startup investor school presentation. This post may be valuable to anyone serious about building startups.

I recently gave up a high-paying corporate job to pursue what I'm passionate about and fully focus on building startups. Sam Altman perfectly summarizes my feelings towards the entire situation:

There's beauty in inexperience. People who are doing things for the first time will be doing things that anyone with a few more battle scars won’t try.

Sam Altman

I feel happier when I'm around people with startup-oriented mindset. These people carry an endless sense of optimism about the future, a quality you likely won't find in any other industry.

Sam mentions that investing in startups is a very humbling experience. You make mistakes and you get used to being wrong.

I believe this concept applies to both angel investing and also building a startup. As a founder, you'll often find yourself making mistakes and it's inevitable. You must be willing to admit that you’ve made and error and try to avoid the same mistake next time.

On the other hand, this should not impact your confidence. You should continue to make decisions, even though you're fully aware that you're prone to mistakes. This is a great quality to have as an individual.

Sam mentions two major mistakes that angel investors often make. I've personally witnessed these two common mistakes throughout my career and it just clicked when Sam mentioned it. As a founder, it's important to understand how most investors think:

People often outsource 80% of their decision-making based on other’s opinions. The issue is that this approach will cause trends where every investor wants to invest in a particular company without any solid reasoning, merely based on other investor’s behaviour
Power law: Your most successful investment will yield a greater return than all your other investments combined. Likewise, your second-best investment will outperform the sum of your third and all subsequent investments. Most people new to angel investing wonder if they can succeed through a series of smaller, consistent investments. While this strategy may work with stocks, angel investing is about hitting home runs. Investors should always be on the lookout for potential home runs, and they often aren’t.

It’s all about magnitude of your biggest success and it’s not about your failure rate.

Sam Altman

You can have 95% failure rate and one investment can return a billion dollar and you’ll be happy.

YC has funded approximately 1700 companies. Their top 5 companies represent about 2/3 of the value they have created, while one top company accounts for 1/3 of this value.

Other than that, many of these generation-defining companies are started by individuals who are not well-known and out of network. These are not the type of people who can launch a company and get bunch of press right away.

First think how big could it be if it works? And only then think about the potential things that can go wrong.

Sam Altman

Maintaining a good reputation during challenging times is more valuable than extracting a small sum from a dying company.

Reputation of being good to work with goes a long way and people remember that for a long time.

Sam Altman

Starting a startup is a long-term commitment. If it's going to work, it will likely take more than a decade, and there may be times when you want to give up. Many people start startups thinking it's a quick path to become rich, but this is rarely the case.

You want focused and mission-driven founders, your personal growth is just as important as your business growth. This helps you stay on track even during tough times.

you have to have a deep sense of mission as a startup founder

Sam Altman

You should favor a small, growing market over a large, existing one. If you pursue what has worked in the past, it will be harder to do for the second time. It's far more better to identify the next rapidly expanding market.

To do that, you need to be an independent thinker, and you are not going to succeed by simply following others.

If you are able to think independently, you will approach trends with skepticism.

To identify genuine trends, look for instances where not many people may be talking about it, but those actually using the product are consistently talking about it.

That's all I got. I hope you found this post valuable.

Best Time to Buy and Sell Stock - Leetcode 121 - TypeScript

Yaz — Mon, 05 Feb 2024 20:47:51 +0000

Here's the Leetcode 121 solution using TypeScript.

Watch on Youtube

Leetcode 121 - Best Time to Buy and Sell Stock:

You are given an array 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.

Approach

The goal is to find the maximum profit that you can obtain by buying and selling a stock given it's prices over time.

You can use a simple one-pass algorithm with two pointers, l and r, and track the buying and selling days.

Initialize l and r to the first and second days, respectively.

Then iterate through the array using a while loop.

In each iteration, check if the price on day l is less than the price on day r. If true, calculate the profit by subtracting the buying price (prices[l]) from the selling price (prices[r]) and update the maximum profit (max) only if the calculated profit is greater than the current maximum.

On the other hand, if the buying price is not less than the selling price, it means a better buying opportunity is found, so move the l pointer to the current selling day (r). This way you can ensure that the algorithm always looks for the lowest buying price before searching for a selling opportunity.

The final result is the maximum profit obtained by buying and selling the stock.

View on Excalidraw

Code Implementation

function maxProfit(prices: number[]): number {
  let l = 0
  let r = 1
  let max = 0

  while (r < prices.length) {
    if (prices[l] < prices[r]) {
      const profit = prices[r] - prices[l]
      max = Math.max(profit, max)
    } else l = r

    r++
  }

  return max
}

Time Complexity

The time complexity is O(n), where n is the length of the input array prices. The algorithm iterates through the array once, and each iteration involves constant-time operations.

Space Complexity

The space complexity is O(1) or constant. The algorithm uses only a constant amount of extra space for variables like l, r, max, and profit.

It doesn't require additional memory that grows with the size of the input array.

Rotate Array - Leetcode 189 - TypeScript

Yaz — Mon, 05 Feb 2024 18:03:42 +0000

Here's the Leetcode 189 solution using TypeScript.

Watch on Youtube

Leetcode 189 - Rotate Array:

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Approach

The goal is to rotate an array nums to the right by k steps. You can use a cyclic rotation by repeatedly popping the last element and unshifting it to the beginning of the array in a loop.

The for loop runs for k iterations, and in each iteration, the pop method removes the last element from the array, and unshift adds it to the beginning. This process is repeated k times and it will rotate the array to the right.

View on Excalidraw

Code Implementation

function rotate(nums: number[], k: number): void {
  for (let i = 0; i < k; i++) nums.unshift(nums.pop()!)
}

Time Complexity

Time complexity is O(k * n), where n is the length of the input array nums. In each iteration of the loop, both pop and unshift operations take O(n) time as they involve shifting elements. Therefore, the total time complexity is O(k * n).

Space Complexity

Space complexity is O(1) or constant. The algorithm performs the rotation in-place, it modifies the input array directly without using additional memory that grows with the size of the input array.

Remove Duplicates from Sorted Array II - Leetcode 80 - TypeScript

Yaz — Sat, 03 Feb 2024 12:24:31 +0000

Here's the Leetcode 80 solution using TypeScript.

Watch on Youtube

Leetcode 80 - Remove Duplicates from Sorted Array II

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Approach

The goal is to modify an array of numbers by allowing at most two duplicates of each element and return the new length of the modified array.

You'll use two pointers:

i to iterate through the array.
k to keep track of the position where valid elements (remember you can only allow at most two duplicates) should be placed.

You'll start the loop from the third element (index 2) since the first two elements are automatically considered as part of the modified array.

Then you'll check if the current element is different from the element at position k - 2.

If it is, it means the current element is not a duplicate within the allowed limit, so you assign its value to the position indicated by the pointer k and then increment k.

This approach will allow only two duplicates of each element in the modified portion of the array.

Now k represents the new length of the modified array.

View on Excalidraw

Code Implementation



function removeDuplicates(nums: number[]): number {

  let k = 2

for (let i = 2; i < nums.length; i++) {

    if (nums[i] !== nums[k - 2]) {

      nums[k] = nums[i]

      k++

    }

  }

return k

}

Time Complexity

The time complexity is O(n), where n is the length of the input array nums. The algorithm iterates through each element in the array once, and the operations inside the loop take constant time.

Space Complexity

The space complexity is O(1) or constant. The algorithm modifies the input array in-place, and only uses a constant amount of extra space for variables. It doesn't require additional memory that grows with the size of the input array.

Majority Element - Leetcode 169 - TypeScript

Yaz — Thu, 01 Feb 2024 18:29:01 +0000

Here's the Leetcode 169 solution using TypeScript.

Watch on Youtube

Leetcode 169 - Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Approach

The goal is to find the majority element in an array, the majority is an element that appears more than ⌊n / 2⌋ times (where n is the length of the array).

There are several approaches to solve this problem, but the easiest approach is sorting the array and finding the element at the middle index.

After sorting, the majority element will always be at the middle index of the sorted array.

View on Excalidraw

Code Implementation



function majorityElement(nums: number[]): number {

  nums.sort((i, j) => i - j)

  const midIdx = Math.floor(nums.length / 2)

  return nums[midIdx]

}

Time Complexity

Time complexity is O(n log n), where n is the length of the input array nums. The dominating factor here is the sorting operation, which has a time complexity of O(n log n) for most sorting algorithms.

Space Complexity

Space complexity is O(1) or constant. The sorting is done in-place, it means the algorithm modifies the input array directly without using additional memory that grows with the size of the input array. The space required for variables like midIdx is constant regardless of the input size.

Remove Duplicates from Sorted Array - Leetcode 26 - TypeScript

Yaz — Tue, 30 Jan 2024 12:00:12 +0000

Here's the Leetcode 26 solution using TypeScript.

Watch on Youtube

Leetcode 26 - Remove Duplicates from Sorted Array:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

Approach

The goal is to modify an array nums by removing any duplicate elements and return the new length of the modified array.

You should use two pointers:

(i) to iterate through the array.
(k) to keep track of the position where unique elements should be placed.

You'll loop through each element in the array and checks if the current element is less than the next element.

If it is, it means the current element is unique, so we assign its value to the position indicated by the pointer k and then increment k.

If the next element is undefined (which indicates the end of the array), you'll also add the current element to the modified portion of the array.

The last element of the original array should be considered anyways, even if it is a duplicate.

View on Excalidraw

Code Implementation



function removeDuplicates(nums: number[]): number {

  let k = 0

for (let i = 0; i < nums.length; i++) {

    if (nums[i] < nums[i + 1]) {

      nums[k] = nums[i]

      k++

    } else if (nums[i + 1] === undefined) {

      nums[k] = nums[i]

      k++

    }

  }

return k

}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array nums.

This is because the algorithm iterates through each element in the array once, and the operations inside the loop take constant time.

Space Complexity

The space complexity is O(1) or constant, which means that the algorithm uses only a fixed amount of extra space regardless of the size of the input array.

The space complexity is low because our algorithm modifies the input array in-place and only uses a constant number of variables.

Remove Element - Leetcode 27 - TypeScript

Yaz — Tue, 23 Jan 2024 04:11:25 +0000

Here's the Leetcode 27 solution using TypeScript.

Watch on Youtube

Leetcode 27 - Remove Element:

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Approach

Your goal is to remove all occurrences of a specified value from an array nums and return the new length of the modified array.

You can use two pointers: one i to iterate through the original array and another k to keep track of the position where non-matching elements should be placed.

You'll loop through each element in the array, and if the current element is not equal to the target value, it means you want to keep that element.

In this case, we assign the value of the current element to the position indicated by the pointer k and then increment k.

This effectively removes the occurrences of val from the modified portion of the array.

Then you'll have your modified array, and you can also return k which is basically the length of the modified array.

View on Excalidraw

Code Implementation

function removeElement(nums: number[], val: number): number {
  let k = 0

  for (let i = 0; i < nums.length; i++) {
    const element = nums[i]
    if (nums[i] !== val) {
      nums[k] = nums[i]
      k++
    }
  }

  return k
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array nums.

This is because the algorithm iterates through each element in the array once, and the operations inside the loop take constant time.

Space Complexity

The space complexity is O(1) or constant because the algorithm modifies the input array in-place,and we are using only a constant amount of extra space for variables. It doesn't require additional memory that scales with the size of the input array.

In simpler terms, the time it takes to run the algorithm grows linearly with the size of the input array, and it doesn't use much extra memory regardless of the array's size.

Merge Sorted Array - Leetcode 88 - TypeScript

Yaz — Sun, 21 Jan 2024 08:33:44 +0000

Here's the Leetcode 88 solution using TypeScript.

Watch on YouTube

Leetcode 88 - Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

Approach

Since both arrays are sorted, you can use two pointers to compare elements from the end of both arrays.

You'll use two pointers (m and n) initially set to the lengths of nums1 and nums2.

Then you can compare the elements at these positions, and the larger element is placed at the end of nums1.

Then you'll decrement the pointers and the position in nums1 accordingly.

You should continue this process until either of the arrays is fully merged.

If there are remaining elements in nums2 after the first loop, you'll add them to the beginning of nums1.

View on Excalidraw

Code Implementation



function merge(nums1: number[], m: number, nums2: number[], n: number): void {

  let last = m + n - 1

while (m > 0 && n > 0) {

    if (nums1[m - 1] > nums2[n - 1]) {

      nums1[last] = nums1[m - 1]

      m -= 1

    } else {

      nums1[last] = nums2[n - 1]

      n -= 1

    }

    last -= 1

  }

while (n > 0) {

    nums1[last] = nums2[n - 1]

    n -= 1

    last -= 1

  }

}

Time Complexity

This solution has the time complexity of O(m + n), where m and n are the lengths of the input arrays nums1 and nums2.

The algorithm iterates through the arrays once, and at each step, it compares and places elements in the correct position.

Since the length of the merged array is m + n, the time complexity is linear with respect to the combined length of both input arrays.

Space Complexity

The space complexity is O(1) or constant.

The algorithm performs the merging in-place without using any additional space that scales with the input size.

We use a constant amount of extra space for variables like last, m, n, and the loop control variables.

This makes the algorithm memory-efficient, as the space required to perform this algorithm remains constant regardless of the input size.