The problem statement​

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type

Understanding the problem​

So lets break down our approach here:

1. Store a map of all the closing brackets as keys, with opening as values. This will allow us to perform lookups when looping through chars.
2. Create an array which will hold our latest opening braces.
3. Loop through the input string
   1. If map contains char (it's a closing brace)
      1. If our array has items, and the latest item in our array is equal to the map value of our closing brace.
         1. We have found a match, so we remove that opening brace from our array.
      2. Else we need to return false from our function as we have an invalid set of braces. The one we are iterating does not close the latest brace.
   2. Else it doesn't contain our brace, and the brace is opening not closing so we push that brace into our array.
4. Return whether our array of opening braces has a length of 0 (which it should) at the end of the function. This means all open braces were closed successfully.

Examples:​

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Code solution​

function isValid(s: string): boolean {
  const closeToOpen = new Map<string, string>();
  closeToOpen.set("}", "{");
  closeToOpen.set("]", "[");
  closeToOpen.set(")", "(");

  const stack: string[] = [];
  for (const c of s) {
    if (closeToOpen.has(c)) {
      // If the last item in the stack is equal to the opening version of the current closing brace, then remove it from the stack.
      if (stack.length > 0 && stack[stack.length - 1] === closeToOpen.get(c)) {
        stack.pop();
      } else {
        return false;
      }
    } else {
      stack.push(c);
    }
  }
  return stack.length === 0;
}

Key Takeaways​

1. Using a hashmap to match closing chars to opening was a technique that Neetcode used, after a while of reading the code it made sense to me. I'll make sure to apply this technique in other problems where I need to match x char to y char.
2. An array is basically a stack.

The problem statement​

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

Understanding the problem​

When we go through the array, we need to decide if the iterated number has already been found. If it has then we want to return true. Else let the whole loop of the array continue and return false.

To store a history of the numbers we find we want to use a Set data type. Primarily because insertion, deletion and lookup all have O(1) time complexity.

Examples:​

Example 1:

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

Output: true

Example 2:

Input: nums = [1,2,3,4]

Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]

Output: true

Code solution​

Potentially need to iterate all elements in the array.

• Time: O(n) - n items in nums.
• Space: O(n) - set grows as the iterations carry on.

function containsDuplicate(nums: number[]): boolean {
  const iterated = new Set<number>();
  for (let i = 0; i < nums.length; i++) {
    if (iterated.has(nums[i])) return true;
    iterated.add(nums[i]);
  }
  return false;
}

Key Takeaways​

1. Set is a really efficient js data structure.

The problem statement​

Let's do some simple two-way binding.

Please create a function model(state, element), to bind state.value to the HTMLInputElement element.

Understanding the problem​

Essentially when state.value changes we need to update the value of element.value to state's new value.

This includes adding an event listener to the element and also to the state value property.

Examples:​

const input = document.createElement("input");
const state = { value: "BFE" };
model(state, input);

console.log(input.value); // BFE
state.value = "dev";
console.log(input.value); // dev
input.value = "BFE.dev";
input.dispatchEvent(new Event("change"));
console.log(state.value); // BFE.dev

Code solution​

function model(state: { value: string }, element: HTMLInputElement) {
  // set the initial dom element value
  element.value = state.value;

  // add event listener so that when element.value changes we update state.value to be element.value.
  element.addEventListener("change", () => {
    state.value = element.value;
  });

  // defineProperty will either add a new property or update the behaviour of an existing one. This allows us to react to updates of state.value and also update element.value.
  Object.defineProperty(state, "value", {
    get: function () {
      return this._value;
    },
    set: function (value) {
      this._value = value;
      element.value = value;
    },
  });
}

Key Takeaways​

1. defineProperty is really useful and there are lots of code challenges / frontend projects where this could be useful for reactivity.

The problem statement​

There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.

Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

Note that multiple kids can have the greatest number of candies.

Understanding the problem​

The problem is asking us to loop through each kid's candy count and see if their new candy amount with the extraCandies added onto ith result is greater than or equal to the highest number of candies in the existing array.

At first I decided to create a new array of candies size and preset the vals to false. Then loop through the array and for each kid, check if their new candy amount was greater or equal to each item in the array. If it was we set their array position to true and move on and then return the array at the end.

This worked. But it's really not efficient as we end up with a space complexity of O(n) and a time complexity of O(n^2).

So lets look at what the question is asking of us again.

Find the highest value of candies in the array. Then loop through the array and return whether the current item in the array + extra candy is greater than the highest value of candies.

By doing an approach like above we can achieve a space complexity of O(1) and a time complexity of O(n).

Approaching the problem​

Examples:​

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3

Output: [true,true,true,false,true]

Explanation: If you give all extraCandies to:

• Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
• Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
• Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
• Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
• Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1

Output: [true,false,false,false,false]

Explanation: There is only 1 extra candy. Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.

Example 3:

Input: candies = [12,1,12], extraCandies = 10 Output: [true,false,true]

Code solution​

Time: O(n^2) Space: O(n)

function kidsWithCandies(candies: number[], extraCandies: number): boolean[] {
  // Create the array to hold our results in.
  const result = new Array(candies.length).fill(false);
  for (let i = 0; i < candies.length; i++) {
    // get the new candy result
    const newCandy = candies[i] + extraCandies;
    // apart from the current candy val, check that every other value is less than or equal to new candy.
    if (candies.filter((_, idx) => idx !== i).every((x) => newCandy >= x)) {
      result[i] = true;
    }
  }
  return result;
}

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

function kidsWithCandies(candies: number[], extraCandies: number): boolean[] {
  // get the max candy val from the array
  const maxCandies = Math.max(...candies);
  // return a new array where the values are calculated by checking that the new candy amount is greater than or equal to the highest candy amount.
  return candies.map((x) => x + extraCandies >= maxCandies);
}

Key Takeaways​

1. Math.max has a lot of uses, make sure to think of the math module in a lot of these problems.
2. By doing a map on the existing array I did not need to create a holding array at the end as it would have kept the results in the same place.
3. Re-read the requirements a good few times. Only after implementing the first way did I have a lightbulb moment and approach in the second way.

The problem statement​

For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Understanding the problem​

Initially I approached this problem by looping the strings by the max length string. Then checking that each value at the same index matched each other. This approach was sort of on the right tracks but wouldn't get us to our final destination.

After watching a neetcode solution here is how I would approach the problem.

First of all it's important to understand that the question wants us to find the largest possible substring that goes into both strings.

To achieve this we need to validate a few things:

1. That the substring length can be divided by both of the string lengths equally.
2. That the substring can be repeated x times where x is str.length / substring.length.

Once we know all of this we can simply report back what is the possible substring.

Approaching the problem​

Examples:​

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"

Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"

Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"

Output: ""

Code solution​

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

function gcdOfStrings(str1: string, str2: string): string {
  function isDivisor(desiredLength: number): boolean {
    // If the desired length cant product a non-remainder number when divided by the string lengths, then this isn't a divisor.
    if (str1.length % desiredLength !== 0 || str2.length % desiredLength !== 0)
      return false;

    // Get the amount of times that str1 and str2 can be divided by our target length
    let factorial1 = str1.length / desiredLength,
      factorial2 = str2.length / desiredLength;

    // Check whether the substring which is generated by repeating the string by 0 and desiredLength f times is equal to both of our strings.
    // i.e. 6 / 2 = 3 && 2 / 2 = 0, AB * 3 = ABABAB, AB * 0 = AB.
    return (
      str1.substring(0, desiredLength).repeat(factorial1) === str &&
      str1.substring(0, desiredLength).repeat(factorial2) === str2
    );
  }
  // Loop the smallest string length
  for (let i = Math.min(str1.length, str2.length); i > 0; i--) {
    if (isDivisor(i)) {
      // if we have found a divisor then return the substring.
      return str1.substring(0, i);
    }
  }
  return "";
}

Key Takeaways​

1. strings have a useful prototype called .repeat() which takes an amount of times that you can repeat a string.

The problem statement​

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implment a solution with a linear runtime complexity and use only constant extra space..

Understanding the problem​

So this problem threw me off initially.

My initial approach was to say okay, i'm going to store a hashmap of integers and the amount that they occur.

Then i'll just iterate through it and find the entry that has a value of 1 and return its key.

But the problem says: Linear complexity and constant space. This means upon each run we can do O(n) time complexity, but we need to use O(1) space. Meaning that the variables we assign, they don't change size regardless of the size of the input. So this throws the map answer out the window.

However, if we think about this problem again. We know that the integer that only occurs once will have the same index as the last time that it occurs.

So we can iterate through the nums and check the index of the integer and it's last index via some prototypes from js. If it's the same, we have found the number with a singular occurence and can return it. This gives us a space complexity of O(1) as we are not creating any new vars as part of our workflow. It is linear in time because we still have to loop through the array n amount of times. where n <= nums.length.

Approaching the problem​

Examples:​

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Code solution​

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

function singleNumber(nums: number[]): number {
  if (nums.length === 1) return nums[1];
  for (let i = 0; i <= nums.length; i++) {
    if (nums.indexOf(nums[i]) === nums.lastIndexOf(nums[i])) {
      return nums[i];
    }
  }
  return 0;
}

Key Takeaways​

1. Keep refreshing the knowledge on js prototypes they will come in handy!
2. Think about how to solve the problem outside of the box. Stop remembering past solutions and thinking of using them as gospel. Try to analytically digest the problem and understand what it's after. Just like we did with the index solution.

The problem statement​

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Understanding the problem​

This is a very tricky problem.

My initial thoughts are to solve this problem by using recursion. Recursively stepping through from 0 -> n and at each increment (step), branching off to 1 or 2 and working through each decision tree. We would then eventually get a count of how many ways we can reach n.

However, this would be very expensive. If you imagined all the possible combinations, you would find yourself repeating a lot of the same checks as the same numbers would be reached at decision trees on the left and right of each other.

This is where a concept called dynamic programming can come into play.

Instead of starting at 0 and working towards n. We start from n and work back up to 0.

So imagine our n is 5. We would start at the number 5 and say how many ways can we land on 5. Well we know one way which is to take 5 * 1 steps. Then we go to 4, we can take one step and get to 5. So therefore we know that we have 1 way to get to 5. So we mark 1 and move to 3. When we get to 4, we already know how many ways to get to 5 which is 1. We also know that when we land on 5 we have 1 way to get there. So we can just add the two previous results together and there is our value for 3. We can continue doing this for each number <= n. Storing the past two results and computing our next values.

This means no storing an object / array of n. Only ever the last two, giving a space complexity of O(1).

Approaching the problem​

Examples:​

Example 1:

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3

Output: 3

Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Code solution​

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

function climbStairs(n: number): number {
  // Store the last two values when working backwards
  let one = 1,
    two = 1;
  for (let i = 0; i < n - 1; i++) {
    // Store the historical value of one so we don't lose it.
    const temp = one;
    // Add the two previous results and get the new result
    one = one + two;
    // Shift two, to the previous value of one
    two = temp;
  }
  // One will have the total amount of ways we can get to n.
  return one;
}

Key Takeaways​

1. I need to do some more investigating into dynamic programming, at least just the basics.
2. Being able to visualize problems like these are quite hard for me, but watching neetcode break it down into a decision tree really helped me grasp the end solution.
3. Watch a video on how to solve a problem rather than just looking at the code solutions. Write up the blog post after.

The problem statement​

Given an integer n return true if its is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n === 4^x.

Understanding the problem​

We can solve this problem with recursion:

1. 1 is a valid result for being a power of a number as the remainder will always be 0.
2. If n is <= 0 then we should return false as a negative number can't be a power of a number.
3. If dividing n by 4 results in a remainder then we should return false as it can't be divided equally.

Approaching the problem​

Examples:​

Example 1:

Input: n = 16

Output: true

Example 2:

Input: n = 5

Output: false

Example 3:

Input: n = 1

Output: true

Code solution​

Log(n)

function isPowerOfFour(n: number): boolean {
  if (n === 1) return true;
  if (n <= 0 || n % 4 != 0) return false;
  return isPowerOfFour(n / 4);
}

Key Takeaways​

1. 1 is always a factor of a number.
2. Anything to the power of 0 is 1.

The problem statement​

Given two arrays, find the intersection(items occur in both arrays)

1. arrays are not sorted, and might have duplicates.
2. you can modify the arrays
3. you can return the items in any order, but without duplicates.

This is an easy problem, What is the time & space complexity of your approach?

Examples:​

There are no examples for the given problem, but lets come up with some: getIntersection([1,2,3], [1]) = [1]

getIntersection([1,2,3], [1, 2]) = [1,2]

getIntersection([3], [1, 2]) = [0]

Understanding the problem​

This problem is basically asking us to find elements that exist in both arrays.

My instinct was to traverse through each array and store a hit when we find elements that are in both.

But we can go simpler than that.

We can assume that if we iterate through one of the input arrays and check for matching elements in the other, that we will have all of our results. This is because if the items in array a are not in our b iteration items then they don't exist.

So all we need to do is loop array b, check if array a contains the item in question. If it does then we have a matching item. Any other items in array a wont be scanned but they dont have a corresponding element in array b anyway.

Code​

function getIntersection(arr1: number[], arr2: number[]): number[] {
  const result = new Set<number>();
  for (let n of arr2) {
    if (arr1.indexOf(n) !== -1) {
      result.add(n);
    }
  }
  return [...result];
}

Code Explanation​

This code is pretty self explanatory.

Key takeaways​

1. The time complexity is still O(n) as we have to iterate through n items of arr2. But we aren't looping through both or doing any crazy result iterations after array iterations.

The problem statement​

The jungle must be too overgrown and difficult to navigate in vehicles or access from the air; the Elves' expedition traditionally goes on foot. As your boats approach land, the Elves begin taking inventory of their supplies. One important consideration is food - in particular, the number of Calories each Elf is carrying (your puzzle input).

The Elves take turns writing down the number of Calories contained by the various meals, snacks, rations, etc. that they've brought with them, one item per line. Each Elf separates their own inventory from the previous Elf's inventory (if any) by a blank line.

In case the Elves get hungry and need extra snacks, they need to know which Elf to ask: they'd like to know how many Calories are being carried by the Elf carrying the most Calories. In the example above, this is 24000 (carried by the fourth Elf).

Find the Elf carrying the most Calories. How many total Calories is that Elf carrying?

Examples:​

For example, suppose the Elves finish writing their items' Calories and end up with the following list:

1000
2000
3000

4000

5000
6000

7000
8000
9000

10000

This list represents the Calories of the food carried by five Elves:

The first Elf is carrying food with 1000, 2000, and 3000 Calories, a total of 6000 Calories. The second Elf is carrying one food item with 4000 Calories. The third Elf is carrying food with 5000 and 6000 Calories, a total of 11000 Calories. The fourth Elf is carrying food with 7000, 8000, and 9000 Calories, a total of 24000 Calories. The fifth Elf is carrying one food item with 10000 Calories.

Understanding the problem​

When you read the question a few times, don't make the same mistake that I did.

It's asking for us to return the HIGHEST NUMBER OF CALORIES not the index of the elf which has the most calories.

To do that we know this:

1. If we split this input by empty line we can get an array of elves.
2. We can then split each item in our array by new line to get each value.
3. Then we can add up the total amount for each elf.
4. As we go through the array, keep track of the highest calories.
5. Return the highest amount.

Let's see how we do that in code.

Code​

function elfCarryingMostCalories(input: string) {
  // split the input by blank lines and begin reducing the array.
  return input.split("\n\n").reduce((acc, curr, index) => {
    // iterate each elf via its array elem, split the array by new line to get each calorie row for that elf. Grab the total.
    const calories = curr
      .split("\n")
      .reduce((acc, curr) => acc + Number(curr), 0);
    // if the elf has a higher amount of calories than the existing highest amount, override it.
    if (calories > acc) {
      acc = calories;
    }
    return acc;
  }, 0);
}

Code Explanation​

This code is pretty self explanatory.

Key takeaways​

1. Array reduce to the rescue! Also you can get the index from reduce. Didn't know that before!