March Over Enemy Forts

Easy

Cells along a line are described by the array line: - 1 is one of your forts; - 0 is an enemy fort; - -1 is an empty cell. You send an army from one of your forts at cell i to an empty cell j, to the left or to the right. The army may only pass over enemy forts: every cell strictly between i and j must be 0. Every enemy fort it passes is captured. Return the largest number of enemy forts a single such march can capture. If no march is possible (or you have no forts at all), return 0.

Example 1

line=[0, 1, 0, 0, 0, -1, 0, 1] → 3

From the fort at cell 1 the army reaches the empty cell 5, capturing three enemy forts (cells 2, 3 and 4). From the fort at cell 7 to cell 5 it captures only one. The answer is 3.

Example 2

line=[1, 0, 1, 0, 0] → 0

There is no empty cell to march to, so the answer is 0.

Example 3

line=[-1, 1, 0, 0] → 0

The army can step into the empty cell 0 next to it, but there are no enemy forts on the way. The answer is 0.

Constraints

1 ≤ len(line) ≤ 10⁵
line[i] is -1, 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers

Similar problems

Squeeze Repeats Out of a Sorted Array Easy Drop the Unwanted Value Easy Merge Into the Spare Tail Easy Zeros to the Back Easy Values in Both Lists Easy

Input

line=[0, 1, 0, 0, 0, -1, 0, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 103 tests on the server, hidden ones included.