Categories
Uncategorized

238. Product of Array Except Self Leetcode Problem Solution

The problem:

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

The solution:

We solve this problem in linear time by computing the production of the left and right array, and then the result array which is simply a production of the left and right array.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    if (nums.length == 0){return 0}
    let n = nums.length
    let right =[], left = [], result =[]
    right[0] = 1, left[n-1] = 1
    for(let i = 1; i< nums.length; i++){
        right[i] = right[i-1]*nums[i-1]
    }
    for(let j = n-2; j>= 0; j--){
        left[j] = left[j+1]*nums[j+1]
    }
   // console.log("right" + right)
   // console.log("left" + left)
     for(let i = 0; i< nums.length; i++){
        result[i] = left[i]*right[i]
    }
    return result
};
Categories
Uncategorized

713. Subarray Product Less Than K Leetcode Problem Javascript Solution

The problem

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:0 < nums.length <= 50000.0 < nums[i] < 1000.0 <= k < 10^6.

My solution:

We will use the sliding window approach for this problem. The number of intervals with subarray product less than k and with right-most coordinate right, is right - left + 1. We’ll count all of these for each value of right.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    if(k <= 1) {return 0};
    let product = 1;
    let left = 0; right = 0, result = 0
    while(right < nums.length){
        product *= nums[right]
        while(product >= k){
            product /= nums[left]
            left += 1
        }
        result += (right - left + 1)
       // console.log(result)
        right += 1
    }
    return result
};
Categories
Uncategorized

44. Wildcard Matching Leetcode Problem Javascript Solution

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

I have been struggling with this problem for a while, not being able to understand dynamic programming well enough to tackle it. First, I tried writing the solution in recursion, but it didn’t pass the lengthy cases and gave a Time Limit Exceed error.

var isMatch = function(str, pattern) {
   // console.log(s[0] + "," + p[0])
   /* recursive solution, not pass
   "abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb"
"**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
     if(p.length == 0){
        return s.length == 0
    }
    if(s.length == 0){
        return p[0] == '*' && isMatch(s,p.substring(1))
    }
    if(s[0] == p[0] || p[0] == '?'){
       return isMatch(s.substring(1),p.substring(1))
       }
     else  if(p[0] == '*'){
         let i = 0
         while(p[i] == '*'){
             i += 1
         }
        return isMatch(s.substring(1),p) || isMatch(s,p.substring(i))
    } else {
        return false
    }
    }

So I delved on this problem while learning about dynamic programming on YouTube, especially the video from theFreeCodeCamp. Finally, something became clear and I was able to fix my solution to make it work:

var isMatch = function(str, pattern) {
  const arr = [];
  for (let i = 0; i <= str.length; i++) {
    arr.push([]);
    for (let j = 0; j <= pattern.length; j++) {
      arr[i].push(false);
    }
  }
  // Empty pattern matches empty string
  arr[0][0] = true;
  // Empty str only matches if pattern is '*'
  for (let i = 1; i <= pattern.length; i++) {
      if(pattern[i-1] != '*'){
          break
      } else {
          arr[0][i] = true
         // console.log(arr[0][i])
      }
  }
  for (let i = 1; i <= str.length; i++) {
    for (let j = 1; j <= pattern.length; j++) {
      if (pattern[j-1 ] == '*') {
        arr[i][j] = arr[i - 1][j] || arr[i][j - 1];
      } else if(pattern[j-1] == '?' || pattern[j-1] == str[i-1] ) {
        arr[i][j] = arr[i - 1][j - 1];
      } else {
          arr[i][j] = false
      }
    }
  }
    /*
  for (let i = 0; i <= str.length; i++) {
      let s = ''
    for (let j = 0; j <= pattern.length; j++) {
        s += arr[i][j]
    }
          console.log(s)
  }
*/
  return arr[str.length][pattern.length];
};
Categories
Uncategorized

5 Reasons Why 2021 Is the Best Time to Start Your Online Business

If you are hesitant about starting a business during an economic downturn, think again. Microsoft was founded during the oil recession from 1973 to 1975. Uber and Airbnb were also founded during the recession of 2007-2009. There are virtually myriads of examples like these to prove to you that it’s maybe your best idea to start a new business during a trying time.

The Available Labor Force

Many people are out of jobs during an economic downturn. While this often has a negative meaning, from an employer’s viewpoint, this means a more available talent pool for them to recruit from. During an economic upbeat, every company is thriving and willing to pay higher to get the best talent. Therefore, you’ll have more difficulty recruiting the best.

Most People Are in Retrospective Mode

More time spent at home means that most people have fewer distractions to keep them from thinking about themselves and the future. Admittedly, too much alone time can be bad for your mental health. However, if you learn to use your alone time in a constructive way to reflect upon yourself, you’ll discover your strengths, weaknesses, and what you want to do in life. This insight can help shape you in the future and give you ideas about the kind of business you want to set up.

More Online Content Is Being Consumed Than Ever

A study has found that daily online content consumption has doubled during COVID-19 time. From an entrepreneur’s point of view, this spells more opportunities to make money. There are virtually endless business opportunities that you can start online for a next-to-nothing cost. Starting a YouTube channel/blog, becoming a freelance writer/social media expert/coach, or selling your art online. These are just some ideas to start with.

Ecommerce Has Spiked 40% During Covid-19

A study concluded that e-commerce sales have risen 40% post-Covid. As restrictions were rolled out, more and more people resort to shopping online. The need to go out and get things done diminished when you could just stay home in your pajamas and get things done the same way. We are talking about online shopping, grocery delivery, remote wellness, and at-home fitness programs. If you can practically attend a divorce court through teleconferencing, what else can you not do online?

If you want to jump on the bandwagon of e-commerce, now is not too late. There are platforms, such as eBay, Etsy, Shopify, and even WordPress, that allow you to set up your store and start selling in virtually no time. You just have to figure out the logistics part of how you will source the products, shipping, and return handling. 

The e-commerce trend is here to stay, as does the remote working culture. If you have high-quality products, accompanied by a good marketing plan, there’s no reason why you shouldn’t be successful.

The Cost of Starting an Online Business Can Be Next-to-Nothing

A brick-and-mortar business generally requires a much larger investment at the beginning than an online one. You don’t need to spend on office rental or hire employees to deal with customers face-to-face. With an online business, you can virtually outsource everything, from product manufacturing to customer support. If you decide to sell on your private website, the greatest cost would be the payment made to a web development agency to get the site done. The cost of hiring a customer service agency to take care of product shipping, error handling, returns, customer complaints, etc. is comparatively cheap if you outsource from countries with cheaper labor costs such as the Philippines, India, or China.

As you can see, it’s worth it to give it a try. If it has always been your dream to be your own boss, work your own hours, and enjoy financial independence, there has never been a better time to start than now.

Categories
Uncategorized

17. Letter Combinations of a Phone Number Leetcode Javascript Solution

The problem:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

The digit 0 maps to 0 itself.

The digit 1 maps to 1 itself.

The solution:

We’ll use backtracking to solve this problem. First, we need to create a hashset to store the character mapping.

/**
@param {string} digits
@return {string[]}
*/
var letterCombinations = function(digits) {
if(digits.length == 0){
return []
}
const letters = {2: “abc”,
3: “def”,
4: “ghi”,
5: ‘jkl’,
6: ‘mno’,
7: ‘pqrs’,
8: ‘tuv’,
9: ‘wxyz’
}
let result = []
backtrack(“”,digits)
function backtrack(combination, next_digits){
if(next_digits.length == 0){
result.push(combination)
}
else{
let chars = letters[next_digits.substring(0,1)]
for (let char of chars){
// console.log(char)
backtrack(combination + char, next_digits.substring(1))
}
}
}
return result
};