A music app records song identifiers in the order in which the songs are played.

A song is played too soon if the same song appears again within a given number of positions.

Find all songs that were played too soon.

Class

SongRepeatChecker

Method Signature

List<Integer> findSongsPlayedTooSoon( List<Integer> playHistory, int gapLimit)

Parameters

• playHistory: Song identifiers in the order they were played.
• gapLimit: The maximum allowed distance between two positions containing the same song.

Returns

Return all song identifiers that appear at two distinct positions whose distance is at most gapLimit.

Return each qualifying song identifier only once. Order the result by when each song first qualifies while processing playHistory from left to right.

Return an empty list if no song qualifies.

Rules

• Positions use zero-based indexing.
• For two positions first and second, their distance is abs(first - second).
• The two positions must be different.
• A song qualifies if at least one pair of its positions has a distance less than or equal to gapLimit.

Constraints

• 1 ≤ playHistory.size() ≤ 100,000
• 1 ≤ playHistory.get(i) ≤ 1,000,000,000
• 0 ≤ gapLimit ≤ 100,000
• playHistory is never null.

Examples

Example 1

findSongsPlayedTooSoon( playHistory = List.of(7, 19, 42, 7, 33, 19), gapLimit = 4)

Returns List.of(7, 19).

Song 7 is repeated after three positions, and song 19 is repeated after four positions.

Example 2

findSongsPlayedTooSoon( playHistory = List.of(55, 12, 55, 55, 80), gapLimit = 1)

Returns List.of(55).

The plays of song 55 at positions 2 and 3 are one position apart.

Example 3

findSongsPlayedTooSoon( playHistory = List.of(9, 14, 22, 9, 14, 22), gapLimit = 2)

Returns an empty list.

Every repeated song is three positions away from its previous play.

Example 4

findSongsPlayedTooSoon( playHistory = List.of(60, 70, 60, 70, 60), gapLimit = 2)

Returns List.of(60, 70).

Both songs qualify, but song 60 qualifies first. Each song is returned only once.