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 to better understand what I needed to generate and it gave me an essential opportunity to spot patterns, which I did.

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];
        
        // wrap all previous entries in parens and put those in the set
        result.add("("+combo+")");
        
        // 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

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.