1009MediumArrayBit ManipulationSliding Window

The Longest Run of Masks Sharing No Channel

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A list of channel masks reads masks. Each mask is a positive whole number, and the bits of its binary form say which channels that mask claims.

A run of neighbouring masks is clean when no channel is claimed by two of its masks: for every pair in the run, no bit is set in both.

Return the length of the longest clean run. A run holding a single mask is always clean.

Examples

Example 1

Input: masks = [2, 4, 8, 3]
Output: 3

The first three masks each claim a single channel of their own, so they form a clean run of three. The last mask claims the two lowest channels, which clashes with the first mask, but the last three masks are clean together as well, so three is the best either way.

Example 2

Input: masks = [7, 7, 7]
Output: 1

All three masks claim the same channels, so no two of them sit in a run together and a single mask is the longest clean run.

Example 3

Input: masks = [1, 2, 4, 8, 16]
Output: 5

Every mask claims a channel no other one touches, so the whole list is clean.

Constraints

1 <= masks.length <= 10^5
1 <= masks[i] <= 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_nice_subarray(masks: list[int]) -> int:

Java

public int longestNiceSubarray(int[] masks)

The intended approach

Time O(n) over the list's length.Space O(1).

A run is clean exactly when every channel belongs to at most one of its masks. That means the run's masks overlap nowhere, so the channels the run claims altogether are simply all their bits together, with no bit contributed twice. So slide one window along the list, carrying the bits of everything inside it. To take a new mask in, check that it shares no bit with the carried bits; while it does, drop masks off the window's left end, clearing each one's bits as it goes, until the new mask fits. Then fold the new mask's bits in and note the window's length against the best seen. Dropping from the left is the right move because a mask that clashes with the carried bits clashes with some particular mask inside the window, and every window holding both of them is unclean, so nothing is lost by shrinking past the offender. The left end never moves backwards, so each mask enters and leaves the window once. Incidentally no clean run can be long: masks stay below a billion, so there are thirty channels to go round, and every mask claims at least one. The sweep never needs to know that.

Pythonentry point: longest_nice_subarray

def longest_nice_subarray(masks):
    used = 0
    lo = 0
    best = 0
    for hi in range(len(masks)):
        while used & masks[hi]:
            used ^= masks[lo]
            lo += 1
        used |= masks[hi]
        if hi - lo + 1 > best:
            best = hi - lo + 1
    return best

The obvious version

Take every starting place and grow the run one mask at a time, testing the newest mask against every mask already inside and stopping that start as soon as a clash turns up, since no longer run from there can be clean either. Costs every run times its length rather than one sliding window.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_nice_subarray(masks):
    n = len(masks)
    best = 0
    for start in range(n):
        for end in range(start, n):
            clash = False
            for at in range(start, end):
                if masks[at] & masks[end]:
                    clash = True
                    break
            if clash:
                break
            if end - start + 1 > best:
                best = end - start + 1
    return best

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in