Playlist Mo Distinct Problem

Playlist Mo Distinct Problem — ExecCode Hard DSA Practice

Solve the Playlist Mo Distinct problem on ExecCode. Free online hard DSA practice in Two Pointers. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A playlist is an array of song ids. For many ranges, count distinct songs. Mo's algorithm sorts the queries into blocks so the two pointers move little, adding/removing frequencies in amortized sqrt time. Each query [l, r] is inclusive. Return the distinct counts. You are given: arr — song ids queries — ranges Return one distinct count per query. The same id twice in a range still counts as one distinct.

Examples

Input {'arr': [1, 2, 1, 3], 'queries': [[0, 3], [0, 2], [3, 3]]}; Output [3, 2, 1]. Input {'arr': [4, 4], 'queries': [[0, 1]]}; Output [1]. Input {'arr': [9], 'queries': [[0, 0]]}; Output [1]

Constraints

0-based indices Empty slice should not appear

Practice Playlist Mo Distinct free on ExecCode. Browse DSA problems, topic map, and placement guides.