0822MediumArrayHash TableMathCounting

Out of Step Seat Pairs

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 single row of a theatre is filled from left to right. Seat i, numbering the seats from 0, is held by a guest whose ticket number is tickets[i].

Take any two seats i and j with i < j. The pair is in step when the number of seats between them matches the rise in ticket number, that is when j - i == tickets[j] - tickets[i]. Every other pair is out of step.

Return how many pairs of seats are out of step. A pair is counted once, not once per order, and a seat is never paired with itself.

Examples

Example 1

Input: tickets = [8, 9, 3]
Output: 2

The pair of seats 0 and 1 is in step: the seats are 1 apart and the ticket numbers 8 and 9 are also 1 apart. The pair 0 and 2 is out of step, 2 seats apart against a ticket rise of -5, and so is the pair 1 and 2, 1 seat apart against a rise of -6.

Example 2

Input: tickets = [4, 5, 6, 7, 8]
Output: 0

The ticket number climbs by exactly one from each seat to the next, so for every one of the ten pairs the seat gap and the ticket rise are the same number.

Example 3

Input: tickets = [3, 4, 3, 4]
Output: 4

Seats 0 and 1 are in step, and so are seats 2 and 3, each pair being 1 seat apart with a ticket rise of 1. The other four pairs, namely 0 with 2, 0 with 3, 1 with 2 and 1 with 3, are all out of step.

Constraints

1 <= tickets.length <= 10^5
1 <= tickets[i] <= 10^9
The count can exceed the range of a signed 32-bit integer; it stays below 10^10.

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 count_out_of_step(tickets: list[int]) -> int:

Java

public long countOutOfStep(int[] tickets)

The intended approach

Time O(n) for n seats.Space O(n) for the tally of values.

Rearranging the in-step test gives `tickets[i] - i == tickets[j] - j`, so a pair is in step exactly when the two seats agree on ticket number minus seat index. Start from the number of pairs the row has altogether, then walk the seats keeping a tally of how many earlier seats carry each value of that quantity, subtracting the matches each new seat brings.

Pythonentry point: count_out_of_step

def count_out_of_step(tickets):
    # A pair is in step exactly when ticket minus seat index takes the same value at
    # both seats, so count the pairs sharing that value and subtract them from the
    # number of pairs there are altogether. One walk keeps a tally of how many
    # earlier seats carry each value, and each seat cancels the pairs it makes with
    # them.
    # Time: O(n) for n seats.
    # Space: O(n) for the tally.
    n = len(tickets)
    total = n * (n - 1) // 2
    seen = {}
    for i in range(n):
        key = tickets[i] - i
        earlier = seen.get(key, 0)
        total -= earlier
        seen[key] = earlier + 1
    return total

The obvious version

Two nested loops over every pair of seats with the smaller index first, applying the test from the statement literally to each pair.

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_count_out_of_step(tickets):
    """Look at every pair of seats and test the rule on it as written."""
    n = len(tickets)
    total = 0
    for i in range(n):
        for j in range(i + 1, n):
            if j - i != tickets[j] - tickets[i]:
                total += 1
    return total

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