Longest Increasing Subsequence - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'orange';
const CURRENT_MIN_LIS_TAIL = 'current_min_lis_tail', CURRENT_MIN_LIS_TAIL_COLOR = 'blue';

function visMainFunction(inputNums) {
    initClassProperties();

    startBatch();
    const nums = VisArray.from(inputNums);
    const minLisTails = new VisArray();

    let index = 0;
    makeVisVariable(index).registerAsIndexPointer(nums, CURRENT);
    endBatch();

    explanationAndColorSchemaNotifications();
    notification(`
        ⚙️ <b>Initialization:</b><br/>
        • Created <code>minLisTails[]</code> as an initially <b>empty</b> array.<br/>
        • <code>minLisTails[]</code> will gradually store the <b>smallest possible tail</b> for increasing subsequences of different lengths.<br/>
        • Set the pointer <code>index</code> to <b>0</b>, ready to process the first element in <code>nums[]</code>.<br/><br/>
        🚀 Now starting the loop to process each <code>num</code> of <code>nums</code> in order.
    `);

    while (index < nums.length) {
        startPartialBatch();
        const num = nums[index];

        notification(`
          📌 Processing <code>${makeColoredSpan('nums[index]', CURRENT_COLOR)}</code> = 
          <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> → finding its correct position in <code>minLisTails[]</code>.<br/>
          🔹 <code>minLisTails[i]</code> stores the <b>smallest possible last element</b> of any increasing subsequence of length <b>i + 1</b>.<br/>
          🔹 We use <b>binary search</b> to find the <b>replacement position</b> for 
          <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> — the first index <code>idx</code> where 
          <code>minLisTails[idx] ≥ ${makeColoredSpan(num, CURRENT_COLOR)}</code>.<br/>
          💡 This index represents the position of the <b>smallest tail</b> that is 
          <b>greater than or equal</b> to the current number, meaning 
          <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> can safely replace it 
          to keep subsequences of length <b>idx + 1</b> ending with the <b>smallest possible value</b>.<br/>
          💡 During binary search, we keep narrowing the range using two pointers (<b>left</b>, <b>right</b>):<br/>
          • When <code>minLisTails[mid] &lt; ${makeColoredSpan(num, CURRENT_COLOR)}</code>, we move <b>left</b> rightward, since the replacement spot (if it exists) must be after <code>mid</code>.
          <small>
          💡 If no such spot exists — meaning <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> is greater than all current tails — it will later be <b>appended</b> to extend the LIS.
          </small><br/>
          • When <code>minLisTails[mid] ≥ ${makeColoredSpan(num, CURRENT_COLOR)}</code>, we move <b>right</b> leftward, because this <code>mid</code> or an earlier index could be the replacement spot.<br/>
          📘 At the end of the search, <b>left</b> will automatically point to the first index satisfying 
          <code>minLisTails[left] ≥ ${makeColoredSpan(num, CURRENT_COLOR)}</code> — the final <b>replacement position</b> if such a position exists.<br/>
          • If <b>left</b> equals <code>minLisTails.length</code>, it means <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> is greater than all tails, so there is no replacement position and we <b>append</b> it to extend the LIS.
        `);

        let left = 0, right = minLisTails.length - 1;

        // Binary Search to find the replacement position of num in minLisTails[]
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            minLisTails.makeVisManagerForIndex(mid).addClass(CURRENT_MIN_LIS_TAIL);

            notification(`
              🔎 <b>Binary Search:</b> Checking 
              <code>minLisTails[${mid}] = ${makeColoredSpan(minLisTails[mid], CURRENT_MIN_LIS_TAIL_COLOR)}</code> 
              to determine the <b>replacement position</b> for <b>${makeColoredSpan(num, CURRENT_COLOR)}</b>.
            `);

            if (minLisTails[mid] < num) {
                notification(`
                  ✅ <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> is greater than 
                  <code>minLisTails[${mid}]</code> (<b>${minLisTails[mid]}</b>), 
                  so any valid <b>replacement position</b> (if it exists) must be in the <b>right half</b>.<br/>
                  <small>⚠️ If no such position exists (i.e., it's greater than all current tails), we will <b>append</b> it to extend the LIS by one.</small>
                `);
                left = mid + 1;
            } else {
                notification(`
                  ❌ <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> is 
                  <b>less than or equal</b> to <code>minLisTails[${mid}]</code> (<b>${minLisTails[mid]}</b>).<br/>
                  👉 A valid <b>replacement position</b> could be <b>here</b> or to the <b>left</b>, so we continue searching left.<br/>
                  <small>💡 If no smaller index qualifies, this <code>mid</code> will remain the final replacement point after the loop.</small>
                `);
                right = mid - 1;
            }

            minLisTails.makeVisManagerForIndex(mid).removeClass(CURRENT_MIN_LIS_TAIL);
        }

        if (left < minLisTails.length) {
            notification(`
              ⚡ <b>Replace</b> at the <b>replacement position (${left})</b>:
              <code>minLisTails[${left}] = ${minLisTails[left]}</code> → <b>${makeColoredSpan(num, CURRENT_COLOR)}</b>.<br/>
              This keeps the <b>smallest possible</b> tail for subsequences of length <b>${left + 1}</b>.
            `);
            minLisTails[left] = num;
        } else {
            notification(`
              📌 <b>Append</b> <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> to <code>minLisTails[]</code> → 
              All current tails are smaller; we <b>extend</b> the LIS by one.
            `);
            minLisTails.push(num);
        }

        index += 1;
        endBatch();
    }

    notification(`
      🏁 <b>Finished!</b> The length of the longest increasing subsequence (LIS) is <b>${minLisTails.length}</b>.<br/>
      🔹 This works because we <b>tracked the smallest possible last element</b> for increasing subsequences of different lengths.<br/>
      🔹 Although <code>minLisTails[]</code> does <b>not</b> store the actual LIS, its <b>length</b> correctly represents the LIS length.
    `);
    
    return minLisTails.length;
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();

  notification(`
    🎨 <b>Color Palette & Legend</b><br/>
    • ${makeColoredSpan('nums[index] or index', CURRENT_COLOR)} — the <b>current input element</b> being processed (or its index in <code>nums[]</code>).<br/>
    • ${makeColoredSpan('minLisTails[mid] or mid', CURRENT_MIN_LIS_TAIL_COLOR)} — the <b>minLisTails</b> element currently inspected during <b>binary search</b> (or its index).
  `);
}

function initClassProperties() {
    setClassProperties(CURRENT, { backgroundColor: CURRENT_COLOR });
    setClassProperties(CURRENT_MIN_LIS_TAIL, { backgroundColor: CURRENT_MIN_LIS_TAIL_COLOR });
}

Approach

Goal

Find the length of the longest increasing subsequence (LIS) using a greedy + binary search method.

Key Idea

Maintain an array minLisTails[] where minLisTails[i] is the smallest possible last element of any increasing subsequence of length i + 1. This structure may not equal an actual LIS, but its length always equals the LIS length.

How We Place Each Number

For each incoming value num (i.e., nums[index]), we find its replacement position in minLisTails[] — the first index idx such that minLisTails[idx] ≥ num. Replacing there keeps the tail for length idx + 1 as small as possible, maximizing our ability to extend to longer subsequences later. If no such index exists (the value is larger than all current tails), we append it, which extends the LIS by one.

Binary Search (Replacement Position)

We binary search over minLisTails using pointers left and right. At each step, inspect minLisTails[mid] (the element currently highlighted in blue in the visualization).
If minLisTails[mid] < num: move left rightward, since the replacement spot (if it exists) must be after mid.
💡 If no such spot exists (i.e., the value is greater than all tails), we will append it to extend the LIS.
If minLisTails[mid] ≥ num: move right leftward (this mid or an earlier index could be the replacement spot).
When the search finishes, left is the first index satisfying minLisTails[left] ≥ num — i.e., the replacement position. If left === minLisTails.length, it means that no replacement point can be found and num is the greatest value encountered so far, so we append it to extend the LIS.

Why This Works

By keeping each minLisTails[i] as small as possible, we maximize the ability to extend subsequences to greater lengths. Replacements do not reduce the length already achieved; they only improve the “future potential” of increasing thatlength. Appends increase the achieved length by one.

Result

After processing all numbers, minLisTails.length is the length of the LIS.

Time Complexity

O(n × log n), where n is the number of elements in the input array.

For each element num in the array, we perform a binary search on minLisTails[] to find its replacement position. The size of minLisTails[] grows gradually from 1 up to at most n, so the total work is: log(1) + log(2) + ... + log(n) = log(n!), which simplifies to O(n × log n).

This is much faster than the O(n²) dynamic programming approach, since we use binary search to locate each element’s position efficiently rather than scanning all previous elements.

Space Complexity

O(n), where n is the number of elements in the input array.

The algorithm uses an auxiliary array minLisTails[], which at most grows to size n — in the case where the entire array is strictly increasing. Apart from this, only a few constant-sized variables (left, right, mid, etc.) are used during binary search.

Therefore, the overall space requirement is O(n).

Input-1

Longest Increasing Subsequence - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Goal

Key Idea

How We Place Each Number

Binary Search (Replacement Position)

Why This Works

Result

Time Complexity

Space Complexity