3sum - 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 FIRST = 'first', FIRST_COLOR = 'gray';
const LEFT = 'LEFT', LEFT_COLOR = 'orange';
const RIGHT = 'RIGHT', RIGHT_COLOR = 'blue';

function visMainFunction(inputNums) {
    initClassProperties();

    explanationAndColorPaletteNotifications();

    notification(`
      🔍 <b>Goal:</b> find all <b>unique triplets</b> <code>(a, b, c)</code> such that <b>a + b + c = 0</b>.<br/>
      📌 We first <b>sort</b> the array. Sorting allows us to use a clean <b>two-pointer</b> strategy after fixing one number.
    `);

    startBatch();
    inputNums.sort((a, b) => a - b);
    const nums = VisArray.from(inputNums);
    const result = new VisArray().options({
        labelExtractionPolicy: (data) => data.join(', ')
    });

    let firstIndex = 0;
    makeVisVariable(firstIndex).registerAsIndexPointer(nums, FIRST);
    endBatch();

    while (firstIndex < nums.length - 2) {
        startPartialBatch();

        notification(`
          📌 Select <b>${makeColoredSpan('nums[firstIndex]', FIRST_COLOR)}</b> = 
          <b>${makeColoredSpan(nums[firstIndex], FIRST_COLOR)}</b> as the <b>first</b> number in the triplet.
        `);

        if (firstIndex !== 0 && nums[firstIndex] === nums[firstIndex - 1]) {
            notification(`
              🔹 <b>Skipping duplicate first value</b> at index <b>${makeColoredSpan(firstIndex, FIRST_COLOR)}</b>
              (value <b>${makeColoredSpan(nums[firstIndex], FIRST_COLOR)}</b>).<br/>
              We’ve already used this value as the <b>first</b> number and explored all pairs while its duplicates were available as second/third numbers.
              Reusing it as the first would only recreate triplets, so we skip to keep results <b>unique</b>.
            `);
            firstIndex += 1;
            continue;
        }

        const firstNum = nums[firstIndex];
        let leftIndex = firstIndex + 1;
        let rightIndex = nums.length - 1;

        notification(`
          🎯 Use two pointers with fixed first value:<br/>
          • ${makeColoredSpan('leftIndex', LEFT_COLOR)} = ${makeColoredSpan(leftIndex, LEFT_COLOR)} 
            (<code>nums[leftIndex]</code> = <b>${makeColoredSpan(nums[leftIndex], LEFT_COLOR)}</b>)<br/>
          • ${makeColoredSpan('rightIndex', RIGHT_COLOR)} = ${makeColoredSpan(rightIndex, RIGHT_COLOR)} 
            (<code>nums[rightIndex]</code> = <b>${makeColoredSpan(nums[rightIndex], RIGHT_COLOR)}</b>)
        `);

        const leftVis = makeVisVariable(leftIndex).registerAsIndexPointer(nums, LEFT).createVis(false);
        const rightVis = makeVisVariable(rightIndex).registerAsIndexPointer(nums, RIGHT).createVis(false);

        while (leftIndex < rightIndex) {
            const total = nums[leftIndex] + nums[rightIndex] + firstNum;

            notification(`
              🔎 Check triplet: 
              (<b>${makeColoredSpan(firstNum, FIRST_COLOR)}</b>, 
               <b>${makeColoredSpan(nums[leftIndex], LEFT_COLOR)}</b>, 
               <b>${makeColoredSpan(nums[rightIndex], RIGHT_COLOR)}</b>) → sum = <b>${total}</b>
            `);

            if (total === 0) {
                notification(`
                  ✅ <b>Valid triplet</b> found: 
                  (<b>${makeColoredSpan(firstNum, FIRST_COLOR)}</b>, 
                   <b>${makeColoredSpan(nums[leftIndex], LEFT_COLOR)}</b>, 
                   <b>${makeColoredSpan(nums[rightIndex], RIGHT_COLOR)}</b>). 
                  Adding to <b>result</b>.
                `);

                result.push([firstNum, nums[leftIndex], nums[rightIndex]]);

                notification(`
                    We've already explored all pairs where the current duplicate values of <b>nums[leftIndex]</b> and <b>nums[rightIndex]</b> were available as second/third numbers.<br/>
                    Keeping them would only regenerate the <b>same triplet</b> with this fixed first.<br/>
                    We advance ${makeColoredSpan('leftIndex', LEFT_COLOR)} to the <b>last occurrence</b> of its current value and retreat ${makeColoredSpan('rightIndex', RIGHT_COLOR)} to the <b>first occurrence</b> of its current value before moving both inward to land on <b>new values</b> to form fresh triplets.
                `);
                while (leftIndex < rightIndex && nums[leftIndex + 1] === nums[leftIndex]) leftIndex += 1;
                while (leftIndex < rightIndex && nums[rightIndex - 1] === nums[rightIndex]) rightIndex -= 1;
                
                notification(`
                    ↔️ Moving pointers inward to shrink the window and land on new values of ${makeColoredSpan('leftIndex', LEFT_COLOR)} and ${makeColoredSpan('rightIndex', RIGHT_COLOR)}: 
                    ${makeColoredSpan('leftIndex', LEFT_COLOR)} → ${makeColoredSpan(leftIndex+1, LEFT_COLOR)}, 
                    ${makeColoredSpan('rightIndex', RIGHT_COLOR)} → ${makeColoredSpan(rightIndex-1, RIGHT_COLOR)}.
                `);

                leftIndex += 1;
                rightIndex -= 1;
            } else if (total < 0) {
                notification(`
                  ➡️ Sum <b>${total}</b> is <b>&lt; 0</b>. 
                  Increase the sum by moving ${makeColoredSpan('leftIndex', LEFT_COLOR)} one step right:
                  ${makeColoredSpan('leftIndex', LEFT_COLOR)} = ${makeColoredSpan(leftIndex, LEFT_COLOR)} → ${makeColoredSpan(leftIndex + 1, LEFT_COLOR)}.
                `);
                leftIndex += 1;
            } else {
                notification(`
                  ⬅️ Sum <b>${total}</b> is <b>&gt; 0</b>. 
                  Decrease the sum by moving ${makeColoredSpan('rightIndex', RIGHT_COLOR)} one step left:
                  ${makeColoredSpan('rightIndex', RIGHT_COLOR)} = ${makeColoredSpan(rightIndex, RIGHT_COLOR)} → ${makeColoredSpan(rightIndex - 1, RIGHT_COLOR)}.
                `);
                rightIndex -= 1;
            }
        }

        leftVis.destroyVis();
        rightVis.destroyVis();

        notification(`
          🔄 Move to next <b>${makeColoredSpan('firstIndex', FIRST_COLOR)}</b>: 
          ${makeColoredSpan(firstIndex, FIRST_COLOR)} → ${makeColoredSpan(firstIndex + 1, FIRST_COLOR)}.
        `);
        firstIndex += 1;
        endBatch();
    }

    notification(`🏁 <b>Finished!</b> Returning all unique triplets.`);
    return result;
}

function explanationAndColorPaletteNotifications() {
  explanationNotification();
  notification(`
    🎨 <b>Color Palette</b><br/>
    • <span style="color:gray"><b>firstIndex / nums[firstIndex]</b></span><br/>
    • <span style="color:orange"><b>leftIndex / nums[leftIndex]</b></span><br/>
    • <span style="color:blue"><b>rightIndex / nums[rightIndex]</b></span>
  `);
}

function initClassProperties() {
    setClassProperties(LEFT,  { backgroundColor: LEFT_COLOR  });
    setClassProperties(RIGHT, { backgroundColor: RIGHT_COLOR });
    setClassProperties(FIRST, { backgroundColor: FIRST_COLOR });
}

Approach

Problem

Return all unique triplets (a, b, c) in an integer array such that a + b + c = 0.

Why Sort First?

Sorting enables a clean two-pointer sweep on the suffix after fixing a first value. In a sorted array: moving the leftIndex right increases the sum, and moving the rightIndex left decreases the sum. This monotonic control makes the search efficient.

Pointers

firstIndex — fixed first element of the triplet (outer loop).
leftIndex — starts at firstIndex + 1, moves right to increase the sum.
rightIndex — starts at the end, moves left to decrease the sum.

Algorithm

Sort the array ascending.
For each firstIndex:
- Skip duplicate first values: if nums[firstIndex] === nums[firstIndex-1], continue.
  We’ve already used this value as the first number and explored all pairs while its duplicates were available as second/third numbers. Reusing it would only recreate triplets without yielding any unexplored ones.
- Set two pointers: leftIndex = firstIndex+1, rightIndex = n-1.
- While leftIndex < rightIndex:
  - Compute total = nums[firstIndex] + nums[leftIndex] + nums[rightIndex].
  - If total === 0:
    - Record the triplet.
    - Move to next fresh leftIndex and rightIndex to shrink the window while avoiding duplicates:
      - First, skip duplicates by advancing leftIndex to the last occurrence of its current value and retreating rightIndex to the first occurrence of its current value.
      - Then, move both inward — do leftIndex++ and rightIndex-- — to shrink the window and continue on new values.
      We’ve already explored all pairs using these duplicate values as second/third; keeping them would regenerate the same triplet without yielding any unexplored ones.
  - If total < 0: the sum is too small. Increase the sum by moving leftIndex one step right (leftIndex++).
  - If total > 0: the sum is too large. Decrease the sum by moving rightIndex one step left (rightIndex--).

Correctness Intuition

Sorting gives a monotone relationship: moving leftIndex right increases the sum; moving rightIndex left decreases it.
For each fixed first value, the two-pointer sweep explores all pairs in the suffix that could complete zero.
De-duplication for the first value and for leftIndex/rightIndex after a match guarantees that each triplet is produced once.

Time Complexity

O(n²)
The array is first sorted in O(n log n). Then, for each of the n possible firstIndex values, we perform a linear two-pointer sweep across the subarray after it. Thus, the dominant cost is O(n × n) = O(n²).

Space Complexity

O(1) or O(n)
The sort step may use either O(1) or O(n) space depending on the algorithm implementation. Additionally, we need O(m) space to store the output list of unique triplets, where m is the number of valid solutions.

Input-1

3sum - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Problem

Why Sort First?

Pointers

Algorithm

Correctness Intuition

Time Complexity

Space Complexity