Ctrl K

Shift a Segment to Match

Medium
You get an integer array values and an integer wanted. Exactly once, you pick a contiguous segment of the array (at least one element) and any integer x, which may be negative or zero, and add x to every element of the segment. Return the largest number of elements equal to wanted that the array can contain after this operation. Keep in mind that elements already equal to wanted inside the segment get shifted too, so with a nonzero x they stop matching.
Example 1
values=[4, 7, 7, 4, 7, 2], wanted=4 → 4

Shift the segment [7, 7, 4, 7] (indices 1–4) by −3: the 7s turn into 4s and the 4 inside becomes 1. The result [4, 4, 4, 1, 4, 2] holds four 4s.

Example 2
values=[3, 3, 3], wanted=3 → 3

Every element already equals 3; shifting any segment by 0 keeps it that way.

Example 3
values=[9, 1, 9, 9, 1], wanted=1 → 4
Constraints
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 50
  • 1 ≤ wanted ≤ 50
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsDisjoint Segments With a Target Sum MediumLevel the Jars MediumPass the Load to the Left MediumStrongest Product Team MediumThe Heaviest Reading Day Hard
loading Python…
Input
values=[4, 7, 7, 4, 7, 2], wanted=4
Expected
4

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