DEV Community: Daniil Polovinkin

LeetCode 46. Permutations: Solution Explained

Daniil Polovinkin — Sat, 06 May 2023 20:10:29 +0000

Let's dive into one of the LeetCode problems which is a great example to learn recursive/backtracking approach to solving algorithmic problems. Also we will beat 94% of JS solutions on the site 😉 (at the time of writing).

Problem Description

Courtesy of LeetCode:

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Our constraints are:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Recursive approach

According to LeetCode itself, the problem is suggested to be solved with recursion/backtracking. For recursion-based solution, we have to figure out what is the base case for recursive calls and what is the recursive case. In order for the algorithm to work, we need our recursive case to get to the base case eventually by decreasing the problem size.

Can we apply this approach here?

In this problem all we have is a nums array, so probably we need to shrink the array size, until we hit the base case, and then work our way up, while keeping in mind the fact that we shrunk the array size, we do not want to lose any data. This is where the backtracking part fits in.

Defining the base case

Now, the base case is definitely an array of size 1. Why? Permutations of the [3] array is just [[3]], we know that for certain, there is no need to do any extra operations here. How do we reduce our initial problem to the base case? We could simply go through each element of the array, removing the first element of the array. If we do that, the recursive case should work it's way to the base case. Then we need to handle the results returned by the base case in the recursive case and return the new result.

Defining the recursive case

For example, let us take the array of size 2: nums = [1, 2]. Is there a way to reduce this input to our base case?

If we remove the first element, we get just [2], this is our base case. In order to complete the permutations array, we should add the missing 1 to the permutations returned by the base case, which will get us [[2, 1]]. Then we add the missing 1 back to the nums array, we get nums = [2, 1]. We remove 2, since this is our first element now and get just [1]. This is, again, the base case. Then we add the 2 to the end and get [1, 2]. We merge these results and get [[2, 1], [1, 2]].

If it works for the array of size 2, it should work for an array of any size.

Solution

Our theoretical musings lead us to writing something like this:

var permute = function(nums) {
    const result = [];
    // - Base case
    if(nums.length === 1) {
        // If there's just 1 element, we simply return a copy
        // of that array
        return [[...nums]];
    }
    // - Recursive case
    // We move through each number in `nums`
    for(let i = 0; i < nums.length; i++) {
        // Remove the first element of `nums`
        const n = nums.shift();
        // Now we have reduced the `nums` size to 
        // `nums.length - 1`, this will get us to the
        // base case eventually
        const perms = permute(nums);
        // Traverse through each of the permutations
        // returned by a recursive call
        for(let perm of perms) {
            // We add the number that we shifted earlier
            // to reduce the problem size to the back of
            // the permutation array
            perm.push(n);
            // We add this permutation to the result array
            result.push(perm);
        }
        // Finally, we add the number we shifted back
        // to the array
        nums.push(n);
    }
    // Return the result
    return result;
};

This is just enough to solve the problem! Great job on getting to this point in the post.

But we could go the extra mile here.

Further runtime improvement

What if we make our base case an array of size 2? Figuring out what the permutations of a 2-sized array is pretty straightforward. For example, permutations of [1, 2] are [[1, 2], [2, 1]]. So if we change our base case to an array of size 2, we could get rid of a few extra recursive calls, and save execution time. Recursive case will do its work as is, no changes needed there.

New base case could look like this:

// - Base case
if(nums.length === 2) {
    return [[nums[0], nums[1]], [nums[1], nums[0]]];
}

This should get you to the promised 94%+ runtime result. Enjoy your place on the leaderboard 🥳 .

Conclusion

LeetCode 46 - Permutations - problem is a great example to learn recursive/backtracking approach. We briefly went through the theoretical basis and applied the same logic to this problem.

Of course, all this is just scratching the surface of the exciting world of algorithm design. Want more depth? Consider reading these books:

Grokking Algorithms: Aditya Bhargava - great and simple to understand introduction to algorithms;
The Algorithm Design Manual: Skiena, Steven S S. - amazing in-depth guide to algorithm design, it has answers to all your questions on this topic.

Speeding up your development with Webpack 5 HMR and React Fast Refresh

Daniil Polovinkin — Thu, 18 Feb 2021 12:15:11 +0000

Part One: Phonecalls

Recently I have received a phone call on my answering machine from my manager: I was assigned to work on a legacy project. It was not a very complex task, but still rather time-consuming. I started working on it with a "quick in-and-out" attitude, not intending to do any serious changes to the project. However, as time went on, I realized that I am spending a lot of time repeating the actions required to get to the UI component I was working on after the page refreshes after a code change. Every project I usually work on has at least HMR setup, but here I was faced with a reload after the slightest CSS change. So I decided to dig in and get HMR and React fast-refresh up and running in order to speed up the process.

Part Two: Questions

What even is HMR and React Fast Refresh?

Let's start with the first one - HMR or Hot Module Replacement. This is a feature of webpack which has been around for quite some time now, it is enabled by default in a popular bootstrapping package create-react-app. It enables your app to swap modules while it is running (the "Hot" of "HMR"), without a full page reload and losing the app's state. However, it is hard to retain the state of a module when it is something complex, like a stateful React component. That is why a group of wonderful people developed React Fast Refresh.

React Fast Refresh is a younger cousin of another similar feature - Hot Reloading, but it is officially supported by React and is stated to be more reliable on its README page. Now, is it possible that someone blatantly lied in the README file? I know I did that a few times, but from my experience, this is not the case with react-refresh. It handles even very complex component changes very well. Once again, projects set up with create-react-app@^4.0.0 have it enabled by default.

Part Three: Connections

The project that I was assigned to work had an outdated webpack and react version so I went ahead and updated react to ^17.0.0 and webpack with webpack-dev-server to ^5.0.0.

Disclaimer

While working on legacy projects you have to be aware of the risks that you are taking when making large changes to the codebase (like updating the bundler and core framework to the next major version). If you do not have automated tests set up or do not have enough QA resources to thoroughly test the software after such an update, I strongly urge you to consider other options if it is possible.

After fixing a number of dependencies issues and seeing a green light on my CI dashboard, I proceeded to set up HMR and React Fast Refresh.

Setting up HMR

Packages used

Package	Version
`webpack`	`^5.0.0`
`react`, `react-dom`	`^17.0.0`

This one could be as simple as slightly editing your devServer section of webpack.config.js:

...
  devServer: {
    ...
    hot: true,
    ...
  },
...

This line tells your webpack-dev-server to enable HMR. The last step is enabling webpack.HotModuleReplacementPlugin. You could do that in the config file manually, but I suggest you to take a safer route and add --hot to your package.json start (or whatever name you prefer to run your project in development mode) script to make sure that the plugin is used only in the development environment:

...
  "scripts": {
    ...
    "start": "webpack serve --mode=development --hot",
    ...
  },
...

That should do it in most cases and you are set up with flawless reloading of CSS and other assets without any extra work. However, editing a React component will probably result in a full page refresh, and all the app state is still lost.

Setting up React Fast Refresh

Disclaimer

This part uses an experimental webpack plugin that might not handle unknown edge cases. From my personal experience, I have had no issues with it at the time of writing. Still, proceed with caution.

Packages used

Package	Version
`webpack`	`^5.0.0`
`react`, `react-dom`	`^17.0.0`
`babel-loader`	`^8.2.2`

The react-refresh npm package that I mentioned earlier is intended to be used by bundler authors. If you want to enable React Fast Refresh in your project, you should check out the react-fast-refresh-webpack-plugin. There is an extensive installation and setup guide, but I will go through these steps here as well.

Its setup is a bit more complex than HMR, but should not be a big problem anyway. First of all, you need to install all the required dependencies:

yarn add -D @pmmmwh/react-refresh-webpack-plugin react-refresh

There are 2 parts of enabling this feature:

Adding the react-refresh/babel to babel-loader plugins.
Adding the react-refresh-webpack-plugin to webpack plugins.

Same as with HMR, enabling React Fast Refresh on production is a huge vulnerability, we need to make sure it is enabled only in the development environment. webpack@^5.0.0 strongly suggests using a --mode parameter, so we could use its value as the source of truth to enable the plugins when necessary. To get the --mode parameter value we need our webpack config file to export a function, so you can just wrap your existing config in an arrow function like this:

// the first parameter in a function
// webpack config is "env" [1]
// which is not used in this example
// so its name is set to "_" to indicate
// that a parameter is being passed, 
// but we do not use it
module.exports = (_, argv) => {
  const mode = argv.mode;
  const isDevelopment = mode === "development";
  return {
    ...
    // your existing webpack configuration
    ...
  }
};

^{[1] - More information about the env parameter available in webpack docs.}

Now that we have the handy isDevelopment constant, we can edit the rule for loading JS files to conditionally include react-refresh/babel:

...
  rules: [
  {
    test: /\.js$/,
    ...
    use: {
      loader: "babel-loader",
      options: {
        plugins: [
          // this code will evaluate to "false" when 
          // "isDevelopment" is "false"
          // otherwise it will return the plugin
          isDevelopment && require("react-refresh/babel")
        // this line removes falsy values from the array
        ].filter(Boolean),
      },
    },
  },
...

Then onto the webpack's plugins section:

...
  plugins: [
    ...
    isDevelopment && new ReactRefreshWebpackPlugin(),
    ...
  ].filter(Boolean),
...

Now that we have both parts set up, you should have React Fast Refresh in your project in development mode.

Part Four: Answers

Now, whenever I start the project with the following command:

webpack serve --hot --mode=development

I enjoy the development process with as few page reloads as possible, so I can instantly see the changes I made in the code immediately take effect in the app. This made the time-consuming task I was assigned with way less time-consuming and a bit more fun.