Implement Prefix Sums and KadaneStep 5 of 5

Pivot Index

12345

Step 5: Pivot Index

Finish with a clean prefix-sum classic. The pivot index is where the sum of everything to its left equals the sum of everything to its right.

Write pivot_index(nums):

  • Compute the total sum once.
  • Walk left to right keeping a running left sum. At index idx, the right sum is total - left - nums[idx].
  • Return the leftmost idx where left equals the right sum, otherwise -1.
Hints
Starter code
class RangeSum:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def query(self, i, j):
        return self.prefix[j + 1] - self.prefix[i]


def subarray_sum_equals_k(nums, k):
    counts = {0: 1}
    running = 0
    total = 0
    for x in nums:
        running += x
        total += counts.get(running - k, 0)
        counts[running] = counts.get(running, 0) + 1
    return total


class DiffArray:
    def __init__(self, n):
        self.n = n
        self.diff = [0] * (n + 1)

    def add(self, i, j, delta):
        self.diff[i] += delta
        self.diff[j + 1] -= delta

    def result(self):
        out = []
        running = 0
        for k in range(self.n):
            running += self.diff[k]
            out.append(running)
        return out


def max_subarray(nums):
    best = nums[0]
    current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best


def pivot_index(nums):
    """Return the leftmost pivot index, or -1 if none exists."""
    # TODO: total sum once, running left sum, compare to total - left - nums[idx]
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges