Get Mode Array Updates

You are given an array of N positive integers, A1, A2 ,…, AN.
Also, given a Q updates of form:

  • i j: Update Ai = j. 1 ≤ i ≤ N.

Perform all updates and after each such update report mode of the array. Therefore, return an array of Q elements, where ith element is mode of the array after ith update has been executed.

Notes

  • Mode is the most frequently occuring element on the array.
  • If multiple modes are possible, return the smallest one.
  • Update array input is via a Q*2 array, where each row represents a update.

For example,

A=[2, 2, 2, 3, 3]

Updates=    [ [1, 3] ]
            [ [5, 4] ]
            [ [2, 4] ]

A = [3, 2, 2, 3, 3] after 1st update.
3 is mode.

A = [3, 2, 2, 3, 4] after 2nd update.
2 and 3 both are mode. Return smaller i.e. 2.

A = [3, 4, 2, 3, 4] after 3rd update.
3 and 4 both are mode. Return smaller i.e. 3.

Return array [3, 2, 3].

Constraints
1 ≤ N, Q ≤ 105
1 ≤ j, Ai ≤ 109

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Get Mode Array Updates on Interview Code Editor
Click here to start solving coding interview questions