Introduction

This problem usually means: find a starting index in a circular array such that the running sum never becomes negative as you traverse the whole array once. It is the same core idea as the classic gas-station problem, and there is a clean O(n) greedy solution.

First Check Whether a Solution Can Exist

If the total sum of the entire array is negative, no starting index can work. That is because one full traversal always adds every element exactly once. If the grand total is already below zero, the running sum must end below zero somewhere.

So the first rule is simple:

• total sum negative: no solution
• total sum non-negative: at least one valid start exists

The interesting part is finding that start efficiently.

The Greedy Insight

Suppose you start at index s and keep a running sum. If the running sum becomes negative at index i, then no index between s and i can be a valid start.

Why? Because any later start inside that failed segment would skip some positive contribution from the beginning of the segment, so it would fail no later than i as well.

That means when a failure happens, you can jump directly to i + 1 and continue scanning. You never need to reconsider the indices you just ruled out.

A Linear-Time Implementation

Here is a compact Python implementation:

1def find_start(nums):
2    total = 0
3    running = 0
4    start = 0
5
6    for i, value in enumerate(nums):
7        total += value
8        running += value
9
10        if running < 0:
11            start = i + 1
12            running = 0
13
14    if total < 0 or start == len(nums):
15        return -1
16    return start
17
18
19print(find_start([1, -2, 3, -1, 2]))   # 2
20print(find_start([2, -1, -1]))         # 0
21print(find_start([-2, 1, 1]))          # 1
22print(find_start([1, -3, 1]))          # -1

The algorithm performs one pass, uses constant extra space, and returns one valid start if it exists.

Why the Algorithm Works

The proof rests on two observations.

First, if the total sum is negative, no solution exists. That part is necessary.

Second, if a segment from start through i has negative cumulative sum, then every candidate start inside that segment is impossible. By resetting start to i + 1, you discard only impossible choices.

Because each index is examined once, the full algorithm is linear.

Prefix-Sum Interpretation

There is another way to see the same answer. Build prefix sums of the array in normal order. A valid starting position is the index immediately after the minimum prefix sum, as long as the total sum is non-negative.

For example, with:

nums = [1, -2, 3, -1, 2]

the prefix sums are:

[1, -1, 2, 1, 3]

The minimum prefix sum is -1, which occurs after index 1. So index 2 is a valid start. That matches the greedy algorithm above.

The greedy method is usually preferred in interviews and contests because it avoids storing the prefix array.

Edge Cases to Handle

A few cases are worth checking explicitly:

• all numbers non-negative: index 0 is valid
• all numbers negative: no solution
• single-element array: valid only if that element is non-negative
• multiple valid answers: the greedy method returns one of them, often the earliest valid answer after the last failure

If the problem asks for the smallest valid index specifically, verify whether the standard greedy return value matches that requirement. In many formulations it does, but the exact statement matters.

Common Pitfalls

• Forgetting to check the total sum before returning a start.
• Resetting the start index without resetting the running sum.
• Solving the circular problem with an O(n^2) simulation from every index.
• Misreading the requirement as "sum stays exactly zero." In most versions the requirement is "never goes below zero."
• Returning 0 on failure instead of a clear sentinel such as -1.

Summary

• The problem is a circular running-sum problem with a standard greedy solution.
• A solution exists only when the total sum of the array is non-negative.
• When the running sum fails at index i, every start inside that failed segment is impossible.
• The greedy algorithm runs in O(n) time and O(1) extra space.
• The same answer can also be understood as the index after the minimum prefix sum.