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

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/mode-query-implementation

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

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

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/mode-query-implementation

Repovive

Mode Query - Implementation - Sqrt Decomposition | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Mode Query - Implementation

The code

Here's the add/remove logic:

function add(value)
    freqCount[cnt[value]] := freqCount[cnt[value]] - 1
    cnt[value] := cnt[value] + 1
    freqCount[cnt[value]] := freqCount[cnt[value]] + 1
    if cnt[value] > maxFreq then
        maxFreq := cnt[value]

function remove(value)
    freqCount[cnt[value]] := freqCount[cnt[value]] - 1
    cnt[value] := cnt[value] - 1
    freqCount[cnt[value]] := freqCount[cnt[value]] + 1
    if freqCount[maxFreq] = 0 then
        maxFreq := maxFreq - 1

Both are $O(1)$ . The query answer is $maxFreq$ .