Gaps Across All Windows

Hard

For an array of numbers, call a **gap** any place in its sorted copy where neighbouring elements differ by more than 1. For example, [5, 1, 3, 3] sorts into [1, 3, 3, 5], which has two gaps: between 1 and 3 and between 3 and 5. You get an array values. Count the gaps of every contiguous non-empty subarray (window) and return the sum of these counts.

Example 1

values=[3, 1, 4, 2] → 5

The windows [3, 1], [1, 4], [4, 2], [3, 1, 4] and [1, 4, 2] have one gap each. Single-element windows and the whole array, which sorts into [1, 2, 3, 4], have none. The total is 5.

Example 2

values=[2, 2, 4, 4] → 4

There is a gap between 2 and 4 in every window holding both: [2, 4], [2, 4, 4], [2, 2, 4] and [2, 2, 4, 4]. Repeated values add no gaps.

Example 3

values=[1, 1, 1] → 0

Constraints

1 ≤ len(values) ≤ 1000
1 ≤ values[i] ≤ len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Ordered Set

Similar problems

Flowers in Bloom on Visit Day Hard Climbing Along Rows and Columns Hard Kitchen Order Board Medium Two Warehouses, One Report Easy Warehouse Top Stock Medium

Input

values=[3, 1, 4, 2]

Expected

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