Topic: Learning notes

LeetCode 724: Find a Pivot Index in TypeScript

Find the leftmost pivot index with a total sum and one running left sum, then make the loop invariant and O(n) analysis explicit.

This note starts with an implementation I wrote, then uses AI to review the derivation and test cases. Before publishing, I checked the program behavior, complexity, and problem constraints again.

Problem

Original problem: LeetCode 724: Find Pivot Index

Given an integer array nums, return the leftmost index i whose elements strictly to the left have the same sum as the elements strictly to the right. A missing side has a sum of 0. Return -1 when no such index exists.

For [1, 7, 3, 6, 5, 6], the answer is 3 because 1 + 7 + 3 and 5 + 6 are both 11.

The original code was correct, but its interview explanation needed work

The first implementation totals the array, then maintains the sum to the left while scanning from left to right.

function pivotIndex(nums: number[]): number {
  let total = 0;

  for (let index = 0; index < nums.length; index += 1) {
    total += nums[index];
  }

  let leftSum = 0;

  for (let index = 0; index < nums.length; index += 1) {
    const rightSum = total - leftSum - nums[index];

    if (leftSum === rightSum) return index;

    leftSum += nums[index];
  }

  return -1;
}

It returns the right result and does not mutate its input. The missing parts were the explanation, not a new data structure.

• Two complete scans are O(2n). Big O drops constant factors, so the conventional form is O(n).
• total, leftSum, and the per-iteration rightSum are a fixed number of scalars. Auxiliary space is O(1), not O(n).
• The formula needs an invariant. State what leftSum contains before the comparison and why a left-to-right return gives the leftmost answer.
• console.log() is not a test. Assertions fail when the result is wrong.

Recomputing both sides for every index would scan the same values repeatedly and take O(n²) time.

Better version: keep the same idea and name the state

The original method is already a good interview solution. This version mainly makes the state easier to discuss.

function pivotIndex(nums: number[]): number {
  const total = nums.reduce((sum, num) => sum + num, 0);
  let leftSum = 0;

  for (let index = 0; index < nums.length; index += 1) {
    const rightSum = total - leftSum - nums[index];

    if (leftSum === rightSum) return index;

    leftSum += nums[index];
  }

  return -1;
}

total contains every value. At index index, leftSum does not yet include nums[index], so subtracting both from total leaves exactly the sum to the right.

Why the loop is correct

At the start of every iteration, leftSum equals the sum of nums[0] through nums[index - 1].

The first iteration starts at index = 0, where the empty left side correctly has sum 0. If the invariant holds at an index, total - leftSum - nums[index] is the sum from nums[index + 1] to the end. Equal sums make the current index a pivot. Otherwise, adding nums[index] to leftSum establishes the invariant for the next iteration.

The scan moves left to right and returns at the first match, so it returns the leftmost pivot index.

Minimal verification

import assert from "node:assert/strict";

assert.equal(pivotIndex([1, 7, 3, 6, 5, 6]), 3);
assert.equal(pivotIndex([1, 2, 3]), -1);
assert.equal(pivotIndex([5]), 0);
assert.equal(pivotIndex([0, 0]), 0);

The one-element and all-zero cases check the empty-side rule and the leftmost-result requirement.

Complexity and transferable idea

One scan computes the total and another searches for the pivot, so time is O(n). The function keeps only scalar state, so auxiliary space is O(1).

This pattern appears whenever processed values form the left side and unprocessed values form the right side. Compute the total once, maintain prefix state, and derive the remaining sum without allocating a prefix-sum array.

Common mistakes

• Counting the current value on either side.
• Continuing after a match and returning a later pivot.
• Leaving the analysis as O(2n) instead of simplifying it to O(n).
• Calling a fixed number of variables O(n) extra space.

External references

• LeetCode 724: Find Pivot Index: original problem, examples, and constraints.
• TypeScript Handbook: More on Functions: function parameter and return-type syntax.
• Node.js: assert.equal(): assertions for program results.