Balanced Weather Audit

Indices of the longest subarray with equal counts of -1, 0, and 1

MediumArrays & HashingPrefix CountsHash Maps

A weather station records one condition code each minute:

  • -1: icing conditions
  • 0: dry conditions
  • 1: rainy conditions

An auditor wants to select a nonempty contiguous span of the log in which all three condition codes occur equally often.

Given the array conditions, return the inclusive, zero-based start and end indices of the longest such span as [start, end]. If several spans have the same maximum length, choose the one with the smallest start index.

If no qualifying span exists, return an empty array.

Examples

Example 1

Input: conditions = [-1,0,1,1,0,-1,0]
Output: [0,5]

The first six records contain two occurrences of each condition. Including the final dry record would break that balance, so the first six records form the longest qualifying span.

Example 2

Input: conditions = [-1,0,1,0,-1]
Output: [0,2]

Both the first three records and the last three records contain each condition once. No longer span qualifies, so the tie is resolved in favor of the earlier span.

Example 3

Input: conditions = [0,0,1]
Output: []

There are no icing records, so no nonempty span can contain equal numbers of all three conditions.

Constraints

  • 0 <= conditions.length <= 12000
  • Every element of conditions is -1, 0, or 1.
  • Returned indices are zero-based and inclusive.
  • Among equally long qualifying spans, return the one with the smallest start index.

The intended solution uses O(n) expected time and O(n) space. A qualifying nonempty span necessarily contains at least one occurrence of every condition.

Hints

Show hint 1

For each prefix, track the dry count minus the icing count and the rainy count minus the icing count.

Show hint 2

Two prefixes with the same pair of differences enclose a balanced span. Which occurrence of each pair should you retain to maximize its length?

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you count all qualifying spans instead of returning the longest one?
  • How would the prefix state change if the log had a fixed number k of condition categories, all of which had to occur equally often?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem