Why Your Bundler Injects <link rel="modulepreload">, and Why It Shouldn’t Have To

This example comes directly from the WHATWG HTML specification:

<!DOCTYPE html>
<html lang="en">
<title>IRCFog</title>

<link rel="modulepreload" href="app.mjs">
<link rel="modulepreload" href="helpers.mjs">
<link rel="modulepreload" href="irc.mjs">
<link rel="modulepreload" href="fog-machine.mjs">

<script type="module" src="app.mjs">

<link rel="modulepreload"> tells the browser to fetch and initialize a module ahead of time (MDN). Unlike <link rel="preload">, which only downloads resources into the HTTP cache, scripts preloaded with <link rel="modulepreload"> are parsed and compiled early by the browser’s module loader so they are ready when referenced by <script type="module">. In practice this is almost always used for JavaScript modules: if the as attribute is omitted, the destination defaults to "script", and support for other module types remains spotty. Without these hints, the browser has to download app.mjs, parse it to find its import specifiers, fetch those dependencies, parse those to find their imports, recursively discovering each graph level one HTTP request at a time. On a mobile connection with 100ms round-trip latency and a dependency tree four levels deep, that’s ~400ms of dead time before execution begins. HTTP/2 multiplexing, cache hits, and speculative parsing reduce it, but none of them eliminate the fundamental problem: the browser cannot see the graph until it fetches and parses each file.

The problem is that every path in a <link rel="modulepreload"> element is already declared in a JS import statement inside those files. The dependency graph exists in two places — HTML and JS — and the browser follows the JS imports regardless of what the modulepreload elements say. As code evolves — modules renamed, added, removed — the HTML doesn’t update itself. A stale modulepreload that points to a file that no longer exists wastes a network request. Worse, if the old file still exists at that path, the browser downloads something the application never uses — a performance penalty imposed by the very mechanism designed to improve performance. A missing modulepreload means the waterfall returns for that dependency. Neither case produces a runtime error. A 404 appears in the console or server logs if the old file is gone, but nothing connects it back to a modulepreload/import mismatch — it’s just a failed network request among hundreds. To keep the two graphs in sync, you need build tooling.

If you’ve seen this pattern in production, it was generated by Vite, SvelteKit, Nuxt, or a similar framework, because maintaining it by hand is untenable.

This is the architecture the web platform shipped. It wasn’t the only option.

In 2009, I proposed a declarative alternative that would have put the dependency graph in HTML — one source of truth, visible to the browser’s networking layer before any JS executes. The discussion ended almost immediately. After a few responses from browser engineers, the thread went quiet. There was no extended design exploration, no prototype, no attempt to refine the idea. On the WHATWG mailing list, once a thread stops receiving implementer engagement, the proposal is effectively dead.

The absence of declarative dependency loading went on to spawn an entire category of workaround software — LABjs, RequireJS, AMD, SystemJS — all solving in JavaScript what the browser refused to solve in markup. Those tools are now largely obsolete, replaced by ES modules and bundlers. But the underlying problem persists: the browser still can’t see the graph without parsing JS first, which is why your framework does the bookkeeping for you.

The Problem: Dependency Discovery Requires Fetching

ES modules moved the dependency graph into JavaScript to try to create a single module system that works across Node, browsers, and other runtimes. That’s an ambitious language-design goal, but it left the browser’s HTML parser blind to dependencies. When a browser hits <script type="module" src="app.js">, it fetches the file, parses it to discover import specifiers, fetches those, parses those — discovering the dependency graph incrementally, one module at a time, rather than reading it from the markup upfront.

modulepreload exists to fix this. But it has fundamental design problems that a better solution would have avoided.

Three-Way Duplication

In the spec example above, the dependency graph lives in three places: the import specifiers inside the JS files, the <link rel="modulepreload"> elements that hint the browser to prefetch them, and the <script type="module"> element that triggers execution — two independent declarations of the same graph, with no validation layer between them. With depends, it would be one:

<script id="helpers" src="helpers.mjs"></script>
<script id="irc" src="irc.mjs"></script>
<script id="fog" src="fog-machine.mjs"></script>
<script src="app.mjs" depends="helpers irc fog"></script>

No Enforcement

Rename helpers.mjs to utils.mjs and update the JS import — the application works. The orphaned <link rel="modulepreload" href="helpers.mjs"> element stays, fetching a file that no longer exists. A 404 appears in the console, but no runtime error is thrown. Nothing connects the failed request to the stale modulepreload.

Optional Dependency Fetching

From the spec:

“A browser may additionally also choose to automatically fetch any dependencies of the module resource.”

And from the algorithm:

“Generally, performing this step will be beneficial for performance, as it allows pre-loading the modules that will invariably be requested later… However, user agents might wish to skip them in bandwidth-constrained situations, or situations where the relevant fetches are already in flight.”

The spec acknowledges these fetches will “invariably” be needed — then gives browsers blanket permission to skip them. MDN warns developers directly:

“The only approach to ensure that all browsers will try to preload a module’s dependencies is to individually specify them.”

Since recursive dependency fetching is optional, browser behavior is implementation-defined. Rich Harris — creator of Svelte and SvelteKit — built a demo that adds artificial latency to make the waterfall visible: Chrome loaded in 1 second while Firefox and Safari took 3, in part because only Chromium supported modulepreload at the time. Firefox didn’t add support until version 115 in July 2023 — five years after Chrome 66 shipped it in April 2018. For half a decade, the only way to avoid the waterfall was to target a single browser engine or use a build tool.

By contrast, depends avoids recursive graph discovery entirely. It tells the browser what to fetch next, rather than relying on behind-the-scenes implementation details. depends="a b c" declares the graph in markup — the browser checks whether elements a, b, and c have loaded, then proceeds. No recursion. No ambiguity about how deep to walk. The simplest thing that could possibly work, but not any simpler.

Scripts Only

modulepreload addresses script-to-script dependencies. It does nothing for the script-depends-on-stylesheet problem — the performance issue that started this entire conversation.

File-level modularity — one file, one cohesive unit of functionality — is not a modern invention. It goes back to C translation units, Java classes, and every language that organizes code into files that can be compiled, tested, and loaded independently. It’s how developers structure their code and their thinking.

CSS supports splitting styles across multiple files. This works for simple webpages — what CSS was originally designed for — but is impractical for component-based SPAs, because every <link rel="stylesheet"> blocks rendering. More files means more blocking requests.

Developers are forced into a losing choice: keep styles modular and accept slow page loads, or collapse them into monolithic bundles that load fast but abandon file-level organization — then depend on build tools to manage the resulting mess. Either path means more effort, worse code structure, and tooling dependencies that wouldn’t exist if the platform supported non-blocking stylesheet loading.

The platform had a closer attempt. HTML5 specified a scoped attribute on <style> — styles scoped to a specified element’s subtree. Firefox shipped it in version 21. In 2016, Domenic Denicola filed the removal:

Domenic Denicola Domenic Denicola

It seems shadow DOM and stylesheets restricted to a shadow tree ends up solving more of the real-world problems developers are faced with.

He followed this up with the familiar “no vendors” trope, parroting Hickson from the depends thread seven years earlier. Apparently “no vendors” is the same thing as “no use case” in his mind. Or maybe it’s post hoc rationalization for the simple fact that only Firefox implemented it. Shadow DOM is a component isolation model — it solves style encapsulation, not style loading. Nevermind that developers and browser engineers wanted scoped — they’re not vendors, and besides, Domenic knows the best way to load scoped CSS modules: Shadow DOM. The reinstatement request was closed as a duplicate of @scope, which is a different feature entirely.

Hickson acknowledged in 2012 that <link scoped> — external files, not inline — was the right design if the use case warranted it. It was never specified. Seven years later, the CSS Working Group shipped @scope — selector containment, nothing for loading. CSS still has no mechanism for non-blocking, file-level module loading.

depends and defer were 75% of the complete solution. Add scoped on <link> and developers would have had declarative dependency loading, non-blocking stylesheets, and component-scoped styles — all in HTML, all visible at parse time, no build step. Three attributes. Instead, the platform killed scoped, never specified <link scoped>, and left CSS with no loading story at all.

This is what HTML was designed to be. The thoughts that went into hypertext in 1989 match exactly what depends solves. Hypertext is a graph — HTML hides that complexity behind <a href>. depends does the same thing for resource loading: a graph declared as a list of IDs. Simple, declarative, and powerful. No tree traversal, no recursive fetch, no build tooling. By keeping things simple, Berners-Lee encouraged others to build upon his ideas. depends follows that principle — developers don’t need to understand dependency graphs to use one.

The defer attribute on <link> in the 2009 proposal would have solved non-blocking CSS directly. Instead, Google’s own web.dev performance guide recommends this “advanced performance technique that can improve performance”:

<link rel="preload" href="styles.css" as="style" onload="this.onload=null;this.rel='stylesheet'">
<noscript><link rel="stylesheet" href="styles.css"></noscript>

— a hack that uses inline JavaScript in a <link> element, a <noscript> fallback, and rel="preload" — which fetches asynchronously but does so at the highest priority, the exact opposite of deferring.

Still Expanding, Seventeen Years In

As of January 2026, Chromium is shipping support for as="style" and as="json" in modulepreload — because CSS and JSON modules can be imported but historically could not be preloaded. The intent to ship calls it a “functionality gap.” Mozilla and WebKit both had no signal at the time of filing. Every new module type requires a new as= value, a new spec change, a new round of browser adoption. A depends attribute referencing element IDs would have been content-type agnostic — it works for scripts, stylesheets, JSON, or anything else loadable by a <script> or <link> element, without per-type spec work.

For a broader view of the damage caused by shipping a module system without a loading mechanism, see joepie91’s “ES Modules are terrible, actually” — 220 stars, years of detailed technical debate, and a comment thread that reads like a support group for developers who’ve lost hours to the CJS/ESM split.

The Better Design That Was Rejected

In February 2009, I submitted a proposal to the WHATWG mailing list: put the dependency graph in HTML.

<script depends="a b c"></script>

Where depends is a space-separated list of element IDs. The browser resolves the graph. One declaration, in markup, visible to the pre-parser before any JS executes.

Two attributes covered the dependency-loading problem. depends on <script> declared which resources a script needs before execution. defer on <link> allowed stylesheets to load without blocking rendering. If a script doesn’t list a stylesheet in depends, the browser knows it doesn’t need that stylesheet’s data — no blocking required.

Because depends references element IDs — not script IDs or stylesheet IDs — it works for any resource type. Scripts, stylesheets, fonts, images, video — anything with an id and an href or src can be a dependency:

<link id="ui-font" rel="preload" href="inter.woff2" as="font" defer>
<link id="ui-style" rel="stylesheet" href="ui.css" defer>
<script id="ui" src="ui.js" depends="ui-style ui-font"></script>
<script src="app.js" depends="ui"></script>

The browser reads the graph at parse time, schedules all fetches in parallel, and resolves the execution order. No bundler required. No recursive fetch. No build step. Developers don’t need to know what a dependency graph is, or how BFS/DFS traversal works — they just declare: “this script needs those resources, and those resources shouldn’t block initial page load.”

Browsers block scripts on preceding stylesheets for a real reason: CSSOM consistency. A script calling getComputedStyle or reading offsetLeft needs accurate style data. The proposal didn’t ask browsers to break that guarantee — it gave developers a way to declare it. If a script needs style data, say so with depends. If it doesn’t, don’t list the stylesheet. The browser still enforces the constraint. The developer simply declares it.

ES modules solve language-level dependency semantics. depends solves HTML-level resource scheduling. They’re complementary — a script loaded via depends can contain import statements. A stylesheet loaded via defer can be required by a script via depends. Cross-resource dependencies, declared in one place.

The architectural difference is where the graph becomes visible:

Current:                          Proposed (2009):
HTML                              HTML
  ↓                                 ↓
load root module                  dependency graph already declared
  ↓                                 ↓
parse JS                          schedule all fetches
  ↓                                 ↓
discover dependency graph         fetch in parallel
  ↓                                 ↓
schedule loads                    execute in declared order

The current architecture requires round trips to discover what to download. The proposed architecture exposes the dependency graph to the browser’s networking layer at parse time, before any JS is fetched.

This wasn’t theoretical. I provided test pages with timing data. A linked stylesheet delayed by five seconds produced contentLoaded and onloadFired values of ~5101ms — the entire page waited for one stylesheet. HTTP waterfall data from Firefox 3.0 showed that a script in the <body> wasn’t even requested until a <head> stylesheet completed, eight seconds after the initial page load:

+---------------------+-------------------------------+
| req                 + HTTP date                     |
+---------------------+-------------------------------+
| link-external.html  | Tue, 10 Feb 2009 07:01:13 GMT |
| example.js?top      | Tue, 10 Feb 2009 07:01:13 GMT |
| delay.jsp?ct=text...| Tue, 10 Feb 2009 07:01:13 GMT |
| example.js?bottom   | Tue, 10 Feb 2009 07:01:22 GMT |
+---------------------+-------------------------------+

The last request — a script before the closing </body> tag — was delayed eight seconds. The browser waited for a stylesheet in <head> to finish before it would even fetch a script in <body>.

The spec’s fetch a modulepreload module script graph algorithm exists today precisely because the HTML doesn’t express the graph. The browser walks it at fetch time because the markup never declared it. A depends attribute would have made the browser’s job explicit and the developer’s intent unambiguous.

What Happened to the Proposal

The thread is public. Here’s what it shows.

Ian Hickson, the WHATWG spec editor, dismissed the problem outright:

“Browsers are already allowed to not block on those elements.”

The spec permitted non-blocking behavior. Browsers didn’t do it. Developers had no way to control it.

Jonas Sicking, a Mozilla engineer, immediately contradicted Hickson. In Gecko, the browser blocks script execution until all preceding stylesheets finish loading — because scripts might call getComputedStyle or read offsetLeft:

“We have found that some sites break if we just use whatever style data happens to have loaded at that point, rather than ensuring that all stylesheets have been parsed and applied.”

When I responded with test data, concrete use cases, and worked examples of depends and defer, Hickson’s objection shifted:

“This seems like an inordinate amount of complexity for something that can just work already.”

The problem went from “doesn’t exist” to “too complex to solve” in one exchange.

Boris Zbarsky of Mozilla engaged more substantively. He acknowledged the technical merit:

“I would be fine with a way to flag scripts with that information.”

But he argued that any new attribute would produce divergent behavior between old and new browsers. If a script declares via depends that it doesn’t need a preceding stylesheet, new browsers skip the blocking while old ones still block:

“I don’t think anything would solve the problem for browsers today.”

Applied consistently, this reasoning blocks any new attribute from ever being specified. Every new HTML attribute produces divergent behavior between supporting and non-supporting browsers. That’s what new features are.

The Structural Problem

WHATWG proposals advance when a browser vendor commits to implementing them. Proposals without that commitment get filtered through different questions: “Is this already possible in theory?” and “Would existing browsers break?” Both tests favor the status quo. The proposal had no vendor backing, and without that, it went nowhere.

How the Graph Got Lost Between Two Specs

Five years later, TC39 designed ES6 modules with a programmatic Loader — a five-stage pipeline (Locate, Fetch, Translate, Instantiate, Link) that would have given the browser access to the dependency graph. The Loader’s instantiate stage returned a structure that declared dependencies before execution (sound familiar?):

instantiate: function(load) {
  return {
    deps: ['some', 'dependencies'],
    execute: function(depA, depB) {
      return new Module({ /* exports */ });
    }
  };
}

An explicit dependency list, declared before execution, so the loader could schedule all fetches immediately. The same architectural requirement that depends addressed in HTML: the system must know the graph before execution to schedule network requests efficiently.

In September 2014, TC39 cut the Loader from the spec. The committee kept the import/export syntax and handed the loading mechanism to the WHATWG as a separate “living standard” Loader project. That project stalled and was effectively abandoned by 2018.

The dependency graph ended up locked inside JS import statements, invisible to the HTML parser — and addressing only JavaScript, leaving the CSS Working Group to solve loading on their own (look how that turned out). The loading spec that was supposed to bridge the two layers was never completed.

AMD and RequireJS are massive projects. They support stylesheet and font loading through plugins and integration with external libraries like Web Font Loader — more “best practices” kludges that rely on browser hacks, and exist to address the barndoor-wide gaps the spec authors failed to close. These tools remain in widespread use because the platform never solved the problem natively. Today’s build tools extract the module dependency graph and inject <link rel="modulepreload"> elements so browsers can fetch modules in parallel.

The web platform provides preload, prefetch, fetchpriority, loading="lazy", and font-display — but those are resource hints and fetch-priority controls, not dependency declarations. They influence when and how a resource is fetched, but they do not express relationships between scripts and other resources. JS import statements express dependency relationships between scripts and other resource types. modulepreload is an afterthought to influence fetch priority behavior of those scripts. There is no web platform API to declare:

script → stylesheet
script → font
script → image
script → JSON

These are the relationships that matter for resource scheduling, and depends expressed all of them. The current platform mixes three unrelated mechanisms:

dependency discovery     JS imports, modulepreload hints
fetch priority           preload, fetchpriority, lazy loading
style containment        @scope, shadow DOM

Of my proposals, depends addressed the first, defer on <link> addressed the second. The scoped attribute addressed the third. depends on <script> does what modulepreload does — and more — more simply, more expressively, with less code. The build tool is the integration layer between specs that never coordinated.

Seventeen years of attempts to solve the same problem:

  • 2009depends and defer on HTML elements. Dismissed within hours, no design exploration.
  • 2012<style scoped> specified in HTML5, implemented in Firefox. Hickson acknowledged that <link scoped> (external files) was the right design. Never specified.
  • 2014ES6 Loader with deps array. Cut from the spec, handed to WHATWG, abandoned.
  • 2016<style scoped> removed from the spec by Domenic Denicola. Shadow DOM cited as the replacement.
  • 2018modulepreload ships in Chrome. JS-only, no validation, requires build tooling. Five years before a second browser implements it.
  • 2019loading="lazy" ships for images and iframes. The platform can add declarative loading attributes when vendors want to.
  • 2023@scope ships. Selector containment. Nothing for loading.
  • 2026modulepreload reaches Baseline Widely Available. Chromium adds as="style" and as="json" to modulepreload — because import-type modules for CSS and JSON can be imported but not preloaded. Browser support for CSS and JSON import types remains spotty.

Two designs declared a flexible, resource-agnostic graph before execution — depends and the ES6 Loader deps array — killed. The one attempt at declarative stylesheet scoping — <style scoped> — also killed. Everything else is either a workaround or addresses the wrong layer.

What Happened to Declarative Dependency Loading

My proposal was dismissed without vendor backing. The ES6 Loader was cut. Both declared the graph before execution. Neither survived.

modulepreload is an afterthought — a fetch-priority hint bolted onto <link> to partially address the waterfall that JS import statements created. It duplicates the dependency graph across HTML and JS with no validation layer between them. It took five years to reach cross-browser support — reaching “Baseline Widely Available” only in March 2026 — the same kind of cross-browser gap Zbarsky used to argue against depends in 2009. The platform still penalizes CSS modularity at the loading level. Build tools fill the gap for JavaScript; everything else is left to hacks and workarounds.

The proposal put the graph in HTML, where the browser could act on it at parse time — before fetching any resource, for any resource type. And it did so simply enough that developers didn’t need to think in terms of graphs or trees — just: “this script needs those styles, and they shouldn’t block initial page load.” The platform put the graph in JS, lost the loading spec between two committees, and compensated with a hint mechanism that requires tooling to maintain.

The thread is still there. The test pages are gone, but the arguments — and who made them — are preserved.


The original WHATWG mailing list thread: [whatwg] defer on style, depends — February 8, 2009

Original message · W3C archive with replies

I Solved Hundreds of LeetCode Problems.

I solved hundreds of LeetCode problems (user: dhtmlkitchen). I would solve the daily problem, then create a write up on LeetCode (because if you can’t explain it, you don’t really understand it that well yourself). Next, I would take screenshots of my code, copy the problem description, and post the problem with my screenshots on LinkedIn. 

After several months of doing this, I built up a following of about 155 followers.

LinkedIn Sucks

But LinkedIn groups were full of spam and many low-quality posts. Recruiters aren’t there looking to see who’s the best of the best because it’s all spam and low-quality posts. And for the spam, the only actions LinkedIn Trust & Safety take are against the user who reported, blocking and restricting the reporter and leaving the spam.

Johnson & Johnson & Getting Banned

LinkedIn kept feeding me Johnson and Johnson ads, which is a bit of a sore spot for me. So, I broke my rule of posting only professionally-related things on LinkedIn and posted a comment in the comment box of the J&J ads LinkedIn was targetting me with. 

The comment was to the effect that my mother used Johnson and Johnson shower to shower talc products for the 20 years leading up to her diagnosis with leiomyosarcoma, caused by those products[1].

Johnson and Johnson recently settled a massive lawsuit for these products. However, because leiomyosarcoma is so rare, it was not listed on the lawsuit and I was excluded as a plaintiff.

I was very careful to remain within the guidelines of LinkedIn’s terms.

However, after that, LinkedIn deleted my account.

Interview Prep Matters…

I failed my 2009 Google interview after failing to solve Product of Array Except Self. It’s a challenging dynamic programming problem but once you know how to solve it, it’s not that hard.

…For the Interview

Only a small percentage of technical interview prep has direct practical relevance to the tasks I’ve performed as a Frontend engineer. Some algorithmic problems I’ve had to address as a front end engineer involve n-ary trees, graphs, strings and arrays, which appear on LeetCode. Other algorithms I’ve had to tackle do not. For example, I’ve never seen colorimetry problems on LeetCode.

Other front-end problems involve design patterns, data sanitization strategies, and using strategies to deal with a dynamic deployment environment (web browsers).

[1] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8106926/#T3

Prefix and Suffix Arrays

A Prefix Array, also known as a Prefix Sum Array or Cumulative Sum Array, is an Array with the calculation of cumulative sums of elements in a source array. It stores the cumulative sum of elements up to a certain index in the array. This can also be done in-place, so that the target rewrites values of the source.

Prefix and Suffix arrays are useful for range computations. For example, LeetCode 1608. Special Array With X Elements Greater Than or Equal X

Here’s how it works:

Given an array of numbers, the prefix array would be another array where each element prefix[i] stores the sum of elements from index 0 to index i in the array.

For example, given nums = [1, 2, 3, 4, 5], the prefix array would be [1, 3, 6, 10, 15], because:

prefix[0] = 1                      // sum from nums[0] to [0]
prefix[1] = 1 + 2 = 3              // sum from nums[0] to [1]
prefix[2] = 1 + 2 + 3 = 6          // sum from nums[0] to [2]
prefix[3] = 1 + 2 + 3 + 4 = 10     // sum from nums[0] to [3]
prefix[4] = 1 + 2 + 3 + 4 + 5 = 15 // sum from nums[0] to [4]
Code language: JavaScript (javascript)

Here is an example of creating a prefix array in-place, in JavaScript:—

const nums = [1, 2, 3, 4, 5];
nums.forEach((num, i) => nums[i] += nums[i-1] ?? 0);
// [1, 3, 6, 10, 15]
Code language: JavaScript (javascript)

Suffix Array:

A suffix array is similar to a prefix array, but it stores cumulative sums in reverse order. Instead of storing the sum of elements up to a certain index from left to right, a suffix array stores the sum of elements from right to left.

Given the array nums = [1, 2, 3, 4, 5], the suffix array would be:—

suffix[4] = 5
suffix[3] = 5 + 4 = 9
suffix[2] = 5 + 4 + 3 = 12
suffix[1] = 5 + 4 + 3 + 2 = 14
suffix[0] = 5 + 4 + 3 + 2 + 1 = 15

//  [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)

Suffix Array Code

Creating a suffix array function is a little trickier than writing a prefix array. It can be done with a new array or in-place, replacing values of an existing array. Here are both.

function createSuffixArray(nums) {
    const suffixArray = new Uint32Array(nums);
    for (let i = suffixArray.length - 2; i >= 0; i--) {
        suffixArray[i] += suffixArray[i+1];
    }
    return suffixArray;
}

const nums = [1, 2, 3, 4, 5];
createSuffixArray(nums);
// [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)

By pre-allocating a Uint32Array of the appropriate length and iterating over the input array from right to left, I efficiently compute the cumulative sums and store them directly in the suffix array without needing to reverse the array or create intermediate copies. This approach is concise and efficient.

This can also be done in-place.

function createSuffixArrayInPlace(nums) {
    for (let i = nums.length - 2; i >= 0; i--) {
        nums[i] += nums[i+1];
    }
    return nums; // Optional: Return the modified nums array
}

const nums = [1, 2, 3, 4, 5];
const suffixArray = createSuffixArrayInPlace(nums);
// [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)

LeetCode 1289. Minimum Falling Path Sum II

DP Solution Without Modifying Input — 24 Lines — O(n^2) / O(n)

Problem: https://leetcode.com/problems/minimum-falling-path-sum-ii/

Solution: https://leetcode.com/problems/minimum-falling-path-sum-ii/solutions/5081680/dp-solution-without-modifying-input-24-lines-o-n-2-o-n/

Algorithm

  1. Find smallest two cells of first row.
  2. Loop through remaining rows, rows i+1 to len-1.
  • For each cell, if it’s not the same col index as the prev smallest, add smallest prev cell, low, else, add the second smallest prev, hi.
  • Find next two lowest cells for each next row after adding lowest cells from prev row
  1. Return last lowest cell

Complexity

  • Time complexity: O(n2)
  • Space complexity: O(n)

The lowest values of the prev row are stored in three properties, low, i, hi.

rowValues = {
  low // lowest value (from prev row)
  hi // second lowest value (from prev row
  i // lowest value's index (from prev row)
}

The values of each row are also temporarily stored in an identically-structured object.

const minFallingPathSum = (() => {
    "use strict";
    const findLeastTwo = (row, prev) => {
        const rowValues = { low: Infinity, hi: Infinity };
       for (let i = 0; i < row.length; i++) {
            let cell = row[i] + (i === prev.i ? prev.hi : prev.low);
            if (cell < rowValues.low) { 
                 Object.assign(rowValues, {hi:rowValues.low, low:cell, i:i});
            } else if (cell < rowValues.hi) {
                rowValues.hi = cell;
            }
        }
        Object.assign(prev, rowValues);
    };

    return grid => {
        const prev = { low: 0, hi: 0, i: -1 }
        for (const row of grid) findLeastTwo(row, prev);
        return prev.low;
    };
})();Code language: JavaScript (javascript)

Top-Level Array filter with Function.prototype.call.bind

Top-level Array generics didn’t make it into EcmaScript. Here’s how to hand-roll them.

const myFilter = Function.prototype.call.bind(Array.prototype.filter);
Code language: JavaScript (javascript)

And that gives is a function that can be called as:—

const isNotUpper =  e=>e>"Z"; // lexicographic comparison
myFilter("asdAxE", isNotUpper).join(""); // "asdx"
Code language: JavaScript (javascript)

How does this filter “magic” work? Let’s look step-by-step with another example, Array.prototype.forEach. But first, let’s get some “basics” out of the way.

Function.prototype.call

Function.prototype.call calls the function it’s called on, passing its first argument as the this value to that function.

In the following example, window.prompt is called three times, passing the value of each character, followed by the index in which it occurs, followed by the this value (a String object).

[].forEach.call("asd", prompt);
Code language: JavaScript (javascript)

The interpreter will execute the above as the following:

thisArg = new String("asd");

prompt("a", 0, thisArg);
prompt("s", 1, thisArg);
prompt("d", 2, thisArg);
Code language: JavaScript (javascript)

(Function window.prompt ignores the last argument.)

We can do likewise with console.log, which prints any number of arguments.

[].forEach.call("asd", console.log);
Code language: JavaScript (javascript)

image
In each call, the arguments passed are (1) the value at each index, (2) the index, and (3) the String object (promoted from a string value), used as the thisArg.

Function.prototype.call.call

We can further abstract the forEach call with:—

Function.prototype.call.call (func, thisArg, ...args )
Code language: JavaScript (javascript)

— as:—

Function.prototype.call.
    call([].forEach, "asd", console.log)
Code language: JavaScript (javascript)

— resulting:—

image

In the above code, the this value to call is [].forEach, the this value to forEach is "asd", promoted to a String object, and the callback function, the first argument to forEach, is console.log.

Function.prototype.call.bind

If the second call method is replaced with call to Function.prototype.bind, forEach will be bound as the this value to a function from call as:—

let arrayForEach = Function.prototype.call.bind([].forEach);
Code language: PHP (php)

The steps by which this new function is created are a bit tricky, but it essentially creates a new function with a `[[BoundThis]] value assigned to the first argument (promoted to an object) (See: 10.4.1.3 BoundFunctionCreate ( targetFunctionboundThisboundArgs )).

The forEach method can now be called generically, without call.

arrayForEach("asd", console.log)
Code language: JavaScript (javascript)

The bound function arrayForEach is passed with "asd", which is promoted to a string object with length=3, and used as the this arg for [].forEach. Function [].forEach is called with, console.log three times, such as:

console.log(thisArg[i], i, thisArg)
Code language: JavaScript (javascript)
image

We can reuse this top-level Array.prototype.forEach:

const arrayForEach = 
Function.prototype.call.bind([].forEach);
arrayForEach("asd", console.log)
arrayForEach("qwe", console.log)
Code language: JavaScript (javascript)
image

Function.prototype.call Shortcut

Just as Array.prototype.forEach is found on every array instance such as [].forEach, so too is Function.prototype.call found on every function instance, such as (function(){}).call.

Base Object to Call and Arrow Functions

Arrow functions get their this value from the lexical environment and Bound functions have a bound thisArg (more on this later). This:—

(e=>e).call("foo")
Code language: JavaScript (javascript)

— results undefined

For our intent, this doesn’t matter. We can still use call a layer of abstraction out, as call.call. We don’t access the Base object that far back. We can also use other functions or the built-in function constructor function, Function.

(function(){return this}).call({})
Code language: JavaScript (javascript)

— which returns the object argument, {}.

Calling of forEach is stored by binding forEach to the call method:

let boundForEach = Function.prototype.call.bind([].forEach);
Code language: JavaScript (javascript)

This can be later called with any thisArg and any callback.

boundForEach("asd", prompt);
Code language: JavaScript (javascript)

Bound Method for Array.prototype.filter

Back to the problem at hand, we want to invoke Array.prototype.filter when it’s called and with the arguments passed in:

const myFilter = Function.prototype.call.bind(Array.prototype.filter);
Code language: JavaScript (javascript)

And that gives is a function that can be called as:—

const isNotUpper =  e=>e>"Z"; // lexicographic comparison
myFilter("asXd", isNotUpper);
Code language: JavaScript (javascript)

— results:—

['a', 's', 'd']
Code language: JavaScript (javascript)

Function myFilter is called with array-like object to act as the this value for the actual function call to Array.prototype.filter.Array.prototype.filter promotes its thisArg to a String object and calls the second parameter, isNotUpper (with that String as the thisArg).

Just as we get Array.prototype.forEach with [].forEach, so too can we get Function.prototype.call from any function (except arrow or bound functions).

Function.call is the same Function.prototype.call, but gets it this arg a Function, the base object, if called as Function.call(). As mentioned, we’re not calling it like that, rather, we’re using the value of that function as the Base object for bind.

From: https://leetcode.com/problems/filter-elements-from-array/discuss/5024144/Function.prototype.call.bind

Checking NaN Values

NaN is a global property that represents an IEEE 754 “not a number”. (There is also a static NaN property of the built-in Number object, Number.NaN for pointless duplication (mdn)).

In older versions of ECMAScript NaN and other global properties like undefined were writable. You shouldn’t be doing that and Brendan, et al made it illegal; even throwin errors in strict mode..

The value type of NaN is “number”, as can be seen by the literal NaN property or by NaN values.

typeof NaN; // "number"
typeof (1 / "foo"); // "number"

Any value compared to NaN using the comparison operators == or === results false.

NaN == NaN; // false
undefined == NaN; // false

Method isNaN almost seems to work:—

isNaN(NaN); // true

— until it does type conversion, even attempting to run the algorithm when no argument is supplied.

isNaN(); // true
isNaN(undefined); // true
isNaN("-."); // true
isNaN(""); // false
isNaN("-2."); // false

The answer to that is to use Number.isNaN, which only returns true for actual NaN values and does not do type conversion.

Number.isNaN(); // false
Number.isNaN("1"); // false
Number.isNaN(""); // false
Number.isNaN("-."); // false
Number.isNaN("0xf"); // false
Number.isNaN("-2."); // false

Object.is can also reliably check NaN values:

 Object.is(NaN, NaN); // true
 Object.is(NaN, undefined); // false

Methods isFinite and the newer non-type-converting version Number.isFinite can work in certain situations:—

 Number.isFinite(NaN); // false

— but do not check exclusively for NaN, as they also return true for Infinity and -Infinity:—

 Number.isFinite(-Infinity); // false

But these methods are useful for numeric validation. Especially Number.isFinite, which, unlike global isFinite, does not do type conversion:

Number.isFinite("2"); // false
Number.isFinite(new Date); // false
isFinite("2"); // true
isFinite(new Date); // true

LeetCode 15. 3Sum, in JavaScript

Problem

LeetCode 15. 3Sum — JavaScript.

Solution

https://leetcode.com/problems/3sum/solutions/2895033/javascript-sorted-typed-array-sliding-window/?orderBy=most_votes

const threeSum = numsArray => {
    "use strict";
    const nums = Int32Array.from(numsArray).sort();
    const results = [];
    const LAST  = nums.length - 1;

    let i = 0;
    do {
        const n = nums[i];
        if (n === nums[i-1]) continue;
        let l = i + 1;
        let r = LAST;
        const isPossible = (n + nums[l] + nums[l+1] <= 0);
        if (!isPossible) break;
        do {
            const ln = nums[l];
            const rn = nums[r];
            const testSum = n + ln + rn;

            if (testSum === 0) {
                results.push([n, ln, rn]);
                // Increment l; decrement r.
                // To avoid duplicate triplets,
                // repeat until unique values appear.
                //  E.g. [-10, 2, 3, 3, 7, 8]
                // [[-10, 2, 8] [-10, 3, 7]] NOT 2nd [-10, 3, 7]
                while (ln === nums[++l]);
                while (rn === nums[--r]);
            } else if (testSum < 0) {
                l++;
            } else {
                r--;
            }
        } while (l < r);
    } while (++i < LAST)
    return results;
};Code language: JavaScript (javascript)

Interactive Web Demo in JavaScript

https://mybanned.com//wp-content/uploads/2023/01/3sum.html

Video

LeetCode 54. Spiral Matrix in JavaScript

Problem

Given an m x n matrix, return all elements of the matrix in spiral order.

https://leetcode.com/problems/spiral-matrix/description/

Solution

https://leetcode.com/problems/spiral-matrix/solutions/2989475/four-pointer-javascript-video-demo/

Interactive Demo

https://mybanned.com//demo/spiral-matrix.html

Video

LeetCode 3. Longest Substring Without Repeating Characters — Interactive JavaScript

Problem

Given a string s, find the length of the longest substring without repeating characters.

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Solution

Dynamic Programming Sliding Window with Set

Interactive Example using Promises

Explanation

Use a Sliding window. Go stepwise through characters of s to expand the longest unique string one character each step. Each time a new maximum size of characters in the Set is reached, it is stored in our variable, ans. The Set is used only to track the next possible longest unique set of characters.

If the next character in s is not in the Set, wordEnd is incremented, widening the window. Save ans = Max(new result, previous max).

If the next character is already in our Set, try a new window. We don’t know where in our word the next character exists, but we can try removing one char from the front of the set. This decreases the current running set of unique characters, but gives us a chance to possibly find a longer unique set.

MAX_LENGTH - wordStart > ans

If the length number of characters remaining are greater than our longest answer, continue the loop for a chance to get a longer answer.

Loop Terminal Condition

MAX_LENGTH - wordStart > ans
If the length number of characters remaining are greater than our longest answer, continue the loop (there is a chance to get a longer answer).

Time complexity

O(n)

Space complexity

O(2n)

JavaScript

function lengthOfLongestSubstring(s) {
    const MAX_LENGTH = s.length;
    const set = new Set();
    let ans = 0, wordStart = 0, wordEnd = 0;
    while (MAX_LENGTH - wordStart > ans) { // Loop terminal condition.
        if(!set.has(s[wordEnd])) {
            set.add(s[wordEnd++]);
            ans = Math.max(ans, wordEnd - wordStart);
        } else {
            set.delete(s[wordStart++]);
        }
    }
    return ans;
}

Changing while to do / while can improve performance. If the readability is good, why not use it?

Only one small tweak is needed to avoid an error. Can you spot the error?

function lengthOfLongestSubstring(s) {
    "use strict";
    const MAX_LENGTH = s.length;
    const testChars = new Set();

    let ans = 0, wordStart = 0, wordEnd = 0;
    if (MAX_LENGTH === 0) return 0;
    do { 
        if(!testChars.has(s[wordEnd])) {
            testChars.add(s[wordEnd++]);
            ans = Math.max(ans, wordEnd - wordStart);
        } else {
            testChars.delete(s[wordStart++]);
        }
    } while (ans < MAX_LENGTH - wordStart)
    return ans;
}

If s === "", its 0 property (wordEnd) is undefined.

We can avoid adding undefined to our map by doing a check for this special case before the loop.

if (MAX_LENGTH === 0) return 0;

Finally, adding "use strict" allows the script engine to make some of its own optimizations, more for sanity than performance. (This should mostly be done on the file level or by using modules or classes.) The result is readable and has phenomenal performance, beating 91.55 % of all javascript submissions.

Non-strict functions use a separate Environment Record for top-level lexical declarations. This is done so direct eval can determine whether any var-scoped declarations introduced by the eval code conflict with pre-existing top-level lexically scoped declarations. This is not needed for strict functions because strict direct eval places all declarations into a new Environment Record.

Performance: Beats 91.55%!