Ctrl K

Sorted Into Runs of Three

Medium
You are given an integer array values sorted in non-decreasing order. Can all of its elements be distributed among one or more runs so that: - every element belongs to exactly one run; - the numbers in each run go up by exactly 1 (for example, 3, 4, 5, 6); - every run has at least three numbers? Return True if this is possible, otherwise False.
Example 1
values=[4, 5, 5, 6, 6, 7] → True

It splits into the runs 4, 5, 6 and 5, 6, 7, both of length 3.

Example 2
values=[-2, -1, 0, 1, 1, 2] → False

The second 1 must either start a new run or extend an old one. The run -2…1 already has a 1, and 1, 2 is only two numbers with no 3 to follow. No valid split.

Example 3
values=[0, 1, 2, 3, 4] → True

A single run of all five numbers works.

Constraints
  • 1 ≤ len(values) ≤ 10⁴
  • -1000 ≤ values[i] ≤ 1000
  • values is sorted in non-decreasing order
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsJobs With a Cooldown MediumSpread Out the Labels MediumCross Out Half the List MediumA Plan for Draining Ponds MediumNarrowest Range Touching Every List Hard
loading Python…
Input
values=[4, 5, 5, 6, 6, 7]
Expected
True

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