#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/distinct-values-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/distinct-values-implementation

Repovive

Distinct Values - Implementation - Sqrt Decomposition | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Distinct Values - Implementation

Complete solution

Here's the full solution:

function solve(arr, queries)
 // Coordinate compress values to [0, n)
 compress(arr)

 B := floor(sqrt(n)) + 1
 sort queries by (floor(l / B), r)

 cnt := array of size n, initialized to 0
 distinctCount := 0
 currentL := 0
 currentR := -1
 answers := array of size q

 for each (l, r, index) in queries
 while currentR < r
 currentR := currentR + 1
 add(arr[currentR])
 while currentL > l
 currentL := currentL - 1
 add(arr[currentL])
 while currentR > r
 remove(arr[currentR])
 currentR := currentR - 1
 while currentL < l
 remove(arr[currentL])
 currentL := currentL + 1
 answers[index] := distinctCount

 return answers

Time: $O((n + q)\sqrt{n})$ . Space: $O(n)$ .