DEV Community: Sebastian Leukhin

Dynamic Programming vs Divide and Conquer

Sebastian Leukhin — Wed, 16 Jul 2025 05:24:44 +0000

Hi there, I think one of the most difficult patterns in the algorithms section is Dynamic Programming (DP). Additionally, DP is similar to Divide and Conquer (DC), but what is the difference?

In this article, I'm gonna share with you:

What is Dynamic Programming
What is Divide and Conquer
What is the difference between them in the examples
Which one to choose
Share my best practices and some templates for them

Definitions

Divide and Conquer - Let's start with the simplest one. It is an algorithm pattern that recursively breaks down a problem into independent sub-problems. The results of all sub-problems are combined to solve the whole problem.

Tips:

Break down a problem
Solve each subproblem independently
Combine the solutions
No overlapping subproblems - each subproblem is solved only once

Dynamic Programming - is an algorithm pattern with an optimization. It also breaks down a problem but into overlapping sub-problems. They share work and can be solved once and reused. "Dynamic Programming" is essentially an optimization technique for "Divide and Conquer" when you have overlapping subproblems. It trades memory for time by storing and reusing solutions to avoid redundant computation.

Tips:

Break down a problem into smaller overlapping sub-problems
Solve each sub-problem once and store the result (Top-Down or Bottom-Up pattern)
Reuse stored solutions
Optimal substructure - optimal solution to the problem contains optimal solutions to sub-problems

Top-Down example

const memo = new Map();
const fibonachi = (n) => {
  if (n <= 1) {
    return n;
  }

  if (memo.has(n)) {
    return memo.get(n);
  }

  const result = fibonachi(n - 1) + fibonachi(n - 2);
  memo.set(n, result);

  return result;
};

Bottom-Up example

const fibonachi = n => {
    let a = 1;
    let b = 1;

    for (let i = 3; i <= n; i++) {
        const c = a + b;
        a = b;
        b = c;
    }

    return b;
};

Differences

Divide and Conquer

QuickSort
Left subarray [from, nextTo] and right subarray [nextFrom, to] are completely separate
Sorting the left subarray doesn't help with sorting the right subarray
No shared work between subproblems

QuickSort([1,5,3,2,4])
├── QuickSort([0,1])     ← Independent
└── QuickSort([2,3,4])   ← Independent
    ├── QuickSort([2])   ← Independent
    └── QuickSort([3,4]) ← Independent

Dynamic Programming

Fibonacci
fib(5) needs fib(4) and fib(3)
fib(4) also needs fib(3) and fib(2)
fib(3) is calculated twice - this is an overlap!

fib(5)
├── fib(4)
│   ├── fib(3) ← Calculated twice
│   └── fib(2)
└── fib(3)     ← Calculated twice
    ├── fib(2) ← Calculated multiple times
    └── fib(1)

Complexity

Time

Divide and Conquer - usually O(n log n) for sorting algorithms
Dynamic Programming - varies by problem, but often O(n²) or O(n³)

Space

Divide and Conquer - minimal extra memory (usually O(log n) for recursion stack, but might be O(1) for in place solutions)
Dynamic Programming - requires additional memory to store solutions (O(n) to O(n²) typically)

Divide and Conquer Best Practices & Template

IDENTIFY if it's a Divide and Conquer problem:
- Can the problem be broken into smaller, independent subproblems?
- Do the subproblems have the same structure as the original problem?
- Can solutions to subproblems be combined to solve the original problem?
- Keywords: "sort", "search", "merge", "conquer", "recursive structure"
DEFINE the divide step:
- How do you break the problem into smaller subproblems?
- What is the size of each subproblem?
- Are the subproblems independent?
FIND the recurrence relation (solution for the each problem):
- What is the base case (smallest subproblem)?
- How do you solve each subproblem recursively?
COMBINE the solutions:
- How do you merge solutions from subproblems?
- What is the complexity of the combine step?

Basic Template:

Divide - break the problem into subproblems
Conquer - solve subproblems recursively
Combine - merge solutions from subproblems
Return result

Dynamic Programming Best Practices & Template

IDENTIFY if it's a DP problem:
- What are we optimizing? (max/min/count/boolean)
- Optimal substructure (optimal solution contains optimal solutions to subproblems)
- Overlapping subproblems (same subproblems are solved multiple times)
- Keywords: "maximum/minimum", "count ways", "longest/shortest", "can we reach", "match"
DEFINE the DP state:
- What does dp[i] or dp[i][j] represent?
- You should easily understand what it means
FIND the recurrence relation (solution for the each problem):
- How does dp[i] relate to previous states?
- What are the transitions between states?
DETERMINE base cases:
- What are the simplest cases we can solve directly?
DECIDE the order of computation:
- Bottom-up (tabulation) vs Top-down (memoization)
- Ensure dependencies are computed before the current state

Basic Template:

Initialize DP structure dp[i] = optimal solution for the first i elements
Set base cases: dp[0], dp[1], etc.
Fill table with recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)
Return answer: dp[n]

Common Patterns: Divide and Conquer

Pattern 1: Array/List Division
Examples: QuickSort, MergeSort, Binary Search
Strategy: Split array into halves or parts

Pattern 2: Tree Division
Examples: Binary Tree Traversal, Tree Height Calculation
Strategy: Process left and right subtrees separately

Pattern 3: Matrix Division
Examples: Strassen's Matrix Multiplication, Matrix Operations
Strategy: Split matrices into quadrants

Pattern 4: Geometric Division
Examples: Closest Pair of Points, Convex Hull
Strategy: Divide space into regions

Pattern 5: String Division
Examples: Palindrome Detection, Suffix Array Construction, Pattern Matching in Chunks
Strategy: Split strings into substrings or process character by character

IMPORTANT: Not all string problems are suitable for divide and conquer! Avoid problems with overlapping subproblems (like LCS, Edit Distance) as they are better solved with Dynamic Programming.

Common Patterns: Dynamic Programming

Pattern 1: Linear DP (1D)
Examples: Fibonacci, House Robber, Climbing Stairs
State: dp[i] depends on dp[i-1], dp[i-2], etc.

Pattern 2: Grid DP (2D)
Examples: Unique Paths, Minimum Path Sum, Edit Distance
State: dp[i][j] depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1]

Pattern 3: Interval DP
Examples: Matrix Chain Multiplication, Palindrome Partitioning
State: dp[i][j] represents the optimal solution for the interval [i, j]

Pattern 4: Knapsack DP
Examples: 0/1 Knapsack, Unbounded Knapsack, Coin Change
State: dp[i][w] represents the optimal solution using the first i items with a weight limit of w

Pattern 5: String DP
Examples: Longest Common Subsequence, Edit Distance, Regular Expression
State: dp[i][j] represents solution for first i chars of string1 and first j chars of string2

That's it, I hope it's helpful, have a nice day 😉

Preparations for trunk-based development - 1st phase

Sebastian Leukhin — Mon, 05 May 2025 18:20:37 +0000

Trunk-based development has been gaining traction as one of the most effective strategies for continuous integration and rapid delivery, especially in big teams. For our team, I don't want to make changes only in the Git branching model — I want to reshape our development culture to support fast feedback, economy resources, and resilience. This is the story of how I researched adding a monorepo tool and cache for my team and what I learned along the way.

Step 1: Understanding the Why

Before proposing to my team to move to trunk-based development, I spent time understanding its core benefits: reduced merge conflicts, efficient CI/CD flows, faster feedback loops, and less overhead around long-lived branches.

Step 2: Audit Our Current Workflow

I reviewed our existing practices, which include multiple long-lived branches, complex merge processes, and weekly releases with release trains. Such practices often result in spending a lot of resources manually merging tasks in waterfall style, manually deploying services, and regressions on the release candidate stage and production environment. Also, such approaches have frequent conflicts and context-switching headaches. Considering that we are moving towards trunk-based development, it is clear that we need a leaner, more collaborative workflow.

Step 3: Introducing the Concept to the Team

Change is hard, and selling a new approach requires empathy. We discussed potential profit, and I researched how much we can optimize in our npm scripts on CI. I considered the most popular solutions, NX and Turborepo.

Step 4: Tooling Up with Nx

We already have a small Lerna setup (now it belongs to NX, and some commands from Lerna just run NX 😀), so I started looking for pros and cons in NX.

Pros

Powerful caching mechanisms
Has a smooth migration from Lerna to NX
Has an interactive dep-graph
Supports a Single version policy
Has an incremental functionality for the scripts via affected
They are in the process of switching to Rust

Cons

Internal vendor libraries for bundling the app: e.g. webpack. You may encounter some locks or their restrictions, also, I don't think it is a good time for us to couple a monorepo tool and a building system.
Can't cache script results in watch mode
Precedent of an attempt to make a remote cache paid by disabling custom task runners. It ended up with a rollback, but precedent is precedent.

Step 5: Tooling Up with Turborepo

Pros

Powerful caching mechanisms
Has an incremental functionality for the scripts via affected
Remote cache is free, and custom task runners are available
It is already on Rust
Time-saved feature and telemetry
Pretty easy to add to your repo without special internal libs for bundling your code

Cons

Non-interactive deps graph, it will be adopted to PlantUML, and you can use its built-in features to visualize the graph, but without interactivity
Supports a "Single version policy" but you need to declare a dependency with asterisks, like:

"dependencies": {
  "react": "*"
}

Example

My result of pet project

Firstly, I tried using NX, and everything was pretty fine until I tried using Turborepo for the same project.

Adding the Turborepo was much easier. Also, when I decided to switch my pet project from webpack to rspack, it took 15-30 minutes. In the end, when I heard about NX's plans to block custom task runners, I decided to use Turborepo for all my stuff and use NX with the simplest configuration only for parsing deps and running an interactive deps graph. The config is really simple for it:

nx.json

{
  "$schema": "node_modules/nx/schemas/nx-schema.json",
  "pluginsConfig": {
    "@nrwl/js": {
      "analyzeSourceFiles": true
    }
  },
  "defaultProject": "@app/entry-point"
}

Run in your console:

nx graph

Ultimately, I got Turborepo without cons for my setup. Pretty simple config at the beginning:

turbo.json

{
  "tasks": {
    "build": {
      "dependsOn": ["^build"],
      "inputs": ["$TURBO_DEFAULT$", ".env*"],
      "outputs": ["./dist/**"]
    },
    "test": {
      "cache": true,
      "inputs": ["$TURBO_DEFAULT$"]
    },
    "lint": {
      "dependsOn": ["^lint"]
    },
    "check-types": {
      "dependsOn": ["^check-types"]
    },
  }
}

And I like that, the tool for my monorepo is not responsible for my tech stack, and it would be worse if it was responsible for bundling my frameworks or libraries that I use. On the opposite side, NX does it.

Eventually, I set up scripts: lint, check-types, and test

lint

Root level:

...
"lint": "turbo run lint",
...

Code

Package level:

"lint": "eslint ."

Code

With a flat ESLint config, it will find and use the root file eslint.config.mjs.

check-types

Root level:

...
"check-types": "turbo run check-types",
...

Code

Package level:

"check-types": "yarn tsc --noEmit",

Code

Here is a simple strategy for tsc to check types.

test

Root level:

...
"test": "export WORKSPACE_ROOT=$(git rev-parse --show-toplevel) && turbo run test -- --config $WORKSPACE_ROOT/jest.config.ts",
...

Code

Package level:

"test": "jest --rootDir .",

Code

Setup is a bit tricky, I run a test script in each package (and use the package as a root dir) and pass down a root config via --config option of jest. Everything works fine except changes in the root jest.config.ts don't trigger turborepo's reset cache. I tried to add the jest.config.ts in inputs, but paths in "inputs" work at the package level. This means Turborepo is looking for jest.config.ts in each package's directory, not at the root. And each package has its nesting. If you know how to add the jest root file in "inputs" to trigger re-run test script in each package after changes in the jest config, pls leave a comment.

Reflections and What’s Next

Switching to trunk-based development won't be without friction, but the payoff will be worth it, I guess. And to simplify the migration process, I want to split it into a few steps.

This is just the beginning, and I’m excited to keep evolving how we build software together.

Literature and Further Reading

Bonus:

Split incremental builds into packages

It might be suitable for you. Split bundling by each package:

Realize the bundling flow for each package (I experimented with tsc and added "start-build": "yarn tsc")
In turbo.json:

"start-build": {
  "dependsOn": ["^start-build"]
},

Before yarn start I ran yarn turbo watch start-build --affected

And I got cacheable results in watch mode for any desirable package 🎉. It's not so suitable for my case, for me it was easier to move to rspack with good compatibility with webpack. I used rspack's internal optimization, incremental builds - here.

Alternative ways without monorepo tools:

For incremental CI, you can use tj-actions/changed-files, find only changed files, and run some scripts with arguments of these files
For lint - use eslint ./files
For jest - use the flag --findRelatedTests
For tsc - a bit more difficult

Text to speech (book to audiobook)

Sebastian Leukhin — Sun, 12 Jan 2025 10:09:28 +0000

Hello everyone! I'm sure each of you has a book you want to read but don't have the time.

Some points off the top of my head:

I have some "simple" books that I can take by listening to them
I'm blocked when I'm reading a book, because I have to put the book or smartphone somewhere, look at it, read it, and it's pretty hard to do anything else
Buy two versions of text + audio or only the audio version might not be suitable for some reasons

After these points in my mind, I just looked around our developed IT world and found the solution with a few lines of code to transform my e-books that I already have into audio format for free.

Solution

It turns out that one of the easiest ways to create audio from a text is with the python library gTTS.

What is gTTS?

gTTS is a Python library that interfaces with Google Translate’s Text-to-Speech API to generate speech from text. It supports multiple languages, and ability to output audio files in MP3 format. gTTS is commonly used in applications like audiobooks, automated announcements, and accessibility tools.

Key Features of gTTS

Language Support: gTTS supports a wide range of languages, allowing users to convert text to speech in English, Spanish, French, and many others
Regional Accents: By specifying the top-level domain (TLD) such as .com, .co.uk, or .co.in, users can influence the accent of the generated speech
Speed Control: The slow parameter allows users to slow down the speech for clarity.

Example: Creating Speech from Text

from gtts import gTTS

# Define the text to be converted
text = "Hello, welcome to the world of text-to-speech."

# Create a gTTS object
speech = gTTS(text=text, lang='en', tld='com', slow=False)

# Save the generated speech to an MP3 file
speech.save("output.mp3")

print("Audio file 'output.mp3' has been saved.")

Ready simple solution

I created the small repo to transform .epub and .fb2 formats to mp3 - text-to-speech

Enjoy your audiobooks! 😉

Building a Codemod Tool for Rewriting Default Exports

Sebastian Leukhin — Tue, 29 Oct 2024 11:40:50 +0000

Recently, at SignNow, we decided to migrate to the named exports/imports and add the eslint rule no-default-export.

Motivation sounded something like:

The default exports can make code harder to maintain, especially in large codebases. Imported names might be different for the same entity, affecting the code reading process and writing static analyzers, making it more difficult. Conversely, switching to named exports removes all the disadvantages of the default exports.

Of course, we have a huge code base and it is not an interesting job to manually replace ~1500 default exports and ~12000 default imports 🤪

The main difficulty was updating all linked files with the same new identifier, created for the named export.

I give you an example:

// Button/Button.tsx
const Button = () => {};
export default Button;

// Button/index.ts
export { default } from './Button.tsx';

// SomePage1.tsx
import OldButton from './component/Button';

// SomePage2.tsx
import TestButton from './component/Button';

And the target result supposed by me would look like this:

// Button/Button.tsx
export const Button = () => {};

// Button/index.ts
export { Button } from './Button.tsx';

// SomePage1.tsx
import { Button as OldButton } from './component/Button';

// SomePage2.tsx
import { Button as TestButton } from './component/Button';

Each solution I found on the internet was just a codemod to transform each file independently without knowing anything else outside that file.

I started dreaming about a parser that would:

resolve all imports in the project and save relations between files
gather information about default import/export
create a new identifier name for the named export
replace all entries across the repo 😇

So I took a new challenge to develop a codemod tool that automatically rewrites default exports/imports to named ones.

spoiler

I already developed it! 🤜 🤛

Development process

First thoughts
It happened right after my previous experiment Visualize react components tree and the first idea was to reuse the babel and webpack plugins to iterate through all modules and parse the AST, but why, if jscodeshift already has the parser, and if I found a replacement for the webpack plugin I would be able to write a bundler-agnostic tool, great 💪

Tools
Ok, I have a jscodeshift as a parser. But to find relations between all files starting from the entry point, I found the resolve package, which helps to resolve paths like native nodejs require.resolve, but it is more similar to resolving paths like bundlers, you have more control over extensions, sync/async behavior, etc.

Engineering the Two-Step Process
The initial version of my tool was like everything in one script. However, to improve flexibility and performance and also simplify the development process with debugging, I refactored the tool into two stages:

Data Collection: The first phase gathers all instances of default imports and exports across the codebase
- I introduced an environment variable, IS_GATHER_INFO, to control this phase. The script uses resolve to find every usage of a default export / import
- Another env var ENTRY contains a relative path to your code base entry point, starting from that file, all imports will be resolved and analyzed
Transformation: Once the data is collected, the second phase rewrites the default exports into named exports. Using jscodeshift, I transformed the source code in parallel and easily.
- I introduced an environment variable, IS_TRANSFORM, to control this phase

By splitting into these two steps:

I was able to decouple data gathering from transformation, reducing the amount of code executed and spent time during development and debugging
- It's a very convenient way to see the gatherInfo function's result, analyze it, rerun your code
- Test transformations without repeatedly running the entire pipeline with the gathering data
Collecting the data dump is helpful if you need to run this tool for different entry points but reuse the collected data

As cases began to accumulate (like dynamic imports, re-exported defaults, different exported entities: variables, functions, and classes, and already used names of variable issues) that time I spent additional time setting up test cases. In around 30 minutes I had a solid testing setup, allowing me to shift to test-driven development (TDD). Trust me, it's worth spending time on TDD for such tools, which have an enormous number of cases. The further you go the more value you feel from your test cases. I would say that after covering half of the cases if you have no tests, it becomes a nightmare to run and debug on a huge project because each time you need to add some changes, it might break a lot of other cases.

AST:
I used the following types of AST nodes:

ImportDefaultSpecifier to find only import default statements
- import something from '...'
ExportDefaultDeclaration to find only export default statements
- export default something;
ExportNamedDeclaration to find import default and export default statements
- export { something as default } from '...' - default export
- export { default as something } from '...' - default import
- export { default } from '...' - default import and default export simultaneously
ImportExpression to find dynamic import and mark that file as needed to preserve the default export. Some tools like React.lazy work with default export only.
- import('...')
Also, I saved info about proxy files, it is files that import default something and export that something as default
- Used it to find the new name of the named export in any file: file a -> file b -> file c

Technical Considerations and Known Limitations
Though the tool is functional, there are some edge cases it doesn't yet handle:

namespace.default usage
the following code won't be transformed yet:

import * as allConst from './const';
console.log(allConst.default);

Conflicts in proxy files
source:

export { Modals as default } from './Modals';
export { Modals } from './Modals';

result:

export { Modals } from './Modals';
export { Modals } from './Modals';

Messed exports like
source:

export class GhostDataProvider {}
export default hoc()(GhostDataProvider);

will result in broken logic, because now it has two same exports with different implementation:

export class GhostDataProvider {}
const GhostDataProviderAlias = hoc()(GhostDataProvider);
export { GhostDataProviderAlias as GhostDataProvider };

And imports for the previous entity should be fixed manually too
source:

// was used to get the class without HOC
import { GhostDataProvider } from '.'
...
// was used to get the class with HOC
import GhostDataProvider from '.'

result:

// now you should manually resolve it to class without HOC somehow
import { GhostDataProvider } from '.'
...
// this will get the class with the HOC
import { GhostDataProvider } from '.'

Despite these limitations, I manually fixed the rest of the errors in 15-20 minutes and successfully spun up our real project. The rewrite-default-exports.

Links

That's it, welcome to the comments below! 👍

Visualize react components tree

Sebastian Leukhin — Tue, 05 Mar 2024 19:06:04 +0000

Hi, today I would like to announce my new library that solved my old idea to get a high view of my react component structure in the project.

When it is useful?:

for newbies on the project
to find unwanted dependencies
to figure out what is happening in the nested subtrees of components

What is it?

It is living here on GitHub
Works with babel and webpack and consists of two plugins: babelPlugin and webpackPlugin
Generates a UML diagram during the build of your project

How it works?

babelPlugin - parsing AST

babelPlugin runs first and uses the AST of each file in your project that is accepted by filter with options packagesPaths and acceptableExts. This plugin uses visitor pattern to traverse AST and utilize the following built-in babel plugin methods:

ImportDeclaration - is used to gather imports that look like component imports within a file - source.

JSXOpeningElement - catches the render of the component and traverses to the parent until it finds the identifier node and after that saves it to the set of identifiers that has the JSX (varsWithJsx) - source.

VariableDeclaration - saves all variable declaration nodes to the set by its name (varDeclarationsByName) - source.

ExportDeclaration - catches the exports and tries to find the original identifier that has JSX by findVarWithJsx. It uses the saved varsWithJsx set and parses VariableDeclarations and CallExpressions to unwrap possible re-assignments like:

// VariableDeclaration
// 1. export const foo = varWithJsx;
// CallExpression
// 2. export default hoc(varWithJsx);

source

Recap:

After the babelPlugin work, we have the JSON file with the maps connectionIdsByFileName (contains fileName -> the array of import names that seem to be component ones.) and exportedIdsWithJsxByFileName (fileName -> the array of exported identifiers that contain JSX).

webpackPlugin - traverse all modules

Runs on the compiler.hooks.done and iterates all modules from compilation that exist in connectionIdsByFileName (gathered by babelPlugin)

resolveConnectionProxyPath - is called for every module to organize the traverse by imported files and to link all modules without a kind of proxy file. The proxy file is the file with the re-export.

Example:

// components/Button/Button.js
export const Button = () => {
...
};

// components/Button/index.js
export { Button } from './Button';

// App.js
import { Button } from './components/Button';

The index.js is a kind of proxy file that we omit and should find a direct link from the App.js to the Button.js file.
Another aspect of this process is that we need to match the component name from the App.js to the component name in the Button.js file.

The result is saved in proxyPathsWithJsx.json file:

[
  "components/Button/index.js",
  [
    ["Button", "components/Button/Button.js"]
  ]
]

Complicated example:

// components/Button/Button.js
export const Button = () => {
...
};

// components/Button/index.js
export { Button as default } from './Button';

// App.js
import Btn from './components/Button';

The result is saved in proxyPathsWithJsx.json file:

[
  "components/Button/index.js",
  [
    ["default", "components/Button/Button.js"]
  ]
]

mapModuleConnectionIds - iterates by all imports in each module (file) to save the following result to the outUmlFileName file (it should have JSON extension):

[
  "/App.js",
  [
    "/Button.js",
  ]
]

The result will be the same for both examples above with different re-exported names of the Button component.

Key ingredient

That's it, right now we have enough data to render the tree of our react components. But if you try to generate a UML diagram with all this data, on the real project it will result in a huge canvas and of course, it will be hard to read the information from it and get profit. Ok, imagine how you would solve this problem with many components. The main idea of a kind of diagram is to get a high-view picture of your system. I could not find any better solution without interactiveness than to omit some excess components from the diagram during the build time. I added the repetitiveCountForRemoveFromTree param to makePlugins (by default it is 4), and I just count the repeating of each component in the diagram and remove them if the number above or equal to the repetitiveCountForRemoveFromTree.

Final stage

Thus in the output we have a UML diagram only with the most valuable component names, they show the main structure of your app. Feel free to adjust the repetitiveCountForRemoveFromTree to an appropriate value for your app to get the desirable picture in the end.
So, try to render it:

java -jar plantuml-1.2023.11.jar ./build/assets/{outFileName}.uml -tsvg -verbose -t4

Enjoy watching your app structure!

What is next?

Once you gathered the data from your code base, just imagine what you could do in the next step. This library right now just organizes the process of traverse, so it is possible to add logic into the library and gather extra data on the way like:

Test coverage for each file and component
Size of your files and components
Component names into files (if you use an approach with multiple components in one file)
Something else
Render it with the interactive like d3.js with the real-time input search filter, and highlights of the arcs when you select one of the nodes

min & max in specified period (sliding window)

Sebastian Leukhin — Sun, 30 Jul 2023 15:21:47 +0000

Hello, today it is time to realize the monotonic stack and when it can be used 😀

First, let's start with the requirements for the task:

Write the function that returns the array of numbers with minimums (or maximums) in each period k.

function gets the array of numbers
k is the length of period

Example:

input: [1, 5, 4, 7, 0]
k: 3

Expected Result:

[1, 4, 0]

Description:

The array: [1, 5, 4, 7, 0] must be split into periods of 3 numbers.
So we get: [1, 5, 4], [5, 4, 7], [4, 7, 0].
And the result must have minimums numbers from each period:
[1, 5, 4] -> 1
[5, 4, 7] -> 4
[4, 7, 0] -> 0

Requirements:

time complexity O(n)
space complexity O(k)

Of course Rules for the code:

Choose the right names for variables
Choose the right loop statements: for, while, forEach, reduce etc.
Avoid excess conditions and comparisons for edge cases
Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity

Write some first assertions to test your function

const compareNumbers = (arr1: number[], arr2: number[]) => {
  return (
    arr1.length === arr2.length &&
    arr1.every((num, index) => {
      return num === arr2[index];
    })
  );
};

console.assert(compareNumbers(getMinimumsFromPeriods([1, 5, 4, 7, 0], 3), [1, 4, 0]));

Your first thought might be about the monotonic stack, or more specifically the min stack. But this is only half true because we should track the period size.

So how can we do that?

Our stack size must not be larger than the period size, because we should store every min value within the period k (i - k), on every step.
We have the right to drop previous values that are greater than the current value. This is because the current value has a larger index and it may be used within the next k steps.

How to use min stack with the period?

We can store not values but indices.
We know the current position of the iteration and the min value index, we can check it every iteration as soon as we get an iteration greater than the period and drop if the min value index is bigger than iterationPosition - period.
We will use the pop method to optimize the change in the array, because of it our min value index will be the first item in the stack.
To drop the stale index we will have to use the shift method.

P.S.
The shift method, which is somehow optimized by the js engine and its complexity can be neglected. Or we can optimize it ourselves (by converting it to an object, for example), but that is beyond the scope of this article.

Possible implementation

const popMinNumFromStack = (arr: number[], stack: number[]) => {
  return arr[stack.shift()!];
};

export const getMinimumsFromPeriods = (arr: number[], period: number) => {
  const minStackIndices: number[] = [];
  const result: number[] = [];

  arr.forEach((num, index) => {
    // drop the values from the stack that are greater than the current value
    while (minStackIndices.length && num <= arr[minStackIndices[minStackIndices.length - 1]]) {
      minStackIndices.pop();
    }
    // save index
    minStackIndices.push(index);
    const position = index + 1;

    // once the position greater period, we must save the min value and drop stale indices at every step if necessary 
    if (position >= period) {
      const min =
        // drop the stale index (greater than the period)
        position - minStackIndices[0] >= period
          ? popMinNumFromStack(arr, minStackIndices)
          : arr[minStackIndices[0]];
      result.push(min);
    }
  });

  // condition for arrays shorter than the period
  return !result.length && minStackIndices.length
    ? [popMinNumFromStack(arr, minStackIndices)]
    : result;
};

Additional assertions

console.assert(compareNumbers(getMinimumsFromPeriods([1, 5, 4, 7, 0], 2), [1, 4, 4, 0]));
console.assert(compareNumbers(getMinimumsFromPeriods([1, 6, 4, 5, 7, 7], 3), [1, 4, 4, 5]));
console.assert(compareNumbers(getMinimumsFromPeriods([0, 8, 6, 4, 3, 1], 3), [0, 4, 3, 1]));
console.assert(compareNumbers(getMinimumsFromPeriods([], 2), []));
console.assert(compareNumbers(getMinimumsFromPeriods([1, 2], 2), [1]));

Let me know your thoughts in the comment section below! 😉

Strings vs Arrays in JS

Sebastian Leukhin — Sat, 04 Mar 2023 13:56:31 +0000

Hey guys, recently I came across the "Design a Text Editor" task on leetcode (hard level). In short, we need to implement the following:

Add text to where the cursor is
Delete text from where the cursor is (simulating the backspace key)
Move the cursor either left or right

Rules for the code (as usual):

Choose the right names for variables
Choose the right loop statements: for, while, forEach, reduce etc.
Avoid excess conditions and comparisons for edge cases
Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity

Strings - version 1

The first thing that might come to mind is manipulating strings.

class TextEditor {
  cursorPosition = 0;
  text = '';

  /**
   * @param {string} text
   * @return {void}
   */
  addText = (text) => {
    this.text =
      this.text.substring(0, this.cursorPosition) + text + this.text.substring(this.cursorPosition);
    this.cursorPosition += text.length;
  };

  /**
   * @param {number} k
   * @return {number}
   */
  deleteText = (k) => {
    const deletedCount = Math.min(this.cursorPosition, k);

    this.text =
      this.text.substring(0, this.cursorPosition - deletedCount) + this.text.substring(this.cursorPosition);
    this.cursorPosition = this.cursorPosition - deletedCount;

    return deletedCount;
  };

  /**
   * @param {number} k
   * @return {string}
   */
  cursorLeft = (k) => {
    this.cursorPosition = Math.max(0, this.cursorPosition - k);

    return this.text.substring(this.cursorPosition - 10, this.cursorPosition);
  };

  /**
   * @param {number} k
   * @return {string}
   */
  cursorRight = (k) => {
    this.cursorPosition = Math.min(this.text.length, this.cursorPosition + k);

    return this.text.substring(this.cursorPosition - 10, this.cursorPosition);
  };
}

Check it out on leetcode.

Sometimes it fails by time limits. But will have a good spot by memory consumption.

Arrays - version 1

Looking at the best time-consuming solution, we will see code that manipulates arrays. And memory usage is good enough too.

Sample code:

var TextEditor = function () {
  this.left = [];
  this.right = [];
};

TextEditor.prototype.addText = function (text) {
  for(var i = 0; i < text.length; i++) {
    this.left.push(text[i]);
  }
};

Conclusion: Big difference in time and almost nothing difference in memory. Why? Let's dive deep into the JS engine.

JS engine

Firstly it depends on the amount of data, in our case we have 2 * 10⁴ operations which is a lot. Also, it depends on the implementation of the JS engine.

The String
It is a primitive data type and as a rule, primitives are immutable, so strings don't change when the developer manipulates the strings. How it works:

let text = 'string';
text += ' changed';
console.log(text);

In the console, we will see the string changed which means our text variable is mutable. But under the hood, the engine just creates a third empty string and copies the values of both strings to it, and assigns the result to the text variable. Therefore, we have mutable the text variable and immutable string data type.

Let's visualize this algorithm:

Create an empty range in memory for the new string. To concatenate our two strings we need to save 14 chars (by 2 bytes).

_ _ _ _ _ _ _ _ _ _ _ _ _ _
Copy the first string

s t r i n g _ _ _ _ _ _ _ _
Copy the second string

s t r i n g c h a n g e d
Assign the result to the var

text = s t r i n g c h a n g e d
Frees memory that was used to hold "string" and " changed" strings.

As you see it takes additional operations than it really needs (it copies each string fully), and at some point in time we have two times more memory. Just open the console and paste the following code:

let str = '';
console.time('experiment');

for (let index = 0; index < 100_000_000; index++) {
    str += 'w';
}

console.timeEnd('experiment');
console.log(str.length);

In my case, it took 9.5 sec. Now try to paste the following one:

let str = [];
console.time('experiment');

for (let index = 0; index < 100_000_000; index++) {
    str.push('w');
}

console.timeEnd('experiment');
console.log(str.length);

In my case, it took 886 milliseconds 😃 great!
Note: This case is only appropriate for inserting in the end of the sequence and if you will try something like:

let str = [];
console.time('experiment');

for (let index = 0; index < 500_000; index++) {
    const middleIndex = Math.floor(str.length / 2);
    str.splice(middleIndex, 0, 'w');
}

console.timeEnd('experiment');
console.log(str.length);

it will take a longer time than with strings 🤯.

The Array
It is happening because in "JS engines" the arrays are implemented like dynamic arrays. The ECMAScript standards don't strictly define how the arrays should work, and because of this, we may encounter different implementations in the JS engines. And also JS engines have different implementations for dense and sparse arrays. Example in v8 for elements. And a few links about dynamic arrays:
Dynamic Array (data structure)
How do Dynamic arrays work?

Thus, in our case, array-based solutions will only be faster than string-based ones if only the push and pop methods are used. So it will look like manipulating two arrays.

class TextEditor {
  left = [];
  right = [];

  /**
   * @param {string} text
   * @return {void}
   */
  addText = (text) => {
    this.left.push(...text);
  };

  /**
   * @param {number} count
   * @return {number}
   */
  deleteText = (count) => {
    let deletedCount = 0;

    while (this.left.length && deletedCount < count) {
      this.left.pop();
      deletedCount++;
    }

    return deletedCount;
  };

  /**
   * @param {number} movesCount
   * @param {'toLeft' | 'toRight'} direction
   */
  moveCursor = (movesCount, direction) => {
    let actualMoves = 0;
    let currentElement = null;
    let from;
    let to;

    if (direction === 'toLeft') {
      from = this.left;
      to = this.right;
    } else if (direction === 'toRight') {
      from = this.right;
      to = this.left;
    }

    while (from.length && actualMoves < movesCount) {
      currentElement = from.pop();
      to.push(currentElement);
      actualMoves++;
    }

    return this.left.slice(-10).join('');
  };

  /**
   * @param {number} movesCount
   * @return {string}
   */
  cursorLeft = (movesCount) => {
    return this.moveCursor(movesCount, 'toLeft');
  };

  /**
   * @param {number} movesCount
   * @return {string}
   */
  cursorRight = (movesCount) => {
    return this.moveCursor(movesCount, 'toRight');
  };
}

Check it out on leetcode.

When we work with "big strings" that we decided to replace with the array we should remember the limit for the range. It is worth noticing that different algorithms exist to optimize manipulating strings and one of the most efficient is rope by splitting strings into multiple smaller chunks.

Sources:
ChatGPT
Efficient string building in javascript
How Arrays are Implemented in JavaScript

Let me know your thoughts in the comment section below! 😊

is QuickSort fastest?

Sebastian Leukhin — Sat, 17 Dec 2022 17:17:25 +0000

Hey guys, lets gonna practice with the QuickSort algorithm.

This algorithm is based on the divide and conquer approach of programming. As a rule, the Quicksort is an in-place sorting algorithm, but that is not necessary.

This algorithm, on average, takes O(nlog n) time to sort n items. In the worst case, it makes O(n^2) (good implementations as a rule take O(nlog n))
The space complexity is O(log n) but it depends on implementation. Another interesting thing is that we can make this algorithm stable and unstable as well. And as for the stable case, it will take O(n) space or O(1) for in-place implementations
A little preparation in choosing a pivot
Used in V8 before Timsort algorithm

Let's visualize the algorithm:

During selecting the pivot we can sort the first, pivot, and last element - it is a constant operation and doesn't take additional time.

Rules for the code (as usual):

Choose the right names for variables
Choose the right loop statements: for, while, forEach, reduce etc.
Avoid excess conditions and comparisons for edge cases
Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity



class QuickSort {
  constructor(inputArray) {
    /**
     * it depends on the requirements, in our case we sort in place
     */
    this.inputArray = inputArray;
  }

  inputArray;

  swap = (arr, firstIndex, secondIndex) => {
    const temp = arr[firstIndex];
    arr[firstIndex] = arr[secondIndex];
    arr[secondIndex] = temp;
  };

  getMedianFrom3WithSwap = (arr, from = 0, to = arr.length - 1) => {
    const middleIndex = Math.round((from + to) / 2);

    if (arr[middleIndex] < arr[from]) {
      this.swap(arr, middleIndex, from);
    }

    if (arr[to] < arr[from]) {
      this.swap(arr, from, to);
    }

    if (arr[to] < arr[middleIndex]) {
      this.swap(arr, to, middleIndex);
    }

    return arr[middleIndex];
  };

  sortPartition = (arr, from, to) => {
    const pivot = this.getMedianFrom3WithSwap(arr, from, to);

    while (from <= to) {
      while (arr[from] < pivot) {
        from++;
      }

      while (arr[to] > pivot) {
        to--;
      }

      if (from <= to) {
        this.swap(arr, from, to);
        from++;
        to--;
      }
    }

    return [from, to];
  };

  sort = () => {
    const repeatSorting = (arr, from, to) => {
      if (arr.length < 2 || from > to) {
        return;
      }

      const [nextFrom, nextTo] = this.sortPartition(arr, from, to);

      repeatSorting(arr, from, nextTo);
      repeatSorting(arr, nextFrom, to);
    };

    repeatSorting(this.inputArray, 0, this.inputArray.length - 1);

    return this.inputArray;
  };
}

console.log(new QuickSort([7, 4, 3, 5, 6, 8, 1, 9]).sort());
console.log(new QuickSort([100, 3, 4, 5, 13, 7, 3, 0]).sort());
console.log(new QuickSort([1, 4, 3, 5]).sort());
console.log(new QuickSort([3, -1]).sort());

Check result on leetcode

Sources:
https://favtutor.com/blogs/quick-sort-cpp
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort

Let me know your thoughts in the comment section below! 😊

How to safely rewrite boolean conditions?

Sebastian Leukhin — Sat, 05 Nov 2022 15:28:27 +0000

Hey guys, today we gonna practice with the "interesting" algorithm. It was my improvisation at work when I once again tried to rewrite some logical conditions. Let's imagine that you have some statement with logical operators like: !(foo || (bar && !baz)) and you have a task to somehow rewrite it.

So, it would be nice to have tests for this case, but you might haven't some. Your brain starts thinking: "how to automate it" and "how to check all possible boolean values after changes". 🤔 Let's try to write the function to check the original condition variant with the new possible one. Our function can get original and new conditions in the form of functions in which we can pass boolean combinations to check the result on equality.

Rules for the code (as usual):

Choose the right names for variables
Choose the right loop statements: for, while, forEach, reduce etc.
Avoid excess conditions and comparisons for edge cases
Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity

const testBoolConditions = (sourceFn, targetFn) => {
  /**
   * n^r - Permutation with Repetition Formula
   * n - is alphabet length equals 2 (for false and true)
   * r - is number of arguments
   */
  const combinationsCount = 2 ** sourceFn.length;

  let counter = 0;
  while (counter < combinationsCount) {
    /**
     * @example
     * n - 2
     * r - 3
     * combinationsCount = 8
     * in binary system we will args:
     * 0 - [0,0,0]
     * 1 - [0,0,1]
     * 2 - [0,1,0]
     * ...
     * 7 - [1,1,1]
     *
     * where boolArgs will be:
     * 0 - [false,false,false]
     * 1 - [false,false,true]
     * ...
     * 7 - [true,true,true]
     */
    const args = counter.toString(2).padStart(sourceFn.length, '0').split('');
    const boolArgs = args.map(arg => Boolean(Number(arg)));
    const sourceFnResult = sourceFn(...boolArgs);
    const targetFnResult = targetFn(...boolArgs);

    if (sourceFnResult !== targetFnResult) {
      throw new Error(
        `Failed condition for [${boolArgs}] with results sourceFn: ${sourceFnResult}, targetFn: ${targetFnResult}`,
      );
    }

    counter++;
  }

  return 'functions have the same conditions';
};

For the sourceFn and targetFn we are generating all possible variants of arguments via the "Permutation with Repetition Formula" - n^r (n to the r power).

n - is alphabet length (in our case, it is 2 for false and true)
r - is number of arguments (it depends on how many arguments in our condition)

Let's look at how to use it:

Convert our condition !(foo || (bar && !baz)) to function:

(foo, bar, baz) => {
  return !(foo || (bar && !baz));
}

Rewrite the original condition somehow, for instance like this foo || (bar && !baz) ? false : true;

Convert this to a function:

(foo, bar, baz) => {
  return foo || (bar && !baz) ? false : true;
}

And now we are ready to use our testBoolConditions

console.assert(
  testBoolConditions(
    (foo, bar, baz) => {
      return !(foo || (bar && !baz));
    },
    (foo, bar, baz) => {
      return foo || (bar && !baz) ? false : true;
    },
  ),
);

That's it, if we get different results for sourceFn and targetFn for some argument combinations it will throw an error. It might be useful for rewriting some complex conditions.

Let me know your thoughts in the comment section below! 😊

is HeapSort fast?

Sebastian Leukhin — Tue, 27 Sep 2022 18:34:54 +0000

Hey guys, today we gonna practice with the heap-sort algorithm.
The best part of that algorithm is in the worst case we need the same time as in the best case - O(n·log(n)). E.g. QuickSort has the best case O(n·log(n)) (in some cases like three-way partition and equal keys has O(n)), but the worst case is O(n2)! 🤯 Likewise, I need to mention that good implementation of quick sort is about two or three times faster than heapsort. And heapsort is an unstable sort this meaning that the relative order of equal sort items is not preserved.

Complexity: O(n·log(n)) time, O(n) space or O(1) for in-place implementations.

Visual example of MinHeap:

Rules for the code (as usual):

Choose the right names for variables
Choose the right loop statements: for, while, forEach, reduce etc.
Avoid excess conditions and comparings for edge cases
Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity



/**
 *         1
 *       /   \
 *     7      12
 *    / \     /
 *  10  15  25
 */

class MinHeap {
  #heap = [];

  get heap() {
    return this.#heap;
  }

  #getParentIndex = (childIndex) => {
    return Math.floor((childIndex - 1) / 2);
  };

  #hasParent = (index) => {
    return this.#getParentIndex(index) >= 0;
  };

  #getParent = (childIndex) => {
    return this.#heap[this.#getParentIndex(childIndex)];
  };

  #getLeftChildIndex = (parentIndex) => {
    return parentIndex * 2 + 1;
  };

  #getRightChildIndex = (parentIndex) => {
    return parentIndex * 2 + 2;
  };

  #hasLeftChild = (parentIndex) => {
    return this.#getLeftChildIndex(parentIndex) < this.#heap.length;
  };

  #hasRightChild = (parentIndex) => {
    return this.#getRightChildIndex(parentIndex) < this.#heap.length;
  };

  #getLeftChild = (parentIndex) => {
    return this.#heap[this.#getLeftChildIndex(parentIndex)];
  };

  #getRightChild = (parentIndex) => {
    return this.#heap[this.#getRightChildIndex(parentIndex)];
  };

  #isSmaller = (firstElement, secondElement) => {
    return firstElement < secondElement;
  };

  #swap = (firstIndex, secondIndex) => {
    const firstElement = this.#heap[firstIndex];

    this.#heap[firstIndex] = this.#heap[secondIndex];
    this.#heap[secondIndex] = firstElement;
  };

  /**
   * @description
   * Sorting parents
   */
  #heapifyUp = () => {
    // starts from last element
    let currentIndex = this.#heap.length - 1;
    const currentElement = this.#heap[currentIndex];

    while (
      this.#hasParent(currentIndex) &&
      this.#isSmaller(currentElement, this.#getParent(currentIndex))
    ) {
      const parentIndex = this.#getParentIndex(currentIndex);

      this.#swap(parentIndex, currentIndex);
      currentIndex = parentIndex;
    }
  };

  /**
   * @description
   * Sorting leaves
   */
  #heapifyDown = () => {
    let parentIndex = 0;

    while (this.#hasLeftChild(parentIndex)) {
      let smallestChildIndex = this.#getLeftChildIndex(parentIndex);

      if (
        this.#hasRightChild(parentIndex) &&
        this.#isSmaller(this.#getRightChild(parentIndex), this.#getLeftChild(parentIndex))
      ) {
        smallestChildIndex = this.#getRightChildIndex(parentIndex);
      }

      if (this.#heap[parentIndex] < this.#heap[smallestChildIndex]) {
        break;
      } else {
        this.#swap(parentIndex, smallestChildIndex);
      }

      parentIndex = smallestChildIndex;
    }
  };

  add = (item) => {
    this.#heap.push(item);
    this.#heapifyUp();
  };

  poll = () => {
    if (this.#heap.length === 1) {
      return this.#heap.pop();
    }

    const smallerItem = this.#heap[0];
    this.#heap[0] = this.#heap.pop();

    this.#heapifyDown();

    return smallerItem;
  };
}

class HeapSort {
  #inputArray;

  constructor(inputArray) {
    this.#inputArray = inputArray;
  }

  sort = () => {
    const minHeap = new MinHeap();

    this.#inputArray.forEach((item) => {
      minHeap.add(item);
    });

    const sortedArray = [];
    let nextMinElement = minHeap.poll();

    while (Number.isFinite(nextMinElement)) {
      sortedArray.push(nextMinElement);
      nextMinElement = minHeap.poll();
    }

    return sortedArray;
  };
}

Usage:



console.log(new HeapSort([3, 2, 1]).sort());
console.log(new HeapSort([3, 2, 1, 10, 20]).sort());
console.log(new HeapSort([5, 1, 1, 2, 0, 0]).sort());

Sources:
Github heap-sort in js
Test your code on leetcode

Let me know your thoughts in the comment section below! 😊

isPalindrome? (LinkedList)

Sebastian Leukhin — Sun, 28 Aug 2022 08:12:46 +0000

Hi, I'm excited to start today the series of blog posts about algorithms in wildlife!

The main goal of posts in this series is an adaptation of the algorithms from sites like codewars, leetcode etc. to real projects.

Let's get started with today's topic isPalindrome algorithm. First off I guess you already heard about it, I mean you know how to check whether strings are palindrome or not, and today we will discuss a little bit more complex example with the LinkedList.

I want to set the rules for complexity like: O(n) time, O(1) space.

Rules for the code:

Choose the right names for variables
Choose the right loop statements: for, while, forEach, reduce etc.
Avoid excess conditions and comparisons for edge cases
Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity

Let's try to do this:

const getIsLinkedListPalindrome = (inputLinkedList) => {
  let leftSide = inputLinkedList;
  let rightSide = inputLinkedList;

  while (rightSide.next) {
    const prevNode = rightSide;

    rightSide = rightSide.next;
    rightSide.prevNode = prevNode;
  }

/**
  * @description
  * wo w ow - input
  * w === w
  * o === o
  * while finish
  * w === w
  * return

  * ww - input
  * while finish
  * w === w
  * return
  */
  while (
    leftSide.current === rightSide.current &&
    // a b c - check the "b" node equality in a left and right sides
    leftSide !== rightSide &&
    // a a - check the "a" node
    leftSide !== rightSide.prevNode
  ) {
    if (leftSide.current !== rightSide.current) {
      return false;
    }

    leftSide = leftSide.next;
    rightSide = rightSide.prevNode;
  }

  // for odd count of nodes check the middle value
  if (leftSide.current === rightSide.current) {
    return true;
  }

  return false;
};

Some thoughts about the code above:

You may be noticed that we mutated the input data, that outside of a function and i.e. we have a side effect in our function. I think about it as a trade-off for the O(1) space complexity, otherwise, we should have created a new node for each input node, and our space complexity would increase up to O(n). But we avoid the breaking changes to our input data and just extend the initial structure to the doubly linked list.

P.S. Don't use the reverse function to the second part of the list, it breaks the direction of the input linked list.

Extra materials:

To simplify check the result of a function with the string input, use the stringToLinkedList

const stringToLinkedList = (inputStr = '') => {
  if (!inputStr) {
    return { next: null, current: null };
  }
  /**
   * @type {{
   * next: Object | null,
   * current: string | null
   * }}
   */
  let currentNode = { next: null, current: null };
  const lastIndex = inputStr.length - 1;

  for (let i = lastIndex; i >= 0; i--) {
    const currentCharacter = inputStr[i];

    if (i === lastIndex) {
      currentNode.current = currentCharacter;
      continue;
    }

    // 9 -> 8 -> 7
    const prevLinkedList = currentNode;

    currentNode = {
      current: currentCharacter,
      next: prevLinkedList,
    };
  }

  return currentNode;
};

Some input data for assertions

console.assert(getIsLinkedListPalindrome(stringToLinkedList('racecar')));
console.assert(getIsLinkedListPalindrome(stringToLinkedList('abcba')));
console.assert(getIsLinkedListPalindrome(stringToLinkedList('aa')));
console.assert(getIsLinkedListPalindrome(stringToLinkedList('a')));
console.assert(getIsLinkedListPalindrome(stringToLinkedList()));
console.assert(!getIsLinkedListPalindrome(stringToLinkedList('1121')));
console.assert(!getIsLinkedListPalindrome(stringToLinkedList('book')));
console.assert(!getIsLinkedListPalindrome(stringToLinkedList('ab')));
console.assert(!getIsLinkedListPalindrome(stringToLinkedList('abcdba')));

Let me know your thoughts in the comment section below! :)