Find Pivot Index
Easy About 10 min Free, no account needed
The index where everything to the left weighs the same as everything to the right.
The brief
Given an integer array nums, return the leftmost index where the sum of
the elements strictly to the left equals the sum strictly to the right.
Return -1 if no such index exists.
- For the first index the left sum is
0; for the last, the right sum is0.
The obvious approach re-adds both sides for every candidate index, O(n2). The hidden test has 200,000 elements and no pivot, the worst case, so the quadratic version is too slow. You will need an approach that runs in close to O(n).
Starter code
using System;
public class Solution
{
// TODO: return the leftmost index whose left-side sum equals its right-side sum, or -1.
public int PivotIndex(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Prefix sums
- Carry running totals or prefix state so any range question becomes a lookup.
Related katas
- Best Time to Buy and Sell Stock Easy Free Maximize the profit from a single buy followed by a later sell.
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Product of Array Except Self Medium Free For each index, return the product of all other elements, without division.
- Subarray Sum Equals K Medium Free Count contiguous subarrays whose elements sum to a target k.