LeetCode 22: Generate Parentheses solution, TypeScript

This summer I took a break from side projects and gave LeetCode a try. It’s been nearly 3 years since my data structures and algorithms course with OSU, so I wanted to give myself a refresher on solving these kinds of problems.

This particular problem, “Generate Parenthesis“, was challenging for me at first but I revisited it a couple times over the summer and on the most recent try, I developed a solution that I think is fairly simple to understand, so I wanted to share it here. (I admit it’s not the most performant solution, but it passes.)

The premise

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

1 <= n <= 8

My solution

I started this problem by writing out what would be generated when n =1, when n = 2, when n = 3, and when n = 4. This step helped me see what I needed to generate and it gave me an opportunity to spot patterns.

When n = 0
result = [""]

When n = 1
result = ["()"]

When n = 2
result = ["()(), (())"]

When n = 3
result = ["()()()","((()))","()(())","(())()"]

When n = 4
result = ["()()()()","(((())))","(()(()))","((())())","()((()))","((()))()","()()(())","()(())()","(())()()"]

The pattern:

I noticed that every time I generated a new result, I was building on the previous n value’s result array.

Specifically, the steps are:

  1. Take each result in the previous n value’s array and wrap it in parentheses. Each of those “wrapped” results becomes part of the new n value’s results array.
  2. Take each result in the previous n value’s results array and insert a new “()” at each possible location in the string. Each of those “inserted” results becomes part of the new n value’s results array.

You might realize at this point that some duplicate results will be generated during this process. This is why I put the results into a Set (so that duplicates are ignored).

Here is this approach, written in TypeScript:

function generateParenthesis(n: number): string[] {
    if (n === 1) { return ["()"]; }
    
    let result = new Set<string>();
    let previousCombos = generateParenthesis(n-1);
    
    for (let i in previousCombos) {
        let combo = previousCombos[i];
        
        // now step through each one and embed a new paren at each possible position
        for (let i = 0; i < combo.length; i++) {
            result.add(combo.substring(0,i) + '()' + combo.substring(i));
        }
    }
    
    return [...result];
};

View as a gist on Github

Runtime analysis

Honestly, I don’t fully understand the runtime on this one, since it’s recursive and since each subsequent step draws from a growing list of “previous step” solutions. It “feels” exponential, but it’s not quite – or at least, the quantity of results in the sets that I worked out by hand is not increasing exponentially.

Pressed to come up with something, I’d say it’s O(2n) because:

  • We have to “handle” every 1…n (that’s the first n)
  • And every time we “handle” an n, we have to produce n * x results, where x is the length of the previous n’s results and that length grows (considerably) with each step.

From this article, “The growth curve of an O(2n) function is exponential – starting off very shallow, then rising meteorically.”

Hey, that sounds like this problem… right?

(If you know how to figure this one out with greater accuracy I’d love to hear it in the comments.)

Performance

[Update] 1 year later: a dynamic programming solution

November 2022 – I showed this blog to a friend and he developed a neat solution that builds a 2D array where each index holds all of the previous step’s calculations. What’s clever about this solution is that it does not generate duplicates the way my Set-based solution above does.

function nextPermutation(previousPermutations: string[][]): string[] {
    const nextPermutationsLength = previousPermutations.length;
    let nextPermutations = [];
    for (let i = 0; i < nextPermutationsLength; i++) {
        // each of the previous permutations becomes our "inner" permutations (array)
        const innerPermutations = previousPermutations[i];
        
        // calculate how many outer permutations we need based on where we are in the loop
        const outerPermutationsLength = nextPermutationsLength - 1 - i; 
        
        // grab from that position to get "outer permutations"
        const outerPermutations = previousPermutations[outerPermutationsLength];
        
        //  now that we have the outer permutations, step through them...
        let newPermutations = outerPermutations.flatMap(outer => innerPermutations.map(inner => `(${inner})${outer}`));
        newPermutations.forEach((newPerm) => {
            nextPermutations.push(newPerm);
        })
    }
    
    return nextPermutations;
}

function generateParenthesis(n: number): string[] {
    let result = [[""]];
    
    for (let i = 1; i < n+1; i++) {
        // push the array of new permutations into the result array 
        result.push(nextPermutation(result));
    }
    
    // result[n] now holds the array we need... 
    return result[n];
};

View as a Gist on Github

Leetcode 1101: The Earliest Moment When Everyone Become Friends solution, TypeScript

The premise:

In a social group, there are n people, with unique integer ids from 0 to n-1.

We have a list of logs, where each logs[i] = [timestamp, id_A, id_B] contains a non-negative integer timestamp, and the ids of two different people.

Each log represents the time in which two different people became friends.  Friendship is symmetric: if A is friends with B, then B is friends with A.

Let’s say that person A is acquainted with person B if A is friends with B, or A is a friend of someone acquainted with B.

Return the earliest time for which every person became acquainted with every other person. Return -1 if there is no such earliest time.

Example test case:

Input: logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], n = 6
Output: 20190301

My solution, in Typescript:

function earliestAcq(logs: number[][], n: number): number {

    // sort the logs by timestamp (earliest first)
    logs.sort((a:number[], b:number[]) => {
       return (a[0] - b[0]);
    });

    // this map is going to serve as a container for all the sets
    let mapOfSets = new Map();
    
    // put every friend ID into its own individual set
    for (let i = 0; i < n; i++) {
        let individualSet = new Set();
        individualSet.add(i);
        mapOfSets.set(i, individualSet);
    }
    
    // now every friend is its own set in the map 
    // console.log(mapOfSets);
    
    // step through the logs and join the sets as matches are encountered 
    for (let i = 0; i < logs.length; i++) {
        let friendA = logs[i][1];
        let friendB = logs[i][2];

        // friendA and friendB have "met" - get their sets
        
        let setA = mapOfSets.get(friendA);
        let setB = mapOfSets.get(friendB);
        
        // and if their sets are not equal...
        if (setA != setB) {
            // join the two sets by adding all of the friends from setB to setA
            for (let friend of setB) {
                // add all the friends from setB to setA
                setA.add(friend);
                
                // update map of sets such that setA is pointed at by each friend originally from B
                mapOfSets.set(friend, setA);
            }
            
            if (setA.size === n) {
                // every friend is now accounted for in set A
                // return the timestamp where this was achieved
                return logs[i][0];
            }
        }
    }
    
    return -1;
};

View as a gist on GitHub

My solution, explained:

  1. Sort all the inputs by timestamp so the earliest ones are first
  2. Create a new map and fill it with sets representing the currently known friendships. The keys will be the friend “ID numbers”, and the values will be the sets representing who that friend is friends with. In the beginning, a friend is only friends with themselves. mapOfSets = {0:{0}, 1:{1}, 2:{2}, 3:{3}, 4:{4}, 5:{5}}
  3. Now, step through the logs and grab each friend pair (friendA and friendB) from that log.
  4. Get the set associated with friendA, and the set associated with friendB, and see if they’re identical
  5. If the sets are not identical, copy all the friends from setB to setA and for each of those relocated friends, update their own value in the mapOfSets to point at setA
  6. If setA becomes equal in size to n (the number of friends), then this is the moment where “everyone knows everyone else” and we can return the timestamp of the current log

Runtime analysis:

O(n log n) due to the sorting

Performance:

Ehh, I doubt this was the absolute best way to do this – it’s just because so few other Typescript submissions exist.

React – Fixing a flickering video that gets redrawn every time something on the page changes

In this post: Fixing a video preview that gets restarted and redrawn every time React redraws the page.

Key words: React, HTML video flicker, DOM redraw React, useMemo

First, an example of the problem:

(This is painful to look at. That’s why we’re going to fix it!)

This is a form that allows the user to upload a video and add a message. But every keystroke was causing the video preview to redraw!

Yikes indeed.

Originally, the <video> tag was part of the React component’s return, like this. On every state change (in this case, the contents of the text area changing), the whole DOM was getting redrawn, video and all.

return (
  ...
  // lots of stuff omitted for brevity 
  ...
  {fileType === 'video' &&
    <Row justify="center">
      <video src={videoURL}
        className="photo"
        preload="auto"
        controls
        style={{height: '95%', width: '95%'}}
      />
    </Row>
  }
  ...
)

I started Googling things like “React video flickers when updating a form” and “React redraws video preview too often” and eventually landed on this helpful tutorial, Getting the heck out of React, which helped me understand the problem better, but the author’s examples were written for an older (2018) version of React and I got lost trying to adapt them to my project. (My React journey only began a few months ago and it seems a lot has changed since the “older” tutorials were written).

I knew there had to be something, but I couldn’t find it by describing my problem to Google, so I explained it to a friend who has more React experience and he pointed me at the useMemo hook, which the docs describe as follows:

Pass a “create” function and an array of dependencies. useMemo will only recompute the memoized value when one of the dependencies has changed. This optimization helps to avoid expensive calculations on every render.

reactjs.org

Okay, that sounded promising. But I still didn’t know how to use it, and the method signature example just exists in a vacuum.

const memoizedValue = useMemo(() => computeExpensiveValue(a, b), [a, b]);

The method signature sets it to the value of a const, but I didn’t know where to put this const or what to have it return, so I went looking for more examples of useMemo.

This tutorial (written in April 2020) was fresh and full of examples. My key takeaways about useMemo were:

  • useMemo doesn’t have to return a function that takes parameters (maybe I’m just a newbie, but seeing the (a, b) in the signature made me think it was going to act like a .sort() callback)
  • useMemo can return JSX instead of a function (JSX being HTML created by JavaScript or TypeScript), which means it can also return React components
  • useMemo has a dependency array like useEffect, and it will run the function it’s attached to if something in that dependency array changes
  • If the dependency array is present but empty, it will compute once on page load and then never again (which isn’t what I want, since the video preview is meant to be set/updated by the user)
  • If there is no dependency argument at all (no array), it will compute every render (which would defeat the purpose of useMemo, so I knew my use case would have to including something in the dependency array)

For my use case, I created a new const, renderVideo, that uses useMemo and placed it above the return (...) but still within the component that makes up the page. The function called by useMemo returns the markup (containing the <video /> tag) that should only redraw when selectedFile changes. Then, where the <video /> markup used to be, I replaced it with a call to renderVideo instead.

The code explains it best:

    const renderVideo = useMemo(() => (
        <Row justify="center">
            <video src={getImageAsUrl()}
                className="photo"
                preload="auto"
                controls
                style={{height: '95%', width: '95%'}}
            />
        </Row>
    ), [selectedFile])

    return (
      ...
      {fileType === 'video' &&
        renderVideo
      }
      ...
    )

(Note: no parenthesis or curly brackets are needed around renderVideo)

It was that simple!

I think I ran in circles for a little while on this one because:

  1. I didn’t know about useMemo, and once I did,
  2. I didn’t realize useMemo could be used for just returning some boring old JSX (HTML markup, basically) that simply has to remain static until a state variable changes – no comparisons or logic calculations needed

Anyway, I hope this helps someone else fix a flickering video or avoid an expensive recalculation on every React redraw!

Additional notes

Notes and observations that didn’t fit elsewhere…

Note #1: the reference to the const can’t be wrapped in any other HTML tags

I had some initial trouble with this technique because I had additional HTML tags around renderVideo. The call to the useMemo const has to be the only thing after the &&.

For example, it does NOT work if you do this:

  // bad idea, does not work!

  {fileType === 'video' &&
    <div className="videoStyling">
      renderVideo
    </div>
  }

Note #2: Using this technique with a component. I later refactored the video preview stuff into its own component, which looks like this:

VideoPreview.tsx

import React from 'react';
import Row from 'shared/components/Row/Row';

interface IVideoPreview {
  videoSrc: string
}

const VideoPreview: React.FC<IVideoPreview> = ({videoSrc}) => {
  return (
    <Row justify="center">
        <video src={videoSrc}
            className="photo"
            preload="auto"
            controls
            style={{height: '95%', width: '95%'}}
        />
    </Row>
  )
}

export default VideoPreview;

I updated const renderVideo to use my new <VideoPreview /> component instead:

    const renderVideo = useMemo(() => (
        <VideoPreview videoSrc={getImageAsUrl()}/>
    ), [selectedFile])

React – replacing an asynchronous .forEach() with for…of (and why it’s better that way)

In this post: My investigation into why ESLint didn’t like my .forEach loop and why for...of is the better choice for an asynchronous loop.

Key words: React, TypeScript, loops, JavaScript array iterators, forEach, for let, asynchronous

So there I was, .forEach-ing through some post replies when I noticed the code was triggering an ES-Lint error, no-loop-func:

Line 73:28: Function declared in a loop contains unsafe references to variable(s) 'repliesTotal' no-loop-func

My code seemed to work fine as it was, though.

const processUnreadReplies = async (userPosts: Post[]) => {
  let repliesTotal = 0;
  for await (let post of userPosts) {
    const replyArray: Array<Reply> = await getRepliesToPost(post.pid);
      replyArray.forEach((reply: any) => {
        if (!reply.read) {
          post.unreadReplyCount = (post.unreadReplyCount ?? 0) + 1;
          repliesTotal++;
        }
      });
  };
  setUnreadRepliesTotal(repliesTotal);
}

In English, this is what this code is doing:

  1. It gets all of the user’s posts as userPosts (and they are of type Post)
  2. It loops through each post in userPosts, getting that post’s replies as replyArray
  3. For each reply in replyArray, it checks each one to see if it is read or not by waiting on an asychronous function call
  4. If the reply is not read (reply.read is false), then it increases the post’s unreadReplyCount
  5. When it’s done with the loop, it sets a state variable called unreadRepliesTotal to the total it tallied up during the loop

ES-Lint’s documentation for no-loop-func was informative, but the examples didn’t make it clear enough to me what I had done wrong. Their “don’t do this” examples were "let i = 0, i < n; i++" and do ... while style loops, and I had a .forEach. They also didn’t have anything on the topic of asynchronous loops.

(Could my code be so awful that they didn’t even consider including it as a “do not do this” example? :D )

I decided to investigate.

First, I had to rethink my assumption that .forEach was the preferred ES6 style – maybe it wasn’t always the case, and maybe my case was one of them.

Two helpful (ie: plain English) posts I read while researching this problem:

For...in iterates through the enumerable properties of an object or array, which means it steps through all the X in object[X] or array[X]. You can still use it to access the elements of an array like so:

for (const idx in cars) {
  console.log(cars[idx]);
}

But that a more roundabout way of accessing the array data, and I soon found a more direct approach:

For...of was the next thing I tried and it worked just as well as my .forEach, but the linter liked it better.

const processUnreadReplies = async (userPosts: Post[]) => {
  let repliesTotal = 0;
  for await (let post of userPosts) {
    const replyArray: Array<Reply> = await getRepliesToPost(post.pid);
      for (let reply of replyArray) {
        if (!reply.read) {
          post.unreadReplyCount = (post.unreadReplyCount ?? 0) + 1;
          repliesTotal++;
        }
      };
  };
  setUnreadRepliesTotal(repliesTotal);
}

But why? I went back to the MDN docs and discovered an important tidbit I overlooked earlier:

forEach expects a synchronous function

forEach does not wait for promises. Kindly make sure you are aware of the implications while using promises (or async functions) as forEach callback. 

from the MDN docs on forEach

As far as ESLint could tell from looking at the code, every loop run by .forEach was returning void. Furthermore, using await does not pause the .forEach (I didn’t expect it to pause it, and I don’t need the previous iteration’s result for the next one, but I wanted to make note of that important distinction anyway).

In any case, this seemed like one of those times where the thing appeared to be working to the user, but could be done better and for...of was the preferred approach here. (There are plenty of opinions and debates about this, though.)

In summary

  • Use for...of for asynchronous loops in JavaScript/TypeScript
  • let creates a block-scoped variable, so in the case of my code the let is creating a new “reply” instance for each iteration of the for...of and each “reply” will be an individual reply from the array
  • .forEach() does not wait for asynchronous code to complete, which may not be a problem in your specific use case but ESLint can’t tell that so it flags it as a potential problem
  • await suspends the current function until it is resolved
  • for...of creates an individual function call for each loop, whereas .forEach() counts as one function call for all iterations

So there we have it – a better, ESLint-approved, way of writing an asynchronous loop in TypeScript/JavaScript.

Related