The problem statement​

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Examples:​

Example 1:

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"

Output: false

Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "

Output: true

Explanation: s is an empty string "" after removing non-alphanumeric characters.

Since an empty string reads the same forward and backward, it is a palindrome.

Understanding the problem​

So lets breakdown how we would tackle solving this problem:

1. Initialize two pointers, one at the beginning of the string, second at the end of the string.
2. Check whether or not the current pair of characters is identical.
3. If they are not identical, return false. Otherwise move both pointers by one index towards the middle.
4. Keep traversing them toward the middle until the pointers meet.
5. If we reach the middle of the string without finding a mismatch, return true.

This is a common technique that the problem is asking us to leverage. Called 'two-pointers'. It can be used for a wide range of problems.

Lets see how we can use it below...

Code​

function isPalindrome(s: string): boolean {
  // We need to strip out all special chars, and lowercase the string.
  s = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  // setup our pointers.
  let left = 0,
    right = s.length - 1;
  // while the pointers haven't met each other in the middle.
  while (left <= right) {
    // If the character at left does not match right, then it's not a palindrome.
    if (s[left] !== s[right]) return false;
    // Increment / Decrement pointers as the chars match.
    left++;
    right--;
  }
  // We made it through the while statement. So it's a palindrome!
  return true;
}

Code Explanation​

This code is pretty self explanatory.

Key takeaways​

1. This pattern of using two pointers is quite a common one, so it would be good to learn it further to apply it more widely.

The problem statement​

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Examples:​

Example 1:

Input: word1 = "abc", word2 = "pqr"

Output: "apbqcr"

Explanation: The merged string will be merged as so:

word1: a b c

word2: p q r

merged: a p b q c r

Example 2:

Input: word1 = "ab", word2 = "pqrs"

Output: "apbqrs"

Explanation: Notice that as word2 is longer, "rs" is appended to the end.

word1: a b

word2: p q r s

merged: a p b q r s

Example 3:

Input: word1 = "abcd", word2 = "pq"

Output: "apbqcd"

Explanation: Notice that as word1 is longer, "cd" is appended to the end.

word1: a b c d

word2: p q

merged: a p b q c d

Understanding the problem​

This problem is asking us to take two words and build a new one from iterating each char at the same position in both words and merge them together.

Code​

function mergeAlternately(word1: string, word2: string): string {
  const chars = [];
  // Loop over the max word length
  for (let i = 0; i < Math.max(word1.length, word2.length); i++) {
    // if the index is in bounds of word1 push that char first
    if (i < word1.length) chars.push(word1[i]);
    // if the index is in bounds of word 2 push that char secondly
    if (i < word2.length) chars.push(word2[i]);
    // this will also allow for the example where one word is longer than the other.
  }
  // return the array as a string.
  return chars.join("");
}

Code Explanation​

This solution is pretty simple and well documented. See above.

Key takeaways​

1. Remember the data we get give in our inputs, like in this example we can iterate over both by using Math.max() to get the largest word length and traverse the array accordingly.
2. Keep it simple wins.

The problem statement​

Given the head of a singly linked list, reverse the list, and return the reversed list.

Examples:​

Example 1:

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]

Output: [2,1]

Example 3:

Input: head = []

Output: []

Understanding the problem​

In a linked list you will normally have a structure that looks like:

class Node {
  val: number;
  next: Node | null;

  constructor(val?: number, next?: Node | null) {
    this.val = val;
    this.next = next;
  }
}

We need to take the numbers from the examples in the array and imagine them packaged up into a node. Then just simply reverse.

Steps to process the problem:

1. A list node at the tail of a list will have a next val of null.
2. Recursion can help us traverse through the array and work backwards.

Code​

function reverseList(head: Node | null): Node | null {
  // If the incoming node is null, just return out.
  if (!head) return head;

  // create a new func that we can recursively call.
  // curr, is our current node to process. Parent is the prev node processed.
  function reverse(curr: Node, parent: Node | null) {
    // set a next pointer.
    const next = curr.next;
    // override the value of curr to have a new next value set to the prev node. This starts our reversal.
    curr = new ListNode(curr.val, parent);

    // if we have no forward looking next node, just return our current one as we are at the tail.
    if (!next) return curr;
    // else process the next node, with the prev node as the one just processed.
    return reverse(next, curr);
  }
  // start the reversal process at head.
  return reverse(head, null);
}

Code Explanation​

Visually this code allows us to do the following:

1. reverse({1, 2}, null)
   1. reverse({ 2, 3}, 1)
      1. reverse({ 3, 4}, 2)
         1. reverse({ 4, 5}, 3)
            1. reverse({ 5, 4}, null) <- this gets returned at the end.

Key takeaways​

1. Recursion isn't limited to the function that they provide. Be creative with inner functions or make use of closure to make recursion work for your solution.
2. I struggle with visualising recursion and how it will progress through. I should find some resources to help with that.

The problem statement​

Given an object or array obj, return a compact object. A compact object is the same as the original object, except with keys containing falsy values removed. This operation applies to the object and any nested objects. Arrays are considered objects where the indices are keys. A value is considered falsy when Boolean(value) returns false.

You may assume the obj is the output of JSON.parse. In other words, it is valid JSON.

Examples:​

Example 1:

Input: obj = [null, 0, false, 1]

Output: [1]

Explanation: All falsy values have been removed from the array.

Example 2:

Input: obj = {"a": null, "b": [false, 1]}

Output: {"b": [1]}

Explanation: obj["a"] and obj["b"][0] had falsy values and were removed.

Example 3:

Input: obj = [null, 0, 5, [0], [false, 16]]

Output: [5, [], [16]]

Explanation: obj[0], obj[1], obj[3][0], and obj[4][0] were falsy and removed.

Understanding the problem​

This problem is asking us to filter out any values within a multi-dimensional array / object that evaluate to false. A few things to note:

1. An array with values equals true in a Boolean() consumption.
2. 0 evaluates to false along with null, undefined etc.

Recursion is going to be the method of choice here to solve this particular problem.

We know from the type provided that the input to the func will be an array or an object. So we can safely assume that we can recursively call this func with any value that we might need.

We will need to differentiate between whether the input is an array or an object as there will be a different process of returning either of them. I.e. array.push vs obj[key] = val.

Code​

type JSONValue =
  | null
  | boolean
  | number
  | string
  | JSONValue[]
  | { [key: string]: JSONValue };
type Obj = Record<string, JSONValue> | Array<JSONValue>;

function compactObject(obj: Obj): Obj {
  // If the incoming obj is an array, only return those where Boolean is true
  // A sub-array is true.
  // Else just set data is the key-value object.
  const data = Array.isArray(obj) ? obj.filter(Boolean) : obj;

  return Object.keys(data).reduce(
    (acc, key) => {
      const value = data[key];
      if (Boolean(value)) {
        // if we have an object which can be a key-value obj or array in js, then recursively call ourselves. Else just set the value for the position.
        acc[key] = typeof value === "object" ? compactObject(value) : value;
      }
      return acc;
    },
    Array.isArray(obj) ? [] : {}
  );
}

Code Explanation​

The approach:

1. Set a const called data, its value is based upon whether the input param obj is an array or not. If it is an array, we run the filter prototype on the array to get rid of all values which are falsy. Else we just return the key-value based object.
2. We then create a new array using Object.keys, for an array input to Object.keys it will simply give you the values. For an object input it will give you all the keys.
   1. Then we perform the reduce prototype on the array
      1. If obj is an array then the initial value is set to [] else its set to an empty {}.
   2. We then get the value iterated by looking up data by the key index from Object.keys;
   3. If that value is true, then we set the value in our accumulator at index key to either be a recursively called instance of ourself if value is an object (which in js can mean an object or array), or simply the value in question which could be a primitive such as string, number etc.
   4. Then we return the accumulated response (our resulting array or object).

This allows us to perform a depth first traversal through data to process any sub-arrays / objects, bubbling up their results so we iterate logically over each index at a time.

Key takeaways​

1. Boolean() can result in true for arrays, numbers etc.
2. Array.reduce is a really helpful tool for processing / transforming arrays and objects. Gives a nice alternative to map().
3. When thinking about composing a recursion based solution. Think of implementing your function at the bottom node upwards. I keep approaching these problems with a top downwards mindset and end up over-engineering it and getting lost. It boils down to results bubbling up from the bottom and how they then get processed further up.

The problem statement​

Given a multi-dimensional array arr and a depth n, return a flattened version of that array.

A multi-dimensional array is a recursive data structure that contains integers or other multi-dimensional arrays.

A flattened array is a version of that array with some or all of the sub-arrays removed and replaced with the actual elements in that sub-array. This flattening operation should only be done if the current depth of nesting is less than n. The depth of the elements in the first array are considered to be 0.

Please solve it without the built-in Array.flat method.

Understanding the problem​

This problem is basically asking us to do a depth-first search of the 2d input array. It wants us to recursively traverse through the array, spreading the results of inner arrays until we get to a certain depth.

We will need to make sure that the solution we choose, keeps a pointer to the current depth.

Code​

type MultiDimensionalArray = (number | MultiDimensionalArray)[];

const flat = (arr: MultiDimensionalArray, n: number) => {
  // if n is 0, the instructions tell us to just return it as is.
  // But also, if we hit a depth of 0 whilst recursively traversing,
  // we want to make sure that we just return it as is.
  if (n === 0) return arr;

  const res: MultiDimensionalArray = [];
  for (const item of arr) {
    // If it's an array, we want to recursively call flat but
    // updating n to reflect our depth relative position.
    if (Array.isArray(item)) {
      res.push(...flat(item, n - 1));
    } else {
      // if its not an array we just want to add the number to the resulting array.
      res.push(item);
    }
  }
  return res;
};

Code Explanation​

The approach:

1. Add our n = 0 case to just return arr;
2. Loop through the current array.
   1. When we find an item that is a number, push that number to our resulting array.
   2. When we find an array, recursively call flat and spread the results into our resulting array. It wont affect nested arrays if we build up any during our recursive calls that exceed the n depth. This is because the spread operator is just spreading the parts which aren't out of our n bounds.
3. Return the resulting array.

Key takeaways​

1. Array.isArray is a useful helper method!
2. Recursion recursion recursion!

The problem statement​

Given two arrays arr1 and arr2, return a new array joinedArray. All the objects in each of the two inputs arrays will contain an id field that has an integer value. joinedArray is an array formed by merging arr1 and arr2 based on their id key. The length of joinedArray should be the length of unique values of id. The returned array should be sorted in ascending order based on the id key.

If a given id exists in one array but not the other, the single object with that id should be included in the result array without modification.

If two objects share an id, their properties should be merged into a single object:

If a key only exists in one object, that single key-value pair should be included in the object. If a key is included in both objects, the value in the object from arr2 should override the value from arr1.

Understanding the problem​

This problem intends to really throw us off from the start. It gives us a JSONValue type which is just not fit for purpose to solve this problem.

The key takeaways from the problem statement are:

1. From the examples we can derive that the ids are in numerical order across arr1 and arr2.
2. If the id is in both arr1 and arr2, choose the value from arr2.
3. If the id is only in arr1 / arr2, just set that value.

Quite simple, but the instructions make it sound so much more complex and the example type is designed to throw you off.

Code​

type JSONValue =
  | null
  | boolean
  | number
  | string
  | JSONValue[]
  | { [key: string]: JSONValue };

function join<T extends { id: number }>(arr1: T[], arr2: T[]): T[] {
  const res = {};
  for (const item of arr1) {
    res[item.id] = item;
  }
  for (const item of arr2) {
    if (res[item.id]) {
      res[item.id] = Object.assign(res[item.id], item);
    } else {
      res[item.id] = item;
    }
  }
  return Object.values(res);
}

Code Explanation​

The approach:

1. Create a hashmap / object to store each id and its corresponding item.
2. Loop arr1 and store all items into this map.
3. Loop arr2
   1. If the item exists in our map, replace it.
   2. If the item doesnt exist, set it.
4. Return the hashmap's values as an array.

We can assume that the arrays are already sorted given the examples provided.

Key takeaways​

1. Remember to use of to iterate object values. Use in to iterate object keys. Arrays are objects.
2. Read examples and understand any information they may leak.
3. Make it work -> make it better.
4. Object.assign is useful for blending two items of the same type. First param is target, second is source. Source will override target.

The problem statement​

Sort By​

Given an array arr and a function fn, return a sorted array sortedArr. You can assume fn only returns numbers and those numbers determine the sort order of sortedArr. sortedArray must be sorted in ascending order by fn output.

You may assume that fn will never duplicate numbers for a given array.

Array prototype last​

Write code that enhances all arrays such that you can call the array.last() method on any array and it will return the last element. If there are no elements in the array, it should return -1.

You may assume the array is the output of JSON.parse.

Understanding the problem​

Sort By​

Please return us a sorted array based upon the values generated via the fn() param, they will never return a duplicate number.

Array prototype last​

The question is asking us within the this scope of the array, please return us the last element or -1 if there are no elements.

Code​

Array prototype last​

Array.prototype.last = function () {
  return this.length === 0 ? -1 : this[this.length - 1];
};

Sort By​

type JSONValue =
  | null
  | boolean
  | number
  | string
  | JSONValue[]
  | { [key: string]: JSONValue };
type Fn = (value: JSONValue) => number;

function sortBy(arr: JSONValue[], fn: Fn): JSONValue[] {
  return arr.sort((a, b) => fn(a) - fn(b));
}

Key takeaways​

1. Prototype functions hold the thing its extending within the this scope.
2. The js sort prototype has a complexity of O(log n).

The problem statement​

Given an array arr and a chunk size size, return a chunked array. A chunked array contains the original elements in arr, but consists of subarrays each of length size. The length of the last subarray may be less than size if arr.length is not evenly divisible by size.

You may assume the array is the output of JSON.parse. In other words, it is valid JSON.

Please solve it without using lodash's _.chunk function.

Understanding the problem​

What the question is asking of us is the following:

Assuming valid inputs, please return a 2D array that contains the passed in array elments but with a maximum size on each inner array of size.

Code​

My initial attempt

type JSONValue =
  | null
  | boolean
  | number
  | string
  | JSONValue[]
  | { [key: string]: JSONValue };
type Obj = Record<string, JSONValue> | Array<JSONValue>;

function chunk(arr: Obj[], size: number): Obj[][] {
  // split the array into an array of mini arrays, max size of x
  const result: Array<Obj[]> = [];
  for (const i of arr) {
    if (result.some((x) => x.length < size)) {
      result.find((x) => x.length < size).push(i);
    } else {
      result.push([i]);
    }
  }
  return result;
}

The most efficient attempt (using js arr prototype)

type JSONValue =
  | null
  | boolean
  | number
  | string
  | JSONValue[]
  | { [key: string]: JSONValue };
type Obj = Record<string, JSONValue> | Array<JSONValue>;

function chunk(arr: Obj[], size: number): Obj[][] {
  const result: Array<Obj[]> = [];
  while (arr.length > 0) {
    // the splice func allows us to remove elements from an array and that array will be updated. So here we remove at index 0, size amounts each time this while loop iterates.
    result.push(arr.splice(0, size));
  }
  return result;
}

Code Explanation​

The first one worked first time round. We just loop the array arr and check if any sub-array within result has a size less than size. If it does we append our value to it. Else we just create a new sub-array with our looped element and add it. Pretty simple. But it's not great from a performance point of view.

The second one works even better. We don't need to scan the 2d result array 2 times per loop iteration. Also we are not looping every single array item. We are just looping chunks of the array at size each time. Resulting in quicker speeds and lower memory usage.

Key takeaways​

1. Splice is a useful prototype to remember. You can add/update/delete elements into an array with splice.
2. Think wider than just for loops when it comes to array problems. Can we utilise a different loop like a while one?

The problem statement​

Given an object or an array, return if it is empty.

• An empty object contains no key-value pairs.
• An empty array contains no elements.

You may assume the object or array is the output of JSON.parse.

Understanding the problem​

The problem seems easy at a glance, but understand whats being asked.

"Please tell us if an object or array is empty"

Fundamentally, arrays in javascript are objects.

Given that, it should highlight the path to take.

Code​

type JSONValue =
  | null
  | boolean
  | number
  | string
  | JSONValue[]
  | { [key: string]: JSONValue };
type Obj = Record<string, JSONValue> | JSONValue[];

// O(n) - we create an array from iterating each item.
function isEmpty(obj: Obj): boolean {
  return Object.keys(obj).length === 0;
}

// O(1) - a for loop can run max once never increases in iteration time
function isEmpty(obj: Obj): boolean {
  for (const _ in obj) {
    return false;
  }
  return true;
}

Code Explanation​

O(1)

When using a for ... in ... we are iterating over the keys of an object. Given that an array is a js object under the hood this allows us to iterate through each key in the array. But when we find one, via a successful iteration we will return false as we know we have an entry.

O(n)

When using the Object.keys func we build up an array of keys from all values in the array. Then we just return the length of that new array.

Key takeaways​

1. Arrays are objects in js, useful to know.
2. The in keyword allows us to iterate an objects keys. Useful in certain scenarios. The of keyword in for loops allows us to iterate an objects values.

The problem statement​

Given an array of integers nums, return the number of good pairs.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Understanding the problem​

When reading the above statement our instinct is to do something like this:

• Loop through nums with i as index
  • Nest loop through nums with j as index
    • if i < j and nums[i] === nums[j]
      • increment a counter
• return total.

This works. But it leaves us with a time complexity of O(n^2) which is exponential and not ideal.

In order for us to understand the better way around this we need to really read into what the question is asking us to do.

1. When we iterate the array, store somewhere the number being iterated and the number of times we have seen that number.
2. As we do that, increment a counter which represents the total number of pairs found.

Lets dive into the code and let the code explain itself

Code​

function numIdenticalPairs(nums: number[]): number {
  // initialise good pairs counter
  let goodPairs = 0;
  // initialise a map to keep track of previous occurences of numbers
  const matches = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    // if our map has the current number
    if (matches.has(nums[i])) {
      // increment good pairs by the number of previous occurences of
      // the number found in the map. i.e. when we first discover a new number
      // we know we have a 1 value of it, so when we see it again goodPairs
      // gets incremented by 1.
      goodPairs += matches.get(nums[i]);
      // then we update the value of the number entry in the map
      // to be incremented by one.
      matches.set(nums[i], matches.get(nums[i]) + 1);
    } else {
      matches.set(nums[i], 1);
    }
  }
  return goodPairs;
}

How It Works​

1. Function Definition: numIdenticalPairs is a function that receives an array of numbers (nums) with the purpose of identifying all identical pairs within the array.

2. Variable Initialization:

   • goodPairs is a counter initialized at 0, used to tally the number of identical pairs.
   • matches is a Map that will store each unique number from the array and how many times it appears.

3. Looping Through the Array:

   • The function uses a for loop to iterate over each number in the nums array.

4. Logic Within the Loop:

   • The function checks if the current number is already in the matches map.
     • If it is, the function increments the goodPairs counter by the amount stored for that number in matches and updates the number's count in matches.
     • If not, the function adds the number to matches with a value of 1.

5. Conclusion:

   • After the loop, the function returns the goodPairs total, which is the count of all good (identical) pairs in the array.

In essence, this function systematically checks each number, keeps track of the frequency of each, and accumulates a total count of identical pairs. It does so efficiently, which makes it particularly effective for large arrays of numbers.

Key Takeaways​

1. Read through a problem and try to think wider than just the default approach. Think outside the box. Truly understand what a simple ask might be after.